Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
hamberg.noI'm laughing a bit at myself after reading his algorithm for determining if a point is inside a polygon. I've known this for 40+ years, but I implemented this for the US by breaking down into triangles first. I have bounding boxes on my states and triangles, so it is probably faster, but unnecessarily so.
On a side note, this is why geometry operations (and particularly reprojections/etc) are sometimes best treated like cryptography: "don't roll your own, use a library".
It's not an absolute, by any means, but a GEOS/etc dependency is often well worth the pain of getting spatial operations correct.
That having been said, I've made very similar mistakes embarrassingly recently...
GEOS is very feature-reach but slow. Mostly because it is a to-the-book port of a Java library and thus allocates and pointer-chases like crazy. By rolling your own implementations of key algorithms you can reap substantial performance benefits.
GEOS was hardly an example of bug-free code.
Maybe it's gotten better, but, back when I looked at it, it failed on all manner of corner cases and started bogging down pretty badly on anything more than a couple hundred elements.
2015
Added. Thanks!