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

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

Pete

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.

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

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

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

In article 
<9ba81c26-151b-42f0-99c5-a214dafac09b@r66g2000hsg.googlegroups.com>,
 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

John B. Matthews wrote:
> In article 
> <9ba81c26-151b-42f0-99c5-a214dafac09b@r66g2000hsg.googlegroups.com>,
>  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

On Jun 5, 3:14 pm, Patricia Shanahan <p...@acm.org> wrote:
> John B. Matthews wrote:
> > In article
> > <9ba81c26-151b-42f0-99c5-a214dafac...@r66g2000hsg.googlegroups.com>,
> >  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

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

In article 
<7009b179-1518-40e3-8582-81c5c5069c42@m73g2000hsh.googlegroups.com>,
 Todd <todd.heidenthal@lmco.com> wrote:

> On Jun 5, 3:14 pm, Patricia Shanahan <p...@acm.org> wrote:
> > John B. Matthews wrote:
> > > In article
> > > <9ba81c26-151b-42f0-99c5-a214dafac...@r66g2000hsg.googlegroups.com>,
> > >  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

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

On Jun 5, 6:01 pm, "John B. Matthews" <nos...@nospam.com> wrote:
> In article
> <7009b179-1518-40e3-8582-81c5c5069...@m73g2000hsh.googlegroups.com>,
>
>
>
>  Todd <todd.heident...@lmco.com> wrote:
> > On Jun 5, 3:14 pm, Patricia Shanahan <p...@acm.org> wrote:
> > > John B. Matthews wrote:
> > > > In article
> > > > <9ba81c26-151b-42f0-99c5-a214dafac...@r66g2000hsg.googlegroups.com>,
> > > >  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

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

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

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

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

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

"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 

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

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

-- 
Shit bitches, you know how I swang. I gets my cinna-on at the
Cinna-bon. -- K-Real

In article 
<bf4643d7-36a9-4d1c-bd2d-11de84344805@25g2000hsx.googlegroups.com>,
 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();
        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
-- 
John B. Matthews
trashgod at gmail dot com
home dot woh dot rr dot com slash jbmatthews

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

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

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 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
illustrate what I see as an inadequacy of your informal notion,
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

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? 

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

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))
        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)); } }
  }
}

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

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

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

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