How to find the outer points in a group?

classic Classic list List threaded Threaded
2 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

How to find the outer points in a group?

Jeff Adams-4
I have a bunch of semi-random points, but they're all "nearby" each other.  I'd like to somehow get the list of only the "outside" points (I.E. if you were going to draw a polygon that contained all the points, which points would be the vertices).

Then, just to make it fun, I actually have a maximum number of points that I want (I.E. no more than 25 points).  I am willing to lose a few points from within the polygon if it is necessary to keep the number of points in the outline below the max.

For example, if I had 100 points in a pseudo circle, that would be the worst case scenario because there is no way to draw a polygon with less than the full 100 without "losing" (being outside the outline) points.  But that's OK for my purposes because the points are going to tend to be in rectangular clouds so I won't lose very many in practice.

My current idea is to somehow draw the outline as a polygon, but then just simplify with larger and larger simplify distances until the number of vertices is below my max, then use the list of vertices as my list of "outline" points.

But how do I draw the outline polygon in the first place?

--
Jeff Adams
Avencia, Inc.
215-701-7717

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

Re: How to find the outer points in a group?

Martin Davis
The simplest way to construct a polygon enclosing a set of points is to
comnpute the convex hull (Geometry.convexHull).  If you need a
non-convex shape there are various ways to do this (alpha shapes,
concave hulls, etc) but JTS currently doesn't provide this.

I've often thought it would be nice to be able to use number of points
as a simplification criteria, as opposed to distance. I think this is a
minor extension to the current algorithm - just have to find the time to
do this.

Also, I'd like to provide an "outer simplification" option, which will
simplify a polygon in such a way that the original vertices are always
contained within the simplified boundary.  Some day...

Jeff Adams wrote:

> I have a bunch of semi-random points, but they're all "nearby" each
> other.  I'd like to somehow get the list of only the "outside" points
> (I.E. if you were going to draw a polygon that contained all the
> points, which points would be the vertices).
>
> Then, just to make it fun, I actually have a maximum number of points
> that I want (I.E. no more than 25 points).  I am willing to lose a few
> points from within the polygon if it is necessary to keep the number
> of points in the outline below the max.
>
> For example, if I had 100 points in a pseudo circle, that would be the
> worst case scenario because there is no way to draw a polygon with
> less than the full 100 without "losing" (being outside the outline)
> points.  But that's OK for my purposes because the points are going to
> tend to be in rectangular clouds so I won't lose very many in practice.
>
> My current idea is to somehow draw the outline as a polygon, but then
> just simplify with larger and larger simplify distances until the
> number of vertices is below my max, then use the list of vertices as
> my list of "outline" points.
>
> But how do I draw the outline polygon in the first place?
>
> --
> Jeff Adams
> Avencia, Inc.
> 215-701-7717
> ------------------------------------------------------------------------
>
> _______________________________________________
> jts-devel mailing list
> [hidden email]
> http://lists.refractions.net/mailman/listinfo/jts-devel
>  

--
Martin Davis
Senior Technical Architect
Refractions Research, Inc.
(250) 383-3022

_______________________________________________
jts-devel mailing list
[hidden email]
http://lists.refractions.net/mailman/listinfo/jts-devel
Loading...