Sporadic inverted and degenerate polygons from varying intersection recursion paths

[benguild]

When performing recursive polygon intersections, we occasionally encounter two types of anomalous results:

1. Inverted polygons - Area > 2π sr (hemisphere), sometimes exactly 4π sr (full sphere)
2. Degenerate polygons - Area < 1e-15 sr (effectively zero-area computational artifacts)

At first, I thought this was a memory management issue, but we can't find any issue there. This behavior appears non-deterministic or path-dependent …the same geometric inputs can produce either valid results or these anomalies depending on prior operations or recursion paths taken. In other words, if these operations are retried via a different recursion path, they do not occur.

It could be related to snapping behavior (rounding/randomness?) or some unknown internal state, but we're only working with "Clone(s)" of each polygon in any case prior to any operation, so there should not be any conflicts, races, or deallocations… unless it's something I haven't caught in the documentation yet.

Is this expected behavior when operating at higher precisions? Retrying the operations is doable, but I'm concerned that it may be masking something else that's going on, and that is not fully understood. I tried to put together example code, but whenever I try the same geometries in an isolated instance, it does work consistently… which is really a head scratcher.

Our workflow involves:

• Creating MutableS2ShapeIndex for each polygon via index->Add(shape)
• Immediately using these indexes in S2BooleanOperation::Build(*a->index, *b->index)
• Polygon cloning thereafter
• Each clone gets a fresh index (that's used immediately)

Since MutableS2ShapeIndex uses lazy batch updates for performance, I'm suspecting there could be an issue in this implementation/approach. But, any thoughts would be appreciated. If not, we could investigate further or consider an alternative mitigation/revision.

[jmr]

Can you make a test that reproduces this? Even if it only fails 1/10k times, that would still help.

Without that, I don't think we'll be able to help much.

You can try adding CHECKs and/or logging to your code to catch when something is going wrong.

[benguild]

Let me see if I can come up with something, I'm keeping it in mind. 💭

[benguild]

The only time I was able to reproduce this aside from what's covered in #475 also included a use of S2Polygon which is considered obsolete, so I opened a PR #473 to suggest highlighting further in the documentation that folks avoid older types at this point. If I can reproduce this in some other way, I'll review and reopen.