Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
1–7 of 7 posts
Re: Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
#22015
Re: Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
#32015
Added. Thanks!
Re: Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
#4I'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.
Re: Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
#5I'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...
Re: Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
#6I'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.
Re: Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)
#7I'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 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.