False positive answer from GEOSCoordSeq_isCCW

[strk]

This closed coordinate sequence is reported to go counterclockwise by GEOSCoordSeq_isCCW (which returns true) when instead it goes clockwise:

010200000004000000FD613B270D6C314031AA543619475140890205230D6C31408177583619475140A4613B270D6C31402FAA543619475140FD613B270D6C314031AA543619475140

It's known to be a robustness problem, which is known to be fixed by using larger foating point numbers on 64bit platform, see https://trac.osgeo.org/postgis/ticket/6065

In that PostGIS ticket you'll see that SFCGAL can give a correct answer.

The problem seems to be the presence of long outgoing spikes.

The documentation for the function (comment above the function signature in geos_c.h) say:

Invalid (collapsed) or short (fewer than 4 points) sequences return false.

I guess this is a case of "collapsed", but the JTS description ( of CGAlgorithms::isCCW, on which this function is based ) has a slightly different wording:

If the ring is invalid (e.g. self-crosses or touches), the computed result may not be correct.

Is this a case of "touches" ?

@dr-jts

[strk]

Test to show the problem:

diff --git a/tests/unit/algorithm/CGAlgorithms/OrientationIsCCWTest.cpp b/tests/unit/algorithm/CGAlgorithms/OrientationIsCCWTest.cpp
index 5dddfac2f..8c0c22bee 100644
--- a/tests/unit/algorithm/CGAlgorithms/OrientationIsCCWTest.cpp
+++ b/tests/unit/algorithm/CGAlgorithms/OrientationIsCCWTest.cpp
@@ -248,6 +248,15 @@ void object::test<16>
 }
 
 
+// See https://trac.osgeo.org/postgis/ticket/6065
+template<>
+template<>
+void object::test<17>
+()
+{
+    const std::string wkt("POLYGON((17.422075702665087 69.11091383235977,17.42207545158684 69.11091383590066,17.42207570266477 69.11091383235974,17.422075702665087 69.11091383235977))");
+    checkCCW(false, wkt);
+}
 
 
 } // namespace tut

[strk]

For the record: the SFCGAL implementation uses exact math operations (arbitrary precision), thus the correct answer.

[strk]

I filed a PR against JTS to check if it works there: locationtech/jts#1189
This is because reading the code suggests it SHOULD work in these cases

[strk]

I was wrong, used the wrong ring. The actual problematic ring is correctly found to be CW.

[strk]

Reopening because using WKB still results in the code finding the ring CCW

0103000000010000000A000000890205230D6C31408177583619475140FD613B270D6C314031AA5436194751405D58985776943140195EE965DE47514085FFA6647B9F31408FC1C62B394851405D58985776943140195EE965DE475140FD613B270D6C314031AA543619475140A4613B270D6C31402FAA543619475140890205230D6C31408177583619475140320205230D6C31407E77583619475140890205230D6C31408177583619475140

[strk]

Bah, closing again, WKB works fine as well.

[strk]

Reopening as I found another case:

0103000000010000000A0000007A6873CA73782440DE38B01D9CEE4D40438AD46B73782440FEAF5D499CEE4D40588FC2F528782440106D5B2FB5EE4D4089058AA63E7824401D9FCAB6B0EE4D4084CBFA5C7A7824405CC705259CEE4D4089058AA63E7824401D9FCAB6B0EE4D4040A8CCBF35782440B80E7F8CB2EE4D40588FC2F528782440106D5B2FB5EE4D40438AD46B73782440FEAF5D499CEE4D407A6873CA73782440DE38B01D9CEE4D40

This case originates from an existing PostGIS test (for ticket 5568).

The ring is considered to be CounterClockwise by GEOS but it isn't, and SFCGAL agrees it isn't.

The interesting thing is that GEOS changes response based on where we start in the ring

The above figure shows the ring, with visible outgoing dangling edges 1 and 4.
The above HEXWKT is starting on the first vertex of edge 4 (on its left side).

The next HEXWKT is starting on the first vertex of edge 1 (on its left side), and is reported by GEOS to NOT be CounterClockwise.

0103000000010000000A00000089058AA63E7824401D9FCAB6B0EE4D4084CBFA5C7A7824405CC705259CEE4D4089058AA63E7824401D9FCAB6B0EE4D4040A8CCBF35782440B80E7F8CB2EE4D40588FC2F528782440106D5B2FB5EE4D40438AD46B73782440FEAF5D499CEE4D407A6873CA73782440DE38B01D9CEE4D40438AD46B73782440FEAF5D499CEE4D40588FC2F528782440106D5B2FB5EE4D4089058AA63E7824401D9FCAB6B0EE4D40

SFCGAL is consistent in saying the ring is NOT CounterClockwise.

I think the problem is that Orientation::isCCW checks orientation of the first up-and-down triplets of vertices found having the middle vertex one with max X (highest/topmost). In this case such top-most vertex is encountered twice: once coming up from the green edge (2), once coming up from the blue edge (1).

In the first case the considered triangle is counterclockwise ( from 2 to 1 ).

In the second case the considered triangle is clockwise ( from 1 to 2 ).