COMPGROUPS.NET | Search | Post Question | Groups | Stream | About | Register

### Creating a shape from a set of points

• Follow

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
 0
Reply todd.heidenthal (70) 6/5/2008 7:10:21 PM

On Thu, 05 Jun 2008 12:10:21 -0700, Todd <todd.heidenthal@lmco.com> wrote:

> 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?

Java does have a geometry package, and I would guess there's a good chance
it can be used to address your problem.  But it seems to me that you need
to do a better job defining "boundary" before your question can be

Pete
 0

Todd <todd.heidenthal@lmco.com> writes:
>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.

 0
Reply ram (2827) 6/5/2008 7:19:24 PM

Todd wrote:
> 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
 0
Reply pats (3215) 6/5/2008 7:21:00 PM

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
 0
Reply todd.heidenthal (70) 6/5/2008 7:22:51 PM

Todd wrote:
> 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?

It sounds like you want what's called the "convex hull"
of the set of points.  Google it, and/or try a newsgroup
with "graphics" in the title.

--
Eric.Sosman@sun.com
 0
Reply Eric.Sosman (4228) 6/5/2008 7:27:06 PM

On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
> Todd wrote:
> > 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

Patricia,

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

Thanks tremendously,
Todd
 0
Reply todd.heidenthal (70) 6/5/2008 7:28:56 PM

In article
Todd <todd.heidenthal@lmco.com> wrote:

> On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
> > Todd wrote:
> > > 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
>
> 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
--
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews
 0
Reply nospam21 (11322) 6/5/2008 8:58:22 PM

John B. Matthews wrote:
> In article
>  Todd <todd.heidenthal@lmco.com> wrote:
>
>> On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
>>> Todd wrote:
>>>> 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
>> 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.

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
 0
Reply pats (3215) 6/5/2008 9:14:19 PM

On Jun 5, 3:14 pm, Patricia Shanahan <p...@acm.org> wrote:
> John B. Matthews wrote:
> > In article
> >  Todd <todd.heident...@lmco.com> wrote:
>
> >> On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
> >>> Todd wrote:
> >>>> 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
> >> 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.
>
> 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
 0
Reply todd.heidenthal (70) 6/5/2008 11:06:04 PM

On Thu, 05 Jun 2008 16:06:04 -0700, Todd <todd.heidenthal@lmco.com> wrote:

> 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?

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
 0

In article
Todd <todd.heidenthal@lmco.com> wrote:

> On Jun 5, 3:14 pm, Patricia Shanahan <p...@acm.org> wrote:
> > John B. Matthews wrote:
> > > In article
> > >  Todd <todd.heident...@lmco.com> wrote:
> >
> > >> On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
> > >>> Todd wrote:
> > >>>> 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
> > >> 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.
> >
> > 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

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 B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews
 0
Reply nospam21 (11322) 6/6/2008 12:01:46 AM

On Jun 5, 5:24 pm, "Peter Duniho" <NpOeStPe...@nnowslpianmk.com>
wrote:
> On Thu, 05 Jun 2008 16:06:04 -0700, Todd <todd.heident...@lmco.com> wrote:
> > 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?
>
> 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
 0
Reply todd.heidenthal (70) 6/6/2008 1:11:20 AM

On Jun 5, 6:01 pm, "John B. Matthews" <nos...@nospam.com> wrote:
> In article
>
>
>
>  Todd <todd.heident...@lmco.com> wrote:
> > On Jun 5, 3:14 pm, Patricia Shanahan <p...@acm.org> wrote:
> > > John B. Matthews wrote:
> > > > In article
> > > >  Todd <todd.heident...@lmco.com> wrote:
>
> > > >> On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
> > > >>> Todd wrote:
> > > >>>> 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
> > > >> 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.
>
> > > 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
>
> 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 B. Matthews
> trashgod at gmail dot com
> home dot woh dot rr dot com slash jbmatthews

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
 0
Reply todd.heidenthal (70) 6/6/2008 1:14:44 AM

