Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)

Fast, Offline, Reverse Geocoding; Or, in Which Polygon Am I? (2015)(hamberg.no)

64 points by ehamberg 6 years ago | 6 comments

LanceH 6 years ago |

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 6 years ago | |

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 6 years ago | | |

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 6 years ago | | |

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.

aw3c2 6 years ago |

2015

dang 6 years ago | |

Added. Thanks!