[jts-dev] point-in-polygon algorithm using voronoi & point nearest-neigh

[David Smiley <david.w.smiley@xxxxxxxxx>]

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

LinkedIn: http://linkedin.com/in/davidwsmiley | Book: http://www.solrenterprisesearchserver.com