[LanceH]

I'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.

[jofer]

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...

[dunkelheit]

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.

[bsder]

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.