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.
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.
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.
6 comments
[ 31.0 ms ] story [ 774 ms ] threadIt'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...
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.