Creating a shape from a set of points

[Todd]

Hello,

I have a bunch of points (defined in 2-D space, i.e., x-y coordinates)
that have a well-defined range that is easy to determine visually. I
need to determine the boundary of the input set of points and then
later test if a new point falls inside or outside of the boundary.

Is there any API, graphical or not, that takes a bunch of points and
creates a bounded shape, ignoring the points internal to the bounds?
Or does someone have some hints as to how I can use the methods of an
API to reduce my point set to just the boundary points?

Thanks,
Todd

 

[Stefan Ram]

API to reduce my point set to just the boundary points?

First idea: A point P is a boundary point iff there is another
point Q from the set, so that one open half plane of the two
half planes given by the line PQ does not contain any point
from the set. (This can be tested for each point Q, and
possibly be optimized by moving the plane test into the
generator for Q. It can also be modified to give the shape.)

Such tests are treated in computer graphics text books.

 

[Patricia Shanahan]

Hello,

I have a bunch of points (defined in 2-D space, i.e., x-y coordinates)
that have a well-defined range that is easy to determine visually. I
need to determine the boundary of the input set of points and then
later test if a new point falls inside or outside of the boundary.

Is there any API, graphical or not, that takes a bunch of points and
creates a bounded shape, ignoring the points internal to the bounds?
Or does someone have some hints as to how I can use the methods of an
API to reduce my point set to just the boundary points?

Are you looking for the convex hull? If so, I suggest a web search for
that with the word "java".

Patricia

 

[Todd]

Pete, and others,

I was concerned that I was unclear, but somewhat uncertain as to how
to be more so.

I am not concerned about there being a smooth, curved boundary to any
set of points. I am content to work with a shape defined by the
points that are the farthest from any given location (for simplicity,
imagine the center) within the cluster of data points. These maximal
points define what I would call the boundary of the shape and the
shape would be a connect-the-dots type shape.

Is that any clearer?

Todd

 

[Todd]

Are you looking for the convex hull? If so, I suggest a web search for
that with the word "java".

Patricia

Patricia,

I had never heard that term before, however, I believe that may be the
key!!

Thanks tremendously,
Todd

 

[John B. Matthews]

Patricia,

I had never heard that term before, however, I believe that may be the
key!!

Thanks tremendously,
Todd

This is a worthy pursuit, but you might also consider getBounds2D() or
contains() in the Shape interface. Polygon is a particularly convenient
implementation.

John

 

[Patricia Shanahan]

This is a worthy pursuit, but you might also consider getBounds2D() or
contains() in the Shape interface. Polygon is a particularly convenient
implementation.

getBounds2D() returns a Rectangle2D. The convex hull is usually not
rectangular. Todd should look at both and decide whether either is what
is really needed.

Patricia

 

[Todd]

getBounds2D() returns a Rectangle2D. The convex hull is usually not
rectangular. Todd should look at both and decide whether either is what
is really needed.

Patricia

Patricia,

You are correct, I need a more tightly-fit boundary. So far, my
research
on the convex hull indicates that for open shapes like the letter C or
U
will result in boundary points closing the opening of shape.

Are you familiar with any algorithms that do not close the openings?

Thanks,
Todd

 

[John B. Matthews]

Patricia,

You are correct, I need a more tightly-fit boundary. So far, my
research
on the convex hull indicates that for open shapes like the letter C or
U
will result in boundary points closing the opening of shape.

Are you familiar with any algorithms that do not close the openings?

Thanks,
Todd

You should consider contains(). Shape's definition of "insideness"
applies specifically to Polygon. The Polygon doesn't have to be convex,
but it is assumed to be simple and closed. Is your polygon is like a "U"
(open) or the outline of a "U" (closed).

John

 

[Todd]

I am again prompted to think that you need to define "boundary" better.

In particular, talking about "interior" points within a set of existing
points does in fact imply to me that a "convex hull" is what you wanted
(thanks to the others for teaching me a new term ). If you don't want
to close a shape like a C or a U, then how can you tell the difference
between points inside such a shape from points not inside such a shape?

