Creating a shape from a set of points

[Jeff Higgins]

Thanks for the vacuum wrap terminology. That was what I was imagining
when I was thinking shrink-wrap - so I apologize again for not having
the correct terms in my lexicon.

I am going to continue researching and will report back when I have
defined my chosen solution.

Thanks to all,
Todd

Now I'm wondering about a spiral shape,
something like a loosly coiled length of rope.
How to find the outline of the rope?

 

[Jeff Higgins]

Well, that goes back to the definition of "boundary". Assuming we're
defining it based on dot density, then as long as the negative area around
the "rope" is completely empty and satisfies the dot density requirement
for "outside", there shouldn't be a problem.

Other definitions of "boundary" may indeed run into issues with a shape
like that. Personally, I don't think that either "shrink wrap" or "vacuum
wrap" are very good ways of describing the problem. The "shrink wrap"
description has obvious problems, but "vacuum wrap" is really just a
slightly different packaging technique that uses the same sort of "outside
surface pulled inward" process that "shrink wrap" does. As such, "vacuum
wrap" doesn't deal with a "spiral rope" any better than "shrink wrap"
would.

Back to the 'C' example.
I hope Todd returns with a solution to his problem.

import java.awt.*;
import java.util.*;

public class Points {

public static void main(String[] args) {

Set<Point> sparse = new HashSet<Point>(100);
Set<Point> dense = new HashSet<Point>(1200);

Path2D path = new Path2D.Double();
path.moveTo(0.0, 0.0);
path.lineTo(40.0, 0.0);
path.lineTo(40.0, 10.0);
path.lineTo(10.0, 10.0);
path.lineTo(10.0, 50.0);
path.lineTo(40.0, 50.0);
path.lineTo(40.0, 60.0);
path.lineTo(0.0, 60.0);
path.closePath();

Random r = new Random();
for (int i = 0; i < 100; i++) {
Point p = new Point(r.nextInt(40), r.nextInt(60));
if (path.contains(p))
sparse.add(p); }

for (int x = 0; x < 41; x++) {
for (int y = 0; y < 11; y++) {
dense.add(new Point(x, y)); } }
for (int x = 0; x < 11; x++) {
for (int y = 11; y < 51; y++) {
dense.add(new Point(x, y)); } }
for (int x = 0; x < 41; x++) {
for (int y = 51; y < 61; y++) {
dense.add(new Point(x, y)); } }
}
}

 

[hoffmann]

Thanks for the vacuum wrap terminology. That was what I was imagining
when I was thinking shrink-wrap - so I apologize again for not having
the correct terms in my lexicon.

I am going to continue researching and will report back when I have
defined my chosen solution.

Thanks to all,
Todd

Todd,

maybe you can use alpha shapes:
First Google result:
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

Idea: roll a coin around the set of points as tight as possible
and draw the envelope. The diameter of the coin defines the
fuzziness of the contour.

Best regards --Gernot Hoffmann

 

[Tom Anderson]

maybe you can use alpha shapes:
First Google result:
http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Alpha_shapes_2/Chapter_main.html

Idea: roll a coin around the set of points as tight as possible and draw
the envelope. The diameter of the coin defines the fuzziness of the
contour.

That looks perfect!

It also looks very similar to the Minkowski sum (which i suggested!),
although i assume it's actually different in some way.

tom

--
It not infrequently happens that something about the earth, about the sky,
about other elements of this world, about the motion and rotation or even
the magnitude and distances of the stars, about definite eclipses of the
sun and moon, about the passage of years and seasons, about the nature
of animals, of fruits, of stones, and of other such things, may be known
with the greatest certainty by reasoning or by experience. -- St Augustine

 

[Todd]

Update:
This weekend, on a whim, I Googled for "concave hull" considering that
"convex hull" was very close to what I was looking for. There is an
algorithm out there using that terminology that can produce what I am
looking to do, however, it is available on an as-requested basis and I
have not yet received a reply from the author.

As I get more, I will let you know.

Todd

 

[Todd]

All,

I have not received any word from Portugal regarding the concave hull
algorithm. I have not been stagnating since I sent the request and
have developed a method that should suit my purposes.

I cut the plot area into a grid, represented internally by a 2D array
of ArrayLists. Then I analyze my data set, adding points to the
proper ArrayList corresponding to the grid within which a particular
point lies. What I end up with is a set of null and non-null
ArrayLists; the non-null contain data points. By tracking min and max
secondary indices by primary index of the 2D array, I have a set of
grids that contain the edges of the shape.

Currently, I then just take the minimum or maximum point in the grid,
depending upon whether the secondary index being processed is a
minimum or maximum index. This does not produce a perfect outline, so
I will need to develop a more robust grid analysis algorithm, but it
does give me a gross estimate of the desired solution.

Thanks again for all your help and suggestions,
Todd