Infinite loop in RegionCoverer Interior Covering

[lukasbindreiter]

Hi,

I've just stumbled upon a case where RegionCoverer.InteriorCovering results in an infinite loop.

To be fair, the s2.Polygon in question isn't a valid polygon according to the restrictions:

• Loops may not cross, i.e. the boundary of a loop may not intersect
  both the interior and exterior of any other loop.
• Loops may not share edges, i.e. if a loop contains an edge AB, then
  no other loop may contain AB or BA.

since it consists of the same loop two times.

I still think this might be worth looking into - since an infinite loop is pretty dangerous to trigger in any case.

And it does work (even correctly) for the RegionCoverer.Covering variant.

Below is a fully reproducible example:

package main

import (
	"fmt"
	"github.com/golang/geo/s2"
)

func main() {
	// a closed-polygon, an area in mexico
	points := []s2.Point{
		s2.PointFromLatLng(s2.LatLngFromDegrees(20.15, -97.70)),
		s2.PointFromLatLng(s2.LatLngFromDegrees(19.72, -97.70)),
		s2.PointFromLatLng(s2.LatLngFromDegrees(19.72, -97.19)),
		s2.PointFromLatLng(s2.LatLngFromDegrees(20.15, -97.19)),
	}
	poly := s2.PolygonFromOrientedLoops([]*s2.Loop{s2.LoopFromPoints(points)})

	coverer := s2.RegionCoverer{MinLevel: 0, MaxLevel: 30, LevelMod: 1, MaxCells: 1}
	interiorCovering := coverer.InteriorCovering(poly) // works as intended
	fmt.Println(interiorCovering)                      // [4/023231102]

	// now let's try the same area again, but with two times the same loop
	// this happened for us when converting a GeoJSON multipolygon to a S2 polygon and we didn't validate the
	// non-overlapping constraint before

	multiPoly := s2.PolygonFromOrientedLoops([]*s2.Loop{s2.LoopFromPoints(points), s2.LoopFromPoints(points)})
	// the call below results in an infinite loop
	interiorCovering = coverer.InteriorCovering(multiPoly)
	fmt.Println(interiorCovering)
}

[lukasbindreiter]

One point I forgot to mention:

err := multiPoly.Validate() does catch the error as expected - the issue above appeared due to a bug resulting in one code-path not validating the geometry.

[jmr]

err := multiPoly.Validate() does catch the error as expected - the issue above appeared due to a bug resulting in one code-path not validating the geometry

Not validating is by design/mis-design and based on the C++.

We should probably have PolygonFromOrientedLoops also return an error and add a separate Must* version.

@flwyd

[alan-strohm]

err := multiPoly.Validate() does catch the error as expected - the issue above appeared due to a bug resulting in one code-path not validating the geometry

Not validating is by design/mis-design and based on the C++.

We should probably have PolygonFromOrientedLoops also return an error and add a separate Must* version.

@flwyd

So we're OK paying the cost for a Validate call on all PolygonFrom* calls? (NB: Validate still isn't fully implemented)

[jmr]

So we're OK paying the cost for a Validate call on all PolygonFrom* calls? (NB: Validate still isn't fully implemented)

There would be the Must version that skips validation and stern comments about when it can be used.

[flwyd]

Changing the constructors to return an error seems somewhat disruptive and awkward, particularly since there's also a Validate method, which suggests that one can construct and validate separately. If we add this for Polygon constructors we should probably take a holistic approach and add it to Poyline and Loop too. This wouldn't fully protect Polyline, though, since its type is just []Point, so one can construct a Polyline by casting. Polygon and Loop are structs with private fields, so there's some protection there. It also looks like these types aren't completely immutable; Polygon.Loops() and Loop.Vertices() return slices that could be modified by the caller, so having called Validate() once isn't a guarantee that the value will be forever valid.

S2Polygon in Java was ported with C++ DCHECK turned into Java assertions but commented out, so it's not currently validating on construction either. There are some other S2 Java classes that aren't currently validating but which should be; Torrey is working with some internal clients who are depending on the non-validating behavior.

I agree that we should avoid getting into an infinite loop, even if the polygon's invalid. Making it impossible to get an invalid polygon is a good goal, but if there's a good way to get RegionCoverer to detect the problem, it might be more expedient to detect and abort there.

[alan-strohm]

On this test case with DCHECKs turned off, the C++ version runs for 50s before returning an empty set of cells. So refreshing the golang implementation from the C++ one might fix this.

[alan-strohm]

It seems like the go code terminates too? So should we just close this as WAI?
time go run main.go
[4/023231102]
[]
go run main.go 70.58s user 8.25s system 141% cpu 55.541 total

[alan-strohm]

In C++, this isn't actually caught by a DCHECK. The validity check is guarded by the s2debug flag and the s2debug_override_ option. Adding s2debug_override to our s2.Polygon seems like a potential option to improve things here. Although we might want to hold off on that until we decide whether we'd like an s2debug library-wide option for it to "override".

I started a discussion to come up with a more comprehensive set of options since it seems like this will be a recurring topic for the project.

[jmr]

It seems like the go code terminates too? So should we just close this as WAI?

SGTM.