Thanks!

It just keeps amazing me that apparently no one else (also on the various polygon/point intersection algorithms on GitHub) thought of actually accelerating the query for the edges that could possibly intersect the ray in that raycast algorithm...

It is simple after all. I implemented the interval tree after reading once about it on the Wikipedia site. Nothing fancy in there, actually.

Handling holes is also easy with this approach:

Just check whether the point is inside the polygon of a hole. This can also be very efficiently implemented by first testing whether the point intersects the bounding sphere/rectangle of the hole, like with doing a normal polygon/point intersection.

If it is in the hole and also in the outer polygon, then -> no intersection.

And because the algorithm is damn fast, we can throw hundreds and even thousands of holes and polygons at it without it even batting an eyelash. Having drawn a 6781 vertices polygon and measuring with System.nanoTime() the query time, it was 0.004 milliseconds..., so just 4 microseconds.

But that OS X issue is strange. I took the latest oss.sonatype.org deployments with Maven.

EDIT: Improved the performance of the tree traversal again by 10%: Before descending into the left child of the interval tree, check if it actually contains an interval whose maximum value is at least the queried 'y' (that maximum value is cached during tree construction).

Likewise for the right child, check if it contains an interval whose minimum value is at most 'y'.

A 1,048,576 vertices polygon can now be queried around 4,664,358 times per second when all query points lie within the polygon.