I was searching for a good point-in-polygon algorithm. The most popular one for arbitrary concave and convex polygons without holes seems to be the “ray casting algorithm.”
It is excellently described on http://alienryderflex.com/polygon/.
Now this algorithm has a problem that it always linearly tests all polygon edges against the query point (which is really unnecessary) and when using polygons with many vertices (like even more than 256) it goes down on its knees.
I was searching for a better way to do point in polygon queries but couldn’t really find any. So I took that ray casting algorithm and simply extended it with an interval tree to dramatically reduce the number of polygon edges that need to be tested. Actually, only the edges that intersect the imaginary ray with the y co-ordinate of the query point are tested now.
The general idea was that the two y co-ordinates of a polygon edge would form an interval that the interval tree allows to query for very efficiently for a given point.
With that solution, a convex polygon with around 256,000 vertices can be tested against around 4,000,000 query points in about a second.
The runtime only really depends on the number of polygon edges that intersect a given horizontal line with a given y co-ordinate.
Now I’d like to ask for improvements to have a final version ready for JOML’s geometry framework.
The current source is here: https://raw.githubusercontent.com/JOML-CI/JOML/geometry/src/org/joml/PolygonPointIntersection.java
Especially bad is the allocations of the Interval and IntervalTree objects. Maybe someone has a nifty idea how to do that better and with good memory locality.