Polygon intersection fails with "Given edges do not form loops (indegree != outdegree)"

[mskd12]

I encountered an error when intersecting two polygons, say p1 and p2. At a high level, I am starting with several polygons formed with MakeRegularLoop like below and then applying several boolean operations between them (intersection, difference).

S2Polygon* s1, s2, s3, ... = new S2Polygon(S2Loop::MakeRegularLoop(center, vertex, NUM_VERTICES) // create several polygons like these

if (p1->Intersects(p2)) { // p1 and p2 are the product of several boolean operations between the starting polygons
           cout << p1->isValid() << " " << p2-> isValid(); // checks succeed
           S2Polygon* intersecting = new S2Polygon();
           intersecting->InitToIntersection(p1, p2); // this line fails for a specific p1, p2
}

The error message is: FATAL INTERSECTION operation failed: Given edges do not form loops (indegree != outdegree)Aborted (core dumped) coming from s2builder_graph.cc:301.

Couple of important points to note:

1. Both the polygons p1 and p2 have only one loop. I also added a check to ensure that the polygons are valid.

2. The error is occuring only when the polygons have many vertices. It happens when NUM_VERTICES = 200 above but doesn't if it is 150.

3. The error also occurs only when I set the boolean operaton option PolygonModel::CLOSED (which is required for my usecase).

I have been trying to think of what's the best way to encode the two polygons so that someone else can reproduce the error. I can provide the list of vertices, but as the error is occuring only when the polygons have many vertices, I thought it might not be ideal. Any ideas on how to encode the polygon in a better way?

[jmr]

Just make a self-contained example and put it here or in a gist. 200 vertices is fine.

[mskd12]

I used s2textformat helper functions to print out the two polygons. Quite unexpectedly, I am unable to reproduce the intersection error upon reading the polygons back. Any thoughts on what might be lost when you run a polygon through s = s2textformat::ToString(p) followed by s2textformat::MakePolygonOrDie(s)? I don't think it is a precision issue as I increased the output precision of doubles to its maximum.

[jmr]

Can you reproduce the bug if you use S2Polygon::Encode/Decode? If so, attach binary files of the encoded polygons.

[mskd12]

Hey Jesse, I tried using Encode/Decode but was unable to reproduce the bug. I also just noticed something surprising about the bug: I included a P1.intersects(P2) call right before the InitToIntersection call. The former succeeds while the latter doesn't.

[jmr]

So you're saying if you call InitToIntersection, it fails, but if you Encode/Decode the polygons first, it works? Sounds like you might have some memory issues. Try running with msan/asan/ubsan. If that doesn't find it, there must be some way to make a self-contained test case.

[jmr]

Do you have a test case for this?

[mskd12]

I was unable to generate a test case for this. Running with msan / asan / ubsan did not help either.. Currently this is a bit low-priority for me, so I am not planning to spend more time on this. Feel free to close this issue..