Port S2LegacyValidQuery and use in polygon validation #72

parsaaes · 2020-09-14T16:30:19Z

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>

The text was updated successfully, but these errors were encountered:

msiner · 2021-02-27T20:03:16Z

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 · 2021-02-27T20:29:36Z

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 · 2025-04-11T10:47:42Z

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

rsned · 2025-04-12T19:19:32Z

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

These are ports of the C++ s2/internal/ types that are needed for ValidationQuery for Loops and Polygons. Work for issues golang#72, golang#108.

msiner mentioned this issue Jun 14, 2021

Implement Polygon.hasInconsistentLoopOrientations #76

Open

jmr changed the title ~~Invalid input loops to PolygonFromOrientedLoops~~ Port S2LegacyValidQuery and use in polygon validation Apr 11, 2025

alan-strohm added the enhancement label Apr 11, 2025

rsned self-assigned this Apr 12, 2025

rsned added a commit to rsned/geo that referenced this issue May 15, 2025

Add incidentEdgeTracker and indexCellData types and tests

40abfda

These are ports of the C++ s2/internal/ types that are needed for ValidationQuery for Loops and Polygons. Work for issues golang#72, golang#108.

rsned mentioned this issue May 15, 2025

Add incidentEdgeTracker and indexCellData types and tests #180

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

Port S2LegacyValidQuery and use in polygon validation #72

Port S2LegacyValidQuery and use in polygon validation #72

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Port S2LegacyValidQuery and use in polygon validation #72

Port S2LegacyValidQuery and use in polygon validation #72

Comments

Uh oh!

Uh oh!

Uh oh!

Uh oh!