4 ms·
Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
- aw3c2 7y ago2015
- dang 7y agoAdded. Thanks!
- LanceH 7y agoI'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 7y agoOn 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 7y agoGEOS 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 7y agoGEOS 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.