Spatial exception - geometry boundary touches interior of edge 4 (XX000)

[strk]

Repro:

Prepare:

SELECT topology.DropTopology ('topo');
SELECT topology.TopoGeo_AddLineString ('topo',
'LINESTRING(
  -11.968112622212203 0.651457829865329,
    8.13909499443551  0.334122751124234,
  -11.964143711257549 0.31568377154268)');

Fail:

SELECT topology.TopoGeo_AddLineString ('topo',
'LINESTRING(
  -0.65145782986533 -11.968112622212203,
  -0.159231454672685  8.13973141470126)');

What happens in this case is that the intersection point computed by GEOS is further than the minimum computed tolerance for the point so when PostGIS Topology adds the point it fails to snap/split the existing edge on which the intersection point was computed, thus creating an isolated node and finding an intersection between that aforementioned edge and the incoming edge upon adding it.

The exception is thrown in the master branch. I didn't try what happens in the 3.4 branch but chances are an invalid topology is created instead.

[strk]

Confirmed: in 3.4 branch the line is added but an invalidity is created: edge crosses edge|4|5

[strk]

Proposed fix: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/201

[Sandro Santilli <strk@…>]

In 3d3421a8/git:

Have _lwt_CheckEdgeCrossing check for interior-boundary intersections

So far only interior-interior intersections have been checked by
the function, missing an important kind of invalid edge addition.

In stable-3.3 branch:
References #5699
References #5711
References #5722

[Sandro Santilli <strk@…>]

In 2aafd239/git:

Have _lwt_CheckEdgeCrossing check for interior-boundary intersections

So far only interior-interior intersections have been checked by
the function, missing an important kind of invalid edge addition.

In stable-3.2 branch (3.2.8dev):
References #5699
References #5711
References #5722

[strk]

Work continues in ​https://git.osgeo.org/gitea/postgis/postgis/pulls/202

What we would need here is a way to tell how much the GEOS input lines were moved to snap to detected intersection points. I don't think such information is currently available even at the C++ level.

Alternatively we should compute intersection points on the PostGIS side, analyzing segment by segment and snapping each in turn if needed.

[strk]

New analisys: upon adding the vertical line GEOS correctly computes nodes but PostGIS is unable to tell that the node falls on the edge. Logs:

[topo/lwgeom_topo.c:_lwt_AddPoint:6536] Adding point: POINT(-0.350498072243138 0.326335974301659)
[topo/lwgeom_topo.c:_lwt_AddPoint:6612] New point is within 1.26179306007529e-15 units of 0 edges
[topo/lwgeom_topo.c:lwt_GetFaceContainingPoint:7479] Closest segment on edge 2 is 1 (dist 8.28391e-18)
DEBUG:  [topo/lwgeom_topo.c:lwt_GetFaceContainingPoint:7482] Closest segment on edge 2 is LINESTRING(8.13909 0.334123, -11.9641 0.315684)

What the logs say is a contradiction:

1. The point is NOT within 1.24e-15 units from the edge
2. The point is at 8.28e-18 distance from the edge

Either 1 or 2 is true, cannot both be true.

• _lwt_AddPoint (1) uses ST_DWithin to find edges within distance, which gives the wrong answer, in this case.
• lwt_GetFaceContainingPoint (2) uses the ←> operator to find the closest edge and ptarray_closest_segment_2d to compute the distance.

[strk]

I'm not sure how 8.28391e-18 comes out from but ST_Distance seems to give 1.8318679906315083e-15 which is still bigger than the computed tolerance of 1.26179306007529e-15:

postgis_reg=# select edge_id, ST_Distance(geom, '0101000000C11966778F6ED6BF27924848B0E2D43F') dist, ST_DWithin(geom, '0101000000C11966778F6ED6BF27924848B0E2D43F', 1.26179306007529e-15) from t
opo.edge where edge_id = 2;
 edge_id |          dist          | st_dwithin 
---------+------------------------+------------
       2 | 1.8318679906315083e-15 | f

In any case the intersection point computed by GEOS is found to be further than the computed min tolerance.

[strk]

So the bottom line problem for PostGIS is to find out which existing edges need to be snapped to the new node. At the moment the code just assumes the maximum drift of an edge can be computed based on the floating point grid. That's where the computed tolerance comes from. I'm pretty sure GEOS uses a different "tolerance" internally, and it would be helpful to extrapolate it externally, or inject it from outside in, using the GEOS-3.9 backed functions for fixed-precision overlay.

[strk]

For the record: current minimum GEOS version is 3.8 so not enough to guarantee fixed-precision overlay support

[robe]

winnie is complaining about this now, did you put a test in place for this?

​https://winnie.postgis.net/job/PostGIS_EDB_Regress_winnie/18898/consoleFull

PostgreSQL 15.6, compiled by Visual C++ build 1937, 64-bit
  Postgis 3.5.0dev - (3.4.0rc1-1104-gfd3a41f8d) - 2024-05-06 06:18:42
  scripts 3.5.0dev 3.4.0rc1-1104-gfd3a41f8d
  raster scripts 3.5.0dev 3.4.0rc1-1104-gfd3a41f8d
  GEOS: 3.13.0dev-CAPI-1.18.0
  PROJ: 8.2.1 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=C:\Users\Administrator\AppData\Local/proj DATABASE_PATH=e:\jenkins\proj\rel-proj-8.2.1w64gcc81\share\proj\proj.db
  SFCGAL: 1.5.1
  GDAL: GDAL 3.8.5, released 2024/04/02

 ./topology/test/regress/topogeo_addlinestring .. failed (diff expected obtained: /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_228_diff)
