Loop validate() fails to adequately detect duplicate vertices

[missinglink]

The current code only checks for duplicate adjacent vertices:

geo/s2/loop.go

Lines 251 to 260 in 6adc566

	// Loops are not allowed to have any duplicate vertices or edge crossings.
	// We split this check into two parts. First we check that no edge is
	// degenerate (identical endpoints). Then we check that there are no
	// intersections between non-adjacent edges (including at vertices). The
	// second check needs the ShapeIndex, so it does not fall within the scope
	// of this method.
	for i, v := range l.vertices {
	if v == l.Vertex(i+1) {
	return fmt.Errorf("edge %d is degenerate (duplicate vertex)", i)
	}

While the comments say:

Loops are not allowed to have any duplicate vertices (whether adjacent or not)

geo/s2/loop.go

Lines 34 to 35 in 6adc566

	// Loops are not allowed to have any duplicate vertices (whether adjacent or
	// not). Non-adjacent edges are not allowed to intersect, and furthermore edges

[rusneustroevkz]

@missinglink Hello
Did you solve this problem?

[missinglink]

It's simple enough to remove duplicate vertices (although slightly slow as it's O(n)).

The issue with removing non-adjacent vertices is that it could invalidate the geometry, such as the case of an hourglass polygon.

What I settled on is to remove adjacent duplicates like it's currently doing and raising an error for all other cases, this still requires a duplicate check operation which is also O(n).

I suspect the authors preferred to assume that the geometry was validated outside the library, but included this adjacent neighbor check specifically to gracefully handle cross compatibility with specifications where the first and last point of a loop are duplicated by convention.

[edit] sorry, reading the code again from desktop, the library doesn't attempt to fix geometries, it just checks them for validity.

So I guess this is still something which needs to be fixed as it's possible to construct an invalid Loop where Validate() returns nil.

[missinglink]

https://github.com/missinglink/s2js/blob/04cea2143a2b587674135dd0dab7585b75d8b2de/geojson/loop.ts#L16-L47

[missinglink]

The bug isn't present in the C++ codebase because it has an OR condition which hasn't yet been implemented in Go:

FindValidationErrorNoIndex(error) || s2shapeutil::FindSelfIntersection(index_, error)

https://github.com/google/s2geometry/blob/ca1f3416f1b9907b6806f1be228842c9518d96df/src/s2/s2loop.cc#L190-L193

[missinglink]

I could port s2shapeutil::FindSelfIntersection to Go but I doubt it would be merged, so not worth the effort:

https://github.com/google/s2geometry/blob/ca1f3416f1b9907b6806f1be228842c9518d96df/src/s2/s2shapeutil_visit_crossing_edge_pairs.cc#L454