3 ms·
"Complicated S2?" That's surprising, the S2 library (https://github.com/google/s2geometry https://github.com/google/s2geometry) seems really clean and fairly in
by mrdmnd 9y ago
"Complicated S2?" That's surprising, the S2 library (https://github.com/google/s2geometry https://github.com/google/s2geometry) seems really clean and fairly intuitive to me.
- gfrangakis 9y agoLibrary also available in Java[0] and to an extent in Golang[1], though the latter is incomplete. S2 is fantastic for geofencing. Arbitrary regions can be covered by a set of S2 cells of varying level. A point (lat/lon) can be converted to a S2 cell of the smallest level (around a cm^2 of area on the sphere). Checking to see if one S2 cell is contained in another amounts to searching an integer range, since all children of a given S2 cell have IDs that fall within a fixed ranged. See also [2] [0] https://github.com/google/s2-geometry-library-java https://github.com/google/s2-geometry-library-java [1] https://github.com/golang/geo https://github.com/golang/geo [2] http://blog.christianperone.com/2015/08/googles-s2-geometry-on-the-sphere-cells-and-hilbert-curve/ http://blog.christianperone.com/2015/08/googles-s2-geometry-...
- Mr_P 9y agoSeriously. S2 is just quadtrees over a cubemap, with a nice mapping from integers to cells. So, instead of using a quadtree (because it's "complicated"), they chose to make their own two-level tree requiring O(N) linear scans at both levels, as opposed to O(1) with a simple trick.
- bpicolo 9y agoS2 was much less well maintained (in the OSS release) when Uber wrote this. Even 4-5 months ago all that was available was a mirror from when google code hosting shut down - undocumented stuff. This repo is new (and great to see)