By what criteria does an unordered collection of points that just happen
to have the shape of a C or a U wind up having a boundary that is defined
in such a way that the points are interpreted as the shape of a C or a U?
Other than the fact that it's a recognizable lexical pattern, what is it
about a C or a U that inherently defines the "boundary" in a way that
preserves the C or U shape? Or conversely, what is it about your
definition of "boundary" that allows you to distinguish a collection of
points as being a C rather than an O?

Pete

Pete,

Imagine a bubble-letter C or U, like the kind middle-school girls
draw. Now, imagine just taking a pen and filling the bubble-letter
with dots. Remove the bubble-letter border, leaving just the dots,
and you have the data set that I am starting with.

Visually, you can see the "edge" defined by where the points are
and where the points are not. This interface between have and
have not is what I am calling the boundary.

I am trying to create an algorithm that will locate those points
that are at the interface between have and have not. And then
use those points to create an approximation of the shape (imagine
a non-smooth bubble-letter). This closed polygon can then be
used to define those points which are inside and those points
which are not.

I don't feel like I have clarified my position very well.

Another example that I have just thought of is a bit more
abstract. Imagine you have a supply of rocks and a sling-shot.
You will be shooting the rocks into the air over a body of
water. When you hear a splash, you write down the angles
and strength of launch. Once you have launched a whole
bunch of rocks, you then convert the data to x and y and
plot the result. This would be an approximate map of the
body of water. Now, if there were a peninsula in the water,
there will be a void in the plot. You would be able to
see this. The shore of the water is the boundary of the
points and would define whether the rock is wet or not.

Again, not feeling like I am too clear, so let me know
if I need to try again.

Todd

 

[Todd]

You should consider contains(). Shape's definition of "insideness"
applies specifically to Polygon. The Polygon doesn't have to be convex,
but it is assumed to be simple and closed. Is your polygon is like a "U"
(open) or the outline of a "U" (closed).

John

John,

I am trying to find an algorithm to develop the closed outline
tight around a set of points, i.e., where shrink-wrap would
close around the points. From that small set of points touching
the shrink-wrap, the closed outline of the polygon will be defined.
Then contains() will be exactly what I am looking to use.

Todd

 

[Patricia Shanahan]

Todd wrote:
....

Another example that I have just thought of is a bit more
abstract. Imagine you have a supply of rocks and a sling-shot.
You will be shooting the rocks into the air over a body of
water. When you hear a splash, you write down the angles
and strength of launch. Once you have launched a whole
bunch of rocks, you then convert the data to x and y and
plot the result. This would be an approximate map of the
body of water. Now, if there were a peninsula in the water,
there will be a void in the plot. You would be able to
see this. The shore of the water is the boundary of the
points and would define whether the rock is wet or not.

This reminds me of a problem in machine learning, cluster detection. In
that model, you have a training data set (splash, no-splash for some
coordinates). You need to estimate whether a new point is in the splash
cluster or the no-splash cluster.

Patricia

 

[Daniel Pitts]

Pete, and others,

I was concerned that I was unclear, but somewhat uncertain as to how
to be more so.

I am not concerned about there being a smooth, curved boundary to any
set of points. I am content to work with a shape defined by the
points that are the farthest from any given location (for simplicity,
imagine the center) within the cluster of data points. These maximal
points define what I would call the boundary of the shape and the
shape would be a connect-the-dots type shape.

Is that any clearer?

Todd

I don't think there is a built-in library to do what you want. I suggest
posting this question in comp.graphics.algorithms, it seems more
appropriate for this kind of question.

 

[Daniel Pitts]

Pete,

Imagine a bubble-letter C or U, like the kind middle-school girls
draw. Now, imagine just taking a pen and filling the bubble-letter
with dots. Remove the bubble-letter border, leaving just the dots,
and you have the data set that I am starting with.

Visually, you can see the "edge" defined by where the points are
and where the points are not. This interface between have and
have not is what I am calling the boundary.

