Port S2LegacyValidQuery and use in polygon validation

[parsaaes]

In the documentation of PolygonFromOrientedLoops, it's said that:

It expects loops to be oriented such that the polygon interior is on the left-hand side of all loops. This implies that shells and holes should have opposite orientations in the input to this method.

and:

The loop orientations must all be consistent; for example, it is not valid to have one CCW loop nested inside another CCW loop, because the region between the two loops is on the left-hand side of one loop and the right-hand side of the other.

But in this example, I'm giving two nested counter-clockwise loops to PolygonFromOrientedLoops and it automatically makes the inner loop a hole like how it does in PolygonFromLoops. So shouldn't Validate returns an error in this situation or I'm missing something here?

This is the visualization of loops:

Code:

package main

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

func main() {
	// ccw
	s := [][]float64{
		{
			35.841751,
			50.991497,
		},
		{
			35.836811,
			50.991626,
		},
		{
			35.83695,
			51.002612,
		},
		{
			35.842065,
			51.00081,
		},

	}

	// ccw
	h := [][]float64{
		{
			35.841056,
			50.996089,
		},
		{
			35.837785,
			50.993557,
		},
		{
			35.83789,
			51.000381,
		},

	}


	sLoop := loopFromDegrees(s)
	hLoop := loopFromDegrees(h)

	polygon := s2.PolygonFromOrientedLoops([]*s2.Loop{sLoop, hLoop})

	fmt.Println(sLoop.Area() - hLoop.Area(), polygon.Area())
	fmt.Println(polygon.Validate())
}

func loopFromDegrees(in [][]float64) *s2.Loop {
	points := make([]s2.Point, 0, len(in))

	for _, p := range in {
		points = append(points, s2.PointFromLatLng(s2.LatLngFromDegrees(p[0], p[1])))
	}

	return s2.LoopFromPoints(points)
}

Output:

9.931323540629714e-09 9.931323540629714e-09
<nil>

[msiner]

This does appear to be a bug or, at least, an implementation inconsistent with the C++ implementation. Below is an equivalent C++ program. The provided loops work fine when calling S2Polygon::InitNested(), but produce an error when calling S2Polygon::InitOriented().

#include <iostream>
#include <memory>
#include <vector>

#include <s2/s2latlng.h>
#include <s2/s2loop.h>
#include <s2/s2point.h>
#include <s2/s2polygon.h>

using std::cout;
using std::endl;
using std::vector;

int main() {
  vector<S2Point> s{
      S2LatLng::FromDegrees(35.841751, 50.991497).ToPoint(),
      S2LatLng::FromDegrees(35.836811, 50.991626).ToPoint(),
      S2LatLng::FromDegrees(35.83695, 51.002612).ToPoint(),
      S2LatLng::FromDegrees(35.842065, 51.00081).ToPoint(),
  };

  vector<S2Point> h{
      S2LatLng::FromDegrees(35.841056, 50.996089).ToPoint(),
      S2LatLng::FromDegrees(35.837785, 50.993557).ToPoint(),
      S2LatLng::FromDegrees(35.83789, 51.000381).ToPoint(),
  };

  vector<std::unique_ptr<S2Loop>> loops;

  loops.push_back(std::make_unique<S2Loop>(s));
  loops.push_back(std::make_unique<S2Loop>(h));

  cout << loops[0]->GetArea() - loops[1]->GetArea() << endl;

  S2Polygon polyN;
  polyN.InitNested(std::move(loops));

  cout << polyN.GetArea() << endl;
  cout << polyN.IsValid() << endl;

  loops.clear();

  loops.push_back(std::make_unique<S2Loop>(s));
  loops.push_back(std::make_unique<S2Loop>(h));

  S2Polygon polyO;
  polyO.InitOriented(std::move(loops));

  cout << polyO.GetArea() << endl;
  cout << polyO.IsValid() << endl;

  return 0;
}

Output:

9.93132e-09
9.93132e-09
1
/home/mark/s2geometry/src/s2/s2polygon.cc:180 ERROR Inconsistent loop orientations detected
/home/mark/s2geometry/src/s2/s2polygon.cc:447 FATAL Check failed: IsValid() Aborted

[msiner]

Looks like the implementation is incomplete. The TODO comment in s2/polygon.go indicates that the validation is currently not implementing the orientation check. As you can see, the planned error message, "inconsistent loop orientations detected" matches the error reported by the C++ implementation.

geo/s2/polygon.go

Lines 462 to 473 in e86565b

	// TODO(roberts): Uncomment the remaining checks when they are completed.
	// Check for loop self-intersections and loop pairs that cross
	// (including duplicate edges and vertices).
	// if findSelfIntersection(p.index) {
	// return fmt.Errorf("polygon has loop pairs that cross")
	// }
	// Check whether initOriented detected inconsistent loop orientations.
	// if p.hasInconsistentLoopOrientations {
	// return fmt.Errorf("inconsistent loop orientations detected")
	// }

[jmr]

In C++, S2Polygon::FindValidationError now uses S2LegacyValidQuery, so that should be ported over.

[rsned]

s2LegacyValidQuery needs s2ValidQuery which needs internal/s2index_cell_data and internal/s2incident_edge_tracker