On Thu, 05 Jun 2008 18:11:20 -0700, Todd <todd.heidenthal@lmco.com> wrote:

> 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".

Using either of your examples, obviously there are infinitely many shapes
that can produce any given dot pattern.  So you must be expecting to be
making sort of estimate.  And I would guess that estimate will depend on
some threshold you define, where any point in space farther than that
threshold from any point in your collection of dots would be considered
"outside", while any other point would be "inside".

Does that sound right?

Unfortunately, I don't have any good suggestions off the top of my head,
but I suppose that, like "convex hull", the problem is a reasonably
well-known one in mathematics.  Maybe someone even knows the specific name
for it.  :)  I haven't run across anything actually part of Java that
would directly address the issue, though of course once you have a
solution, you could use the geometry classes to represent the results.  :)

One question is: what problem are you specifically trying to solve?  If
you just want to know whether some given point is "inside" versus
"outside", it may make more sense to just do a straight distance
comparison with your known points.  You can use some sort of grid or
quad-tree to organize the collection of points, so that you never have to
compare too many.  I think that wouldn't be too hard at all, and wouldn't
really require framework support.  Generating an actual polygonal shape
that describes the boundary is somewhat more complicated (as well as
subject to a variety of necessary assumption-making, given the "inifite
possibility" issue I mentioned above :) ).

A happy medium might be found by applying the simple solution (distance
comparison) to some sort of raster description of a region.  A true
geometrical solution would, I think, involve some kind of vector
representation.  But maybe a bitmap is sufficient for your purposes
(either for display or even for the "inside"/"outside" test).

Maybe someone else will have some ideas, or maybe something will occur to
me later.  :)

Pete
 0

On Thu, 05 Jun 2008 18:14:44 -0700, Todd <todd.heidenthal@lmco.com> wrote:

> 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.

That's not what you wrote elsewhere.

A "shrink-wrap" solution would be the convex hull.  Shrink-wrap only goes
so far, and the theoretical application of the idea would preclude the
shrink-wrap going into the interior of a C shape at all.  But you're
saying that you actually do what your boundary detection to take into
account hollow interiors like this.

I think you should be able to easily find a convex hull solution, as
suggested by others.  But based on your elaboration, I really don't think
that's what you want, nor do I think that describing the problem as
"shrink-wrap" correctly summarizes the problem as well.

Pete
 0

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
 0
Reply pats (3215) 6/6/2008 1:41:10 AM

Todd wrote:
> 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' Tech Blog: <http://virtualinfinity.net/wordpress/>
 0
Reply newsgroup.spamfilter (920) 6/6/2008 2:51:48 AM

Todd wrote:
> On Jun 5, 5:24 pm, "Peter Duniho" <NpOeStPe...@nnowslpianmk.com>
> wrote:
>> On Thu, 05 Jun 2008 16:06:04 -0700, Todd <todd.heident...@lmco.com> wrote:
>>> 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?
>> 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
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.

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
 0
Reply newsgroup.spamfilter (920) 6/6/2008 2:54:27 AM

"Peter Duniho" <NpOeStPeAdM@nnowslpianmk.com> wrote in message
news:op.ucazhxka8jd0ej@petes-computer.local...
> On Thu, 05 Jun 2008 18:11:20 -0700, Todd <todd.heidenthal@lmco.com> wrote:
>
>> 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

 0
Reply asandstrom (221) 6/6/2008 5:27:19 AM

Todd wrote:
>
> 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...

--
Shane
 0
Reply i.dont.need (6) 6/6/2008 6:08:50 AM

On Thu, 5 Jun 2008, Todd wrote:

>>  Todd <todd.heident...@lmco.com> wrote:
>>>>>  Todd <todd.heident...@lmco.com> wrote:
>>>>>
>>>>>> On Jun 5, 1:21 pm, Patricia Shanahan <p...@acm.org> wrote:
>>>>>>> Todd wrote:
>>>>>>>
>>>>>>>> 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.
>>>>>>>
>>>>>>> Are you looking for the convex hull? If so, I suggest a web search
>>>>>>> for that with the word "java".
>>>>>>
>>>>>> I had never heard that term before, however, I believe that may be the
>>>>>> key!!
>>>
>>> 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?
>
> 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
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

