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


Back to the top