I am trying to create an algorithm that will locate those points
that are at the interface between have and have not. And then
use those points to create an approximation of the shape (imagine
a non-smooth bubble-letter). This closed polygon can then be
used to define those points which are inside and those points
which are not.

I don't feel like I have clarified my position very well.

Another example that I have just thought of is a bit more
abstract. Imagine you have a supply of rocks and a sling-shot.
You will be shooting the rocks into the air over a body of
water. When you hear a splash, you write down the angles
and strength of launch. Once you have launched a whole
bunch of rocks, you then convert the data to x and y and
plot the result. This would be an approximate map of the
body of water. Now, if there were a peninsula in the water,
there will be a void in the plot. You would be able to
see this. The shore of the water is the boundary of the
points and would define whether the rock is wet or not.

Again, not feeling like I am too clear, so let me know
if I need to try again.

Todd

Ah, at this point it sounds like you're dealing with more
pattern-recognition type of problems, and more appropriate to an A.I.
newsgroup or fuzzy-logic.

Good luck.

 

[Arved Sandstrom]

Imagine a bubble-letter C or U, like the kind middle-school girls
draw. Now, imagine just taking a pen and filling the bubble-letter
with dots. Remove the bubble-letter border, leaving just the dots,
and you have the data set that I am starting with.

Visually, you can see the "edge" defined by where the points are
and where the points are not. This interface between have and
have not is what I am calling the boundary. [...]

If I understand the question correctly, what you're looking for is a lot
harder than the convex hull mentioned earlier.

Ignoring for the moment all of the additional complexities that surely
will come up, it seems like the basic criteria is of "dot density".

[ SNIP ]

I tend to agree. One crude approach is to simply divide the area in question
into subareas, perhaps tiling with triangles or hexagons, and define a
polygon as being part of the shape if it contains enough points.

Another similar approach is to triangulate the point set, perhaps with a
Delaunay triangulation (the advantage of this being that there are
well-known algorithms for it, not to mention quite a few libraries). You
could then apply an area criterion to each triangle to see if it belongs to
the shape.

AHS

 

[i.dont.need]

I have a bunch of points (defined in 2-D space, i.e., x-y coordinates)
that have a well-defined range that is easy to determine visually. I
need to determine the boundary of the input set of points and then
later test if a new point falls inside or outside of the boundary.

Do you have to do this for a single point set, or do you have to deal
with an arbitrary number? If it's just a one-off, can you handle some
human intervention? Some of the boundary points are easy to identify:
construct a Voronoi tessellation, and all points inside infinite cells
are on the boundary. The others are tougher. A person could tease out
some data from a conforming Delaunay triangulation, but I can't think of
an algorithmic technique. If precision isn't too important, one could
adopt a GIS perspective: buffer all inputs, then union the resulting
circles together to form a polyline containing all inputs, but somewhat
larger in area (islands would still be a problem). As others have
indicated, a graphics group might have some techniques. No answers, but
ideas in any case...

 

[Tom Anderson]

I am trying to find an algorithm to develop the closed outline tight
around a set of points, i.e., where shrink-wrap would close around the
points. From that small set of points touching the shrink-wrap, the
closed outline of the polygon will be defined. Then contains() will be
exactly what I am looking to use.

Shrink-wrap does not work that way.

As others have pointed out, althought what you want is intuitively quite
simple, i think it's formally not well-defined. That's not to say you
can't define it, but you need to think about it a bit more. Try giving a
formal mathematical-sounding description of what you want - a description
precise enough that it could be used to decide whether a given polygon
enclosing the points is what you want or not. Then, you might be able to
come up with an algorithm to construct such a polygon.

Now, although what you want is not shrink-wrapping, it is quite like
vacuum packing. A convex hull is the shortest line that encloses a set of
points: a physical analogy is that you're wrapping your points with an
elastic band, and, being elastic, its energy is minimised when its length
is minimised. You can continue the physical analogy for vacuum packing:
the energy is the sum of the tension energy in the membrane and the
pressure energy in the interior (or of the surrounding space pressing
against the interior, anyway). Skipping over the physical details, you
could define a constant k, in length units, and say that for a bounding
polygon with perimeter p and area a, the 'energy' is kp + a, and then work
out how to minimise that. I can't think of an algorithm off the top of my
head, but it should be fairly simple to do iteratively: start with the
convex hull, then at each line, try pushing it in to meet a point further
in; if it reduces the total energy, keep the change, otherwise try
something else. Of course, you have to make sure that the perimeter still
encloses all the points, which you can do by making sure that the
triangles where you do the pushing-in do not contain any of the points.

Another thing you might try is computing the Minkowski sum of the point
set with a circle of some size, and then taking the perimeter of the
connected area.

But seriously, ask an algorithms newsgroup!

tom

 

[John B. Matthews]

Imagine a bubble-letter C or U, like the kind middle-school girls
draw. Now, imagine just taking a pen and filling the bubble-letter
with dots. Remove the bubble-letter border, leaving just the dots,
and you have the data set that I am starting with.

Visually, you can see the "edge" defined by where the points are
and where the points are not. This interface between have and
have not is what I am calling the boundary.

I am trying to create an algorithm that will locate those points
that are at the interface between have and have not. And then
use those points to create an approximation of the shape (imagine
a non-smooth bubble-letter). This closed polygon can then be
used to define those points which are inside and those points
which are not.

[...]

Ah, you need to find the points defining the outline of a raster. The
outline is simple and closed but not necessarily convex. You might look
at the wand tool in ImageJ <http://rsb.info.nih.gov/ij/>.

Once you get the hull, contains() works correctly even for a non-convex
Shape. In the example below, outline is the implicitly closed, simple,
non-convex polygonal boundary of a "U".

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Polygon;
import java.awt.Shape;
import java.awt.geom.AffineTransform;
import javax.swing.JFrame;

/**
* Test Shape.contains
* @author John B. Matthews
*/
public class Contains extends JFrame {

private static Shape outline = initPoly();
private static AffineTransform at = new AffineTransform();

public static void main(String args[]) {
JFrame frame = new Contains();
frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
frame.setSize(400, 400);
frame.setVisible(true);
}

public void paint(Graphics g) {
Graphics2D g2D = (Graphics2D) g;
g2D.setBackground(Color.WHITE);
g2D.clearRect(0, 0, 400, 400);
g2D.setPaint(Color.BLACK);
g2D.drawLine(0, 200, 400, 200);
g2D.drawLine(200, 0, 200, 400);
g2D.setPaint(Color.BLUE);
drawShape(g2D, 200, 200);
}

/** Draw a scaled and translated outline. */
private void drawShape(Graphics2D g2D, int x, int y) {
at.setToIdentity();
at.translate(x, y);
at.scale(30, 50);
Shape shape = at.createTransformedShape(outline);
g2D.fill(shape);
System.out.println("Inside(" + (x + 1) + ", " + (y + 1) + ") "
+ shape.contains(x + 1, y + 1));
System.out.println("Inside(" + (x - 1) + ", " + (y - 1) + ") "
+ shape.contains(x - 1, y - 1));
}

/** Create a U shaped outline. */
private static Polygon initPoly()
{
Polygon poly = new Polygon();
poly.addPoint( 1, 0);
poly.addPoint( 1, -2);
poly.addPoint( 2, -2);
poly.addPoint( 2, 1);
poly.addPoint(-2, 1);
poly.addPoint(-2, -2);
poly.addPoint(-1, -2);
poly.addPoint(-1, 0);
return poly;
}
}

John

 

[Tom Anderson]

Tom Anderson wrote:
...

I think that is the second step. The first step is to really think
through the problem definition. Is it cluster detection? Is it vacuum
wrap?

I disagree, actually. I'd tell the algorithm wizards about my problem, and
see if they know anything which fits. Starting with a strict formal
definition means risking ruling out some algorithms which would do a
slightly different but equally useful job.

Look at it this way: his requirement is to convert a set of points to an
outline. That's it. That really is the entire requirement. Anything more
formal than that has to include arbitrary assumptions.

tom

 

[Todd]

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