--
Shit bitches, you know how I swang. I gets my cinna-on at the
Cinna-bon. -- K-Real
 0
Reply twic (2083) 6/6/2008 11:24:45 AM

In article
Todd <todd.heidenthal@lmco.com> wrote:
[...]
> 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();
return poly;
}
}

John
--
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews
 0
Reply nospam21 (11322) 6/6/2008 11:24:54 AM

Tom Anderson wrote:
....
> But seriously, ask an algorithms newsgroup!

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?

Patricia
 0
Reply pats (3215) 6/6/2008 12:10:41 PM

On Fri, 6 Jun 2008, Patricia Shanahan wrote:

> Tom Anderson wrote:
> ...
>> But seriously, ask an algorithms newsgroup!
>
> 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

--
Shit bitches, you know how I swang. I gets my cinna-on at the
Cinna-bon. -- K-Real
 0
Reply twic (2083) 6/6/2008 2:22:28 PM

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
 0
Reply todd.heidenthal (70) 6/6/2008 2:24:10 PM

Todd wrote:
> On Jun 5, 5:24 pm, "Peter Duniho" <NpOeStPe...@nnowslpianmk.com>
> wrote:
>> [...]
>> I am again prompted to think that you need to define "boundary" better.
> [...]
> 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.
> [...]

I agree with Peter: You need to define "boundary."  To
let's consider a set of just three points, the vertices of an
equilateral triangle.  What "shape" should the algorithm detect?
Should it find the convex hull (the triangle itself), or should
it find something like the letter V?  In the latter case, which
of the three points should be the middle of the V, or equivalently,
which side should be "gapped" while the other two remain intact?

Now consider a four-point set, the corners of a square.
Should the algorithm decide that the shape is a square, or a
U, or two | side by side, or an L plus one stray point, or ...?

And so on.  For a general N-point set, I suspect there's an
extremely large number of candidate "shapes" that enclose all
the points, even if we consider only polygonal shapes.  You
need to develop some criterion that allows you to choose one
of these as the "best" shape, rejecting the weirdos.  There's
no point in searching for an algorithm until you know what you
want the algorithm to do.

--
Eric.Sosman@sun.com
 0
Reply Eric.Sosman (4228) 6/6/2008 2:56:37 PM

Todd wrote:
> 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?

 0
Reply oohiggins (266) 6/6/2008 7:01:25 PM

On Fri, 06 Jun 2008 12:01:25 -0700, Jeff Higgins <oohiggins@yahoo.com>
wrote:

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

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.  :)

Pete
 0

Peter Duniho wrote:
> Jeff Higgins wrote:
>
>> Now I'm wondering about a spiral shape,
>> something like a loosly coiled length of rope.
>> How to find the outline of the rope?
>
> 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))

for (int x = 0; x < 41; x++) {
for (int y = 0; y < 11; y++) {
for (int x = 0; x < 11; x++) {
for (int y = 11; y < 51; y++) {
for (int x = 0; x < 41; x++) {
for (int y = 51; y < 61; y++) {
}
}

 0
Reply oohiggins (266) 6/7/2008 1:34:20 AM

Todd schrieb:
> 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:
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
 0
Reply hoffmann (427) 6/7/2008 2:08:07 PM

On Sat, 7 Jun 2008, hoffmann@fho-emden.de wrote:

> Todd schrieb:
>
>> 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.
>
> maybe you can use alpha shapes:
> 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
 0
Reply twic (2083) 6/8/2008 11:50:45 AM

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

As I get more, I will let you know.

Todd
 0
Reply todd.heidenthal (70) 6/9/2008 6:28:44 PM

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
 0
Reply todd.heidenthal (70) 6/11/2008 6:27:29 PM

33 Replies
39 Views

4/20/2013 2:08:08 PM