Deterministic algorithm to determine whether a point is in a polygon

[seangransee]

I haven't gotten a chance to spend much time with this, but I've dropped in the algorithm I'm using in my application to replace Polygon.contains?.

There's one failing test, which is the check for a point being on the edge of a convex polygon. As stated in the section Point on a (Boundary) Edge from the algorithm's source page, this algorithm isn't able to predict when a point is exactly on the edge of a polygon. Perhaps a hybrid of this new algorithm with your current algorithm will do the trick.

Feel free to mess around with this and push commits to my branch.

[seangransee]

I made an additional change to go back to the way you were originally checking whether a point was on a boundary. When a point is not on a boundary, it uses the deterministic algorithm I found as a replacement for intersection_count(choose_good_ray).odd?.

All tests in contains_point_test.rb pass now.

[DanielVartanov]

Thanks @seangransee! Will look into it tomorrow :+1:

[DanielVartanov]

Status update: still trying to figure out the idea of the algo author.

From the description, I conclude that it is the same algorithm as the current one in this gem, but instead of a random ray they choose a horizontal positively-oriented ray, the rest is the same (they just calculate whether the number of intersections with edges is odd or even).

If I understood everything correctly, why would it work well with edge-cases when the semi-infinite ray contains a vertex or a whole edge? @seangransee, can you please help me to understand? I'd really appreciate assistance as it would save me a lot of time digging/drawing/testing/thinking.