search

google / s2geometry

Computational geometry and spatial indexing on the sphere
http://s2geometry.io/
Apache License 2.0
2.29k stars 302 forks source link

loop.Normalize() not working as expected? #369

Open paro- opened 2 months ago

paro- commented 2 months ago

Hi,

I've got this loop that I'm not sure Normalize() works as expected on (sorry, it's huge).

At the end of the snippet there are instructions to build the loop and with the questions. The script was run by building a recent s2geometry (0.11.0) and pip installing it.

Note that with the simple pip install s2geometry (0.9.0) it works as expected (areas are equal).

loop

Thank you for your time, Best regards, Paul

smcallis commented 2 months ago

I'm not sure who maintains the pip build of S2 (it's not us). You'll likely have to ask there :(

paro- commented 2 months ago

Even regardless of the diff between the pip build (0.9.0) and github (0.11.1), do you confirm that github results are as expected? Is it normal to find an area diff between a loop and its reverse when they're both normalized? For the record I'm running this on hundreds of loops and the diff only rarely shows. And this is actually why I'm computing the reverse loops in the first place, it's because I can't trust Normalize() to yield loops that are all on the same orientation, so I compute loop & reverse loop and select the one with the smallest area, but it's slow... Good day, Paul

smcallis commented 2 months ago

Our bindings don't even expose S2Loop so I can't test directly. If you can reproduce in C++ I can debug it though.

paro- commented 2 months ago

I found a more manageable example (with 2k vertices instead of 12k), you can slap this example in the test suite to investigate. Thank you for your time, Paul

paro- commented 2 months ago

FYI I git checkout a4dddf4, when the fork happened, and at that commit the test passes (the GetRectBound().Area() match, if that is indeed to be expected).

smcallis commented 1 month ago

Sorry for the delay but I dug into this further. The problem is the loop has duplicate vertices at the start and end (you don't have to close them manually). Having those duplicate vertices breaks the containment check which determines whether the loop contains S2::Origin() or not. If I remove them it seems to work fine.

If you don't know the provenance of your loops, then either running them through S2Builder to make them valid or checking with IsValid is advisable:

E0722 08:37:30.493461 2250940 s2loop.cc:168] Edge 1 is degenerate (duplicate vertex)

paro- commented 1 month ago

Ok thank you for your help, will try to use S2Builder or remove the start & end vertices. Closing this atm, will reopen if tests don't prove successful. Good day, Paul