robust-predicates

If you find this interesting, you might enjoy my write up of the Matoušek-Sharir-Welzl (MSW) algorithm used by D3’s circle-packing layout. https://observablehq.com/@d3/d3-packenclose I still haven’t quite figured out how to make D3’s implementation robust, though. Volodymyr Agafonkin’s robust-predicated would probably help… https://github.com/mourner/robust-predicates

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 t