Skip to main content
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index] [List Home]
Re: [jts-dev] point-in-polygon algorithm using voronoi & point nearest-neighbor
I worked my way into this algorithm by thinking... if I could represent a polygon by a series of points such that I only need to find the nearest point to a query point (to test is it "inside" or not), then how might I do this?  And I imagined, opposite each side of an edge/line of the polygon an opposing point equi-distant such that the edge/line completely divides the space between the points.  As I did this on some paper, it occurred to me that I was building something much like a Voronoi diagram, at least it looked like one.  Maybe it isn't completely.

On Fri, Apr 15, 2016 at 2:56 PM Martin Davis <mtnclimb@xxxxxxxxx> wrote:
I think you'd need a LINE Voronoi of the polygon - which is much harder  to compute than the point Voronoi (harder = code complexity, robustness).

But I may be missing something - I don't understand what are the "points opposing each side".

On Fri, Apr 15, 2016 at 11:51 AM, David Smiley <david.w.smiley@xxxxxxxxx> wrote:
Hello,

For whatever reason, I was thinking about point-in-polygon, and doing so quickly.  It occurred to me (and I am not the first to make this observation!) that one could pre-compute a Voronoi set of points for the polygon (including the points opposing each side -- "outside" voronoi points), then index those points into some simple spatial index.  At query time you query the spatial index by point to find the closest point.  If it's an inside point then it's in the poly, if its an outside point then it isn't.  Does that make sense?  Might that be faster than whatever JTS is doing now with a PreparedPolygon?  And AFAICT, I only need the triangles/points associated with edges of the polygon, not with the inside ones I sometimes see in Voronoi diagrams.

~ David
--
Lucene/Solr Search Committer, Consultant, Developer, Author, Speaker

_______________________________________________
jts-dev mailing list
jts-dev@xxxxxxxxxxxxxxxx
To change your delivery options, retrieve your password, or unsubscribe from this list, visit
https://www.locationtech.org/mailman/listinfo/jts-dev


_______________________________________________
jts-dev mailing list
jts-dev@xxxxxxxxxxxxxxxx
To change your delivery options, retrieve your password, or unsubscribe from this list, visit
https://www.locationtech.org/mailman/listinfo/jts-dev
--
Lucene/Solr Search Committer, Consultant, Developer, Author, Speaker

Back to the top