Loop `validate()` fails to adequately detect duplicate vertices

[missinglink]

The current code only checks for duplicate adjacent vertices:

https://github.com/golang/geo/blob/6adc5660321723185f04b66d66a5563b29228236/s2/loop.go#L251-L260

While the comments say:

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

https://github.com/golang/geo/blob/6adc5660321723185f04b66d66a5563b29228236/s2/loop.go#L34-L35

[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

[panmari]

There is indeed a an open TODO to implement findSelfIntersection at https://github.com/golang/geo/blob/0b6e08c212fb81033dc8017d23f8ddfbdfecc5f4/s2/polygon.go#L466. @missinglink your PR would be greatly appreciated!

[missinglink]

@panmari I don't see many PRs getting merged here, I wouldn't want to commit the time unless it's actually going to be reviewed and merged.

I see you are a collaborator on the repo, do you have merge access?

[panmari]

Indeed, there was a period of less active maintenance, but I'm happy to say that the repository is now actively being maintained again, see recently merged PRs.

Yes, I do have merge access and we are committed to reviewing and merging PRs in a timely manner. We are actively working through the backlog right now.

We would definitely value your contributions and encourage you to submit your PRs.