0
$\begingroup$

I have an array of polygons which are arrays of points. There are no gaps and none of them overlap like a Voronoi diagram.

Unlike a Voronoi diagram I cannot simply find the nearest centroid to select a polygon, this returns the correct polygon most of the time but sometimes the point lies within a neighboring polygon.

The developer tools in my chrome browser seem to be able to do it with the selection tool but I have no idea how it is doing it.

$\endgroup$
  • $\begingroup$ Perhaps it's just iterating over the entire array. $\endgroup$ – Yuval Filmus Sep 6 at 13:26
2
$\begingroup$

I would use a winding number algorithm. There are a few, but the fastest goes like this:Imagine a line from your point along the positive x-axis. Now, for every edge of your polygon, determine if it crosses this line. if it crosses the line from below to above, then increment the winding number (which is initially zero), if it crosses going from above to below then decrement. If the winding number is zero, then the point lies outside of the polygon, otherwise it lies inside.

You probably don't want to test every polygon every time the point moves, so I would pre-compute a bounding box or sphere for every polygon. I would then only test winding numbers against those polygons whose bounding shapes collide with the point in question.

Hope this helped. Good luck!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.