RelateCompute intersection report inconsistent for lines and boundary points

[strk]

RelateComputer says there's an intersection between line A interior and and line B boundary but says there is no intersection between B boundary and A.

Line A: 010200000002000000B02EA9C2AE5430400E3994256830514037F136E82055304039FAE86851305140 Line B: 01020000000200000064AB380D714E3040A38E9F0E1F305140E798A2D4E85430405F5969945C305140

A Interior intersects B boundary in dim = 0

   I B E
I: F 0 1
B: F F 0
E: 1 0 2

A has no intersection with Boundary(B)

   I B E
I: F F 1
B: F F 0
E: 0 F 2 

Reported in https://lists.osgeo.org/pipermail/geos-devel/2024-March/011012.html and confirmed in https://github.com/libgeos/geos/issues/968#issuecomment-2041134101

[dr-jts]

This is not a bug, but a limitation in the ability to compute the relate matrix due to numeric rounding. In order to correctly compute the relate matrix for two lines the node point must be computed (see https://github.com/locationtech/jts/issues/396 for an example of a case which requires noding for correct evaluation). However, due to numeric roundoff the computed node point equals an endpoint of line B, even though the robust Orientation test reports that it lies in the interior of B.

It's not clear that there is an algorithm which can avoid noding, since this would cause an inconsistency in other cases.

Another future option is to support evaluating predicates with a distance tolerance. This will essentially allow avoiding inconsistency due to roundoff. (However, note that this may not be a solution in itself - when used as part of a bigger process, the entire process must be designed to support using a tolerance.)

[strk]

For the record, GEOS-3.8 gives a different intersection matrix for the two lines, saying there is no interior/boundary intersection. Did 3.8 not have this limitation ?

   I B E
I: F F 1
B: F F 0
E: 1 0 2

[strk]

An XML test for this case was added in #1092 - the test passes in 3.8 branch, fails in main branch:

build/bin/test_xmltester -v ../3.8/tests/xmltester/tests/issue/issue-geos-gh1064.xml 
../3.8/tests/xmltester/tests/issue/issue-geos-gh1064.xml: case1: test1: relatestring(A, B): failed. (0 ms)
        Description: See https://github.com/libgeos/geos/issues/1064
        Geometry A: LINESTRING (16.330791631988802 68.75635661578073, 16.332533372319826 68.75496886016562)
        Geometry B: LINESTRING (16.30641253121884 68.75189557630306, 16.33167771310482 68.75565061843871)
        Expected result: FF1FF0102
        Obtained result: F01FF0102

Files: 1
Tests: 1
Failed: 1
Succeeded: 0

[strk]

CI confirming the problem in main branch: https://github.com/libgeos/geos/actions/runs/8982099329/job/24668988763?pr=1093#step:8:7913 (PR GH-1093)

CI confirming there is no problem in 3.8 branch: https://github.com/libgeos/geos/actions/runs/8982102259/job/24668979871?pr=1092#step:4:6239 (PR GH-1092)

[dr-jts]

For the record, GEOS-3.8 gives a different intersection matrix for the two lines, saying there is no interior/boundary intersection. Did 3.8 not have this limitation ?

This might be due to the change in line intersection computation math, from ttmath to DD (in https://github.com/libgeos/geos/commit/ec219c058280dae38f338437925c8062fb6b85d7). However, the reason that DD was added is that it fixes other cases which were failing using ttmath.

Note that 3.8 is reporting that there is no intersection between the lines at all. However, the 3.12 Orientation predicate is reporting that there is a proper intersection between them (see image below). This uses the best known algorithm we have, so the only thing we can do is to accept it as the correct analysis of the situation. So in this case 3.8 is "wrong", according to current technology.