-----------------------------------------------------------------------------
--- ./topology/test/regress/topogeo_addlinestring_expected	2024-04-30 15:13:51.239393800 -0400
+++ /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_228_out	2024-05-06 03:27:40.668553000 -0400
@@ -171,8 +171,7 @@
 t3280.start|t
 t3280|L11
 t3280|L22
-t3280|L1b1
-t3280|L1b2
+ERROR:  Spatial exception - geometry intersects edge 2
 t3280.end|Topology 'bug3280' dropped
 t3380.start|t
 t3380.L1|1
-----------------------------------------------------------------------------
 ./topology/test/regress/topogeo_addlinestring_robust .. failed (diff expected obtained: /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_229_diff)
-----------------------------------------------------------------------------
--- ./topology/test/regress/topogeo_addlinestring_robust_expected	2024-04-30 15:13:51.265763100 -0400
+++ /projects/postgis/tmp/3.5.0dev_pg15_geos3.13_gdal3.8.5w64/test_229_out	2024-05-06 03:29:00.619283800 -0400
@@ -1,2 +1,4 @@
 #5699|-checking-
+#5699|addline exception|Spatial exception - geometry intersects edge 3 (XX000)
 #5711|-checking-
+#5711|addline exception|Spatial exception - geometry intersects edge 3 (XX000)
-----------------------------------------------------------------------------

[robe]

hmm I thought winnie was running with latest geos, but looks like the hook isn't working, so her last build was like a month ago. ​https://winnie.postgis.net/view/GEOS/job/GEOS_Master/

Going to force a rebuild to see if it fixes this issue.

[strk]

topogeo_addlinestring is not any recent, topogeo_addlinestring_robust is recent

I guess the floating point grid on 32bit is different

[strk]

Interesting fact: the test for this case succeeds with GEOS-3.8 (before OverlayNG)

[strk]

Confirmed. Building PostGIS against GEOS-3.8 and then installing/uninstalling GEOS from the main branch shows the difference:

$ regress/run_test.pl --nodrop --topology -v topology/test/regress
PostgreSQL 15.6 (Debian 15.6-0+deb12u1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 12.2.0-14) 12.2.0, 64-bit
  Postgis 3.5.0dev - (3.4.0rc1-1104-gfd3a41f8d) - 2024-05-07 06:58:49
  GEOS: 3.13.0dev-CAPI-1.19.0

Running tests

 topology/test/regress/topogeo_addlinestring_robust .. failed (diff expected obtained: /tmp/pgis_reg/test_1_diff)
-----------------------------------------------------------------------------
--- topology/test/regress/topogeo_addlinestring_robust_expected 2024-05-07 09:01:54.377226450 +0200
+++ /tmp/pgis_reg/test_1_out    2024-05-07 09:03:58.072220001 +0200
@@ -1,3 +1,4 @@
 #5699|-checking-
 #5711|-checking-
 #5722|-checking-
+#5722|addline exception|Spatial exception - geometry boundary touches interior of edge 4 (XX000)
-----------------------------------------------------------------------------

Run tests: 1
Failed: 1

$ regress/run_test.pl --nodrop --topology -v topology/test/regress
PostgreSQL 15.6 (Debian 15.6-0+deb12u1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 12.2.0-14) 12.2.0, 64-bit
  Postgis 3.5.0dev - (3.4.0rc1-1104-gfd3a41f8d) - 2024-05-07 06:58:49
  GEOS: 3.8.4-CAPI-1.13.5

Running tests

 topology/test/regress/topogeo_addlinestring_robust .. ok in 195 ms

Run tests: 1
Failed: 0

[Sandro Santilli <strk@…>]

In 50abdc26/git:

Have _lwt_CheckEdgeCrossing check for interior-boundary intersections

So far only interior-interior intersections have been checked by
the function, missing an important kind of invalid edge addition.

in stable-3.1 branch (3.1.12):

References #5699
References #5711
References #5722

[strk]

It's hard to tell who's right and who's wrong between GEOS-3.8 and GEOS-3.12 because the error could also be in a false negative validity detection too. Comparing logs when run against 3.8 and 3.12:

 3.8: [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:700] Edge 4 relate pattern is FF1F00102
3.12: [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:700] Edge 4 relate pattern is F01F001F2

This is what is reported here: ​https://github.com/libgeos/geos/issues/1064#issuecomment-2097689307

[mdavis]

Replying to strk:

It's hard to tell who's right and who's wrong between GEOS-3.8 and GEOS-3.12 because the error could also be in a false negative validity detection too.

GEOS 3.12 (and some earlier versions) has the best available Orientation algorithm (for testing line-line intersection) that we have found so far. This test reports that the endpoints of B lie on opposite sides of Line A, and vice-versa. So Line B does intersect Line, in their interiors. This means that the relate matrix computed by 3.12 is correct (as best we can tell).

This is a good example of why to get fully valid noding a snap-rounding approach with a distance tolerance needs to be used.

[strk]

I confirm GEOS-3.8 "succeeds" only because it does not notice the interior-interior intersection. I tested this by using GEOS-3.8 to build the topology. The so-built topology validates fine with GEOS-3.8. Then I upgraded to GEOS-3.12 and ONLY run the topology validation, which told me the topology was invalid !

I am aware that we need to snap-round existing edges. The current problem with this ticket is finding out what a proper "distance tolerance" is. My current guess is that GEOS is internally computing such "distance tolerance" and it does not match the one computed by PostGIS Topology.