3 ms·
Howdy, I work on S2 [1] so I have questions! How do you deal with polygons that cross the antimeridian? The indexing structure you've come up with seems very
by s2mcallis 3y ago
Howdy, I work on S2 [1] so I have questions! How do you deal with polygons that cross the antimeridian?
The indexing structure you've come up with seems very interesting. In spherical coordinates line sweep algorithms like that are a little less intuitive because there's not really a min and max y value to work with. Does your index support multiple polygons indexed together?
The lack of exact predicates worries me a little bit. It's tricky because it will work right until it doesn't for mysterious reasons, and it's very hard to test for if you haven't built it on a foundation of exact predicates. You'll periodically fall into the fractal foam around edges when testing if you cross them or not ([2] has some good pictures). We do this in S2 by relying on a set of predicates [3] that fall all the way back to symbolic perturbation if they have to. We simply don't have to think about colinear points in S2 for that reason.
[1] https://s2geometry.io/ https://s2geometry.io/
[2] https://github.com/mourner/robust-predicates https://github.com/mourner/robust-predicates
[3] https://github.com/google/s2geometry/blob/master/src/s2/s2predicates.h https://github.com/google/s2geometry/blob/master/src/s2/s2pr...
- tidwall 3y agoTG isn't spherical and wasn't designed to be. It's 2D and projection agnostic. Crossing the antimeridian is a user problem to solve. I recommend following the GeoJSON rule of antimeridian cutting [1]. As I said in the README. My goals are fast point-in-polygon, geometry intersections, and low memory footprint. Those are my bread-and-butter. From what I know about S2, it has different goals. Such as being spherical and using discrete cells for distributed spatial indexes. Those are great things of course, but not really what I need. This is the second comment that recommends using Shewchuk’s methods. And while yes I agree that that may be a superior way to go, and always on the table for the future, I'm still able to achieve my goals without those methods. At least for now. [1] https://datatracker.ietf.org/doc/html/rfc7946#section-3.1.9 https://datatracker.ietf.org/doc/html/rfc7946#section-3.1.9
- s2mcallis 3y agoYeah we're spherical mostly because working in spherical coordinates let's you not have to worry about the projection. S2Cells are really just nodes in a quadtree, the difference being our quad tree is implicit, you can (and we do) store them in a linear array in memory.