ERROR: XX000: SQL/MM Spatial exception - geometry crosses an edge

[Lars Aksel Opsahl]

When running attached before_error_2.sql it runs ok with no errors

PostgreSQL 12.6 (Ubuntu 12.6-0ubuntu0.20.04.1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 9.3.0-17ubuntu1~20.04) 9.3.0, 64-bit

POSTGIS="3.4.0 0874ea3" [EXTENSION] PGSQL="120" GEOS="3.12.1-CAPI-1.18.1" (compiled against GEOS 3.10.2) SFCGAL="1.3.7" PROJ="8.2.0 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db" GDAL="GDAL 3.4.3, released 2022/04/22" LIBXML="2.9.10" LIBJSON="0.13.1" LIBPROTOBUF="1.3.3" WAGYU="0.5.0 (Internal)" TOPOLOGY RASTER

But then I run line below and I get the topology error

SELECT topology.TopoGeo_addLinestring('tmp_dyrkbarjord_04_t3_a_test_issue_70_87','0102000020A2100000100000000D880F7BEC5930406F570C22A7305140C8AC7234EB5930405F149102A730514053CB13A4DA593040B76B72A1A5305140E8A20595C8593040E64298B4A43051400F88396EBD593040F7AD0040A4305140F45788B1AB5930405377D394A330514064D7228B9B593040E5B2F209A3305140FBEE4BCD895930409618A437A23051400AD56EC465593040D2CC44809F3051402EFFCCC95259304025A49FFC9D30514044D849034459304007A8D89F9C3051409F963BB333593040749B58689B3051406D643F49255930409399D1439A30514065EAA6911D593040CAF1A7BA99305140F63C2ACD16593040D2B1794C99305140558DD4BB19593040835BCB8198305140');

Here is the error message

ERROR:  XX000: SQL/MM Spatial exception - geometry crosses an edge (endnodes in faces 34 and 0)
LOCATION:  pg_error, lwgeom_pg.c:345

I also tested on my local mac and we have the same problem here running this setup

PostgreSQL 14.10 (Homebrew) on aarch64-apple-darwin23.0.0, compiled by Apple clang version 15.0.0 (clang-1500.0.40.1), 64-bit

POSTGIS="3.3.4 3.3.4" [EXTENSION] PGSQL="140" GEOS="3.12.1-CAPI-1.18.1" PROJ="9.3.1" LIBXML="2.11.5" LIBJSON="0.17" LIBPROTOBUF="1.5.0" WAGYU="0.5.0 (Internal)" TOPOLOGY

and on this system same problem

PostgreSQL 15.4 (Ubuntu 15.4-2.pgdg22.04+1) on x86_64-pc-linux-gnu, compiled by gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0, 64-bit

POSTGIS="3.4.0 0874ea3" [EXTENSION] PGSQL="150" GEOS="3.10.2-CAPI-1.16.0" PROJ="8.2.1 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db" LIBXML="2.9.13" LIBJSON="0.15" LIBPROTOBUF="1.3.3" WAGYU="0.5.0 (Internal)" TOPOLOGY

[Lars Aksel Opsahl]

File to run to prepare error context

[Lars Aksel Opsahl]

The line added is not connected to any other lines the database.

So here the problem seems to be that just before adding the last the line the topology is invalid and that seems to happen silently when adding the lines from the attached file as see we in this check before adding the last line.

select ValidateTopology('tmp_dyrkbarjord_04_t3_a_test_issue_70_87');

returns this before adding the last line

LOCATION:  exec_stmt_raise, pl_exec.c:3883
           validatetopology            
---------------------------------------
 ("edge crosses edge",65,77)
 ("hole not in advertised face",-112,)
 ("hole not in advertised face",-111,)
 ("hole not in advertised face",-91,)
(4 rows)

[strk]

Reduced testcase

-- Creates a valid topology
SELECT topology.CreateTopology ('topo_t5699');

SELECT topology.TopoGeo_addLinestring('topo_t5699', 'LINESTRING(
16.330791631988802 68.75635661578073,
16.332533372319826 68.75496886016562,
16.355483101540106 68.756151360702)');

SELECT topology.TopoGeo_addLinestring('topo_t5699', 'LINESTRING(
16.345890311070306 68.75803010362833,
16.33167771310482 68.75565061843871,
16.330791631988802 68.75635661578073)');

SELECT * FROM ValidateTopology('topo_t5699'); -- verify the topology is valid

BEGIN;

-- Corrupts the topology introducing crossing edges
SELECT topology.TopoGeo_addLinestring('topo_t5699', 'LINESTRING(
16.30641253121884 68.75189557630306,
16.33167771310482 68.75565061843871
)'::geometry);

SELECT * FROM ValidateTopology('topo_t5699'); -- crossing edges are found

[strk]

The initial state of the topology has only 2 edges being almost coincident in the segment incident to a shared node. Note how there is no node in the point in which they get far apart:

The incoming line has an endpoint near the spot in which we're missing a node

According to ST_Relate the incoming line has the same relation to both edges:

=# select ST_Relate(i.g,e.geom), ST_Crosses(i.g, e.geom), ST_Touches(i.g, e.geom), e.edge_id from t5699_offending_input i, topo_t5699.edge e;
 st_relate | st_crosses | st_touches | edge_id 
-----------+------------+------------+---------
 FF10F0102 | f          | t          |       2
 FF10F0102 | f          | t          |       1
(2 rows)

The matrix is:

    i b e
    - - -
i | F F 1
b | 0 F 0
e | 1 0 2

What the matrix tells us is that the incoming line's endpoint intersects with the interiors of both edges, but if it is true that those two edges only intersect at their boundary how can their interior intersect both with the same point ? It sounds like a possible bug in GEOS to me.

ST_Relate finds one endpoint of the incoming segment being completely disjoint, as expected, and the other intersecting edge 2 but being disjoint from edge 1.

[strk]

Analyzing the resulting topology, reported as having crossing edges, I cannot get ST_Crosses nor ST_Relate to confirm the fact:

strk=# select * from validatetopology('topo_t5699');
       error       | id1 | id2 
-------------------+-----+-----
 edge crosses edge |   1 |  46
(1 row)

strk=# select ST_Relate(e1.geom, e2.geom), ST_Crosses(e1.geom,e2.geom), st_touches(e1.geom, e2.geom) from topo_t5699.edge e1, topo_t5699.edge e2 where e2.edge_id > e1.edge_id;
 st_relate | st_crosses | st_touches 
-----------+------------+------------
 FF1F00102 | f          | t
 FF1FF0102 | f          | f
 FF1F00102 | f          | t
 F01FF0102 | f          | t
 FF1F00102 | f          | t
 FF1F00102 | f          | t
(6 rows)

But I do see next_left and next_right labels being wron. Note how edges 1,2 and 45 have them wrong

[strk]

Using squared distance, edge2 is confirmed being closer than edge1:

psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_AddPoint:5079] Edge 2 squared distance: 0
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_AddPoint:5079] Edge 1 squared distance: 1.64235648202829e-31
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_AddPoint:5110] Splitting edge 2

So what happens here is that edge 1 is indeed crossed by the incoming edge because the added node only splits edge 2 and leaves edge 1 untouched, with the result that noding in the topology breaks.

I believe the solution here would be to implement snapping of all edges upon inserting a new node, same as with ​https://trac.osgeo.org/postgis/ticket/5310#comment:3 - handling edges collapse as needed (the portions of edge1 and edge2 going from the new node to their shared node would be equal and thus need to be collapsed into one).

[strk]

A probably more severe issue here is that we ALLOW an invalid topology to be created. This should supposedly not happen as the code is theoretically checking for all these invalid conditions before accepting the change.

The relevant snippt of the log is this:

sql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:682] lwt_be_getEdgeWithinBox2D returned 3 edges 
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:713] Edge 5 converted to GEOS
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:726] Edge 5 relate pattern is FF1F00102
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:713] Edge 2 converted to GEOS
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:726] Edge 2 relate pattern is FF1F00102
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:713] Edge 1 converted to GEOS
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:726] Edge 1 relate pattern is F01FF0102
psql:break.sql:10: DEBUG:  [topo/lwgeom_topo.c:_lwt_CheckEdgeCrossing:792] No edge crossing detected amongh the 3 candidate edges

The last edge (Edge 1) is clearly having the a boundary-interior intersection but the code is not considering that as problematic, while it IS, in this case.

[strk]

Raising an exception instead of silently creating an invalid topology is done in this PR: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/195

With the code in that PR we now get, upon adding the final line:

ERROR:  Spatial exception - geometry boundary touches interior of edge 1

This is still puzzling because the boundary of the geometry is supposed to be the same as the new node being created upon splitting edge 2, so if that boundary touches interior of edge 1 then also the added point should, but was found to be at a squared distance of 1.64235648202829e-31 units.

I suspect GEOS is internally reducing the precision of the geometries upon catching a topology error due to the same robustness troubles we are having.

[Sandro Santilli <strk@…>]

In d5ba6b7/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.

References #5699

[strk]

The GEOS suspect is voiced here: ​https://lists.osgeo.org/pipermail/geos-devel/2024-March/011012.html

[Lars Aksel Opsahl]

Replying to strk:

Raising an exception instead of silently creating an invalid topology is done in this PR: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/195

With the code in that PR we now get, upon adding the final line:

ERROR:  Spatial exception - geometry boundary touches interior of edge 1

This is still puzzling because the boundary of the geometry is supposed to be the same as the new node being created upon splitting edge 2, so if that boundary touches interior of edge 1 then also the added point should, but was found to be at a squared distance of 1.64235648202829e-31 units.

I suspect GEOS is internally reducing the precision of the geometries upon catching a topology error due to the same robustness troubles we are having.

When the overlay NG code was added in JTS was not one intentions make spatial operations more robust and avoid Topology exceptions and I assume that may involve some kind off snapping ?

[Lars Aksel Opsahl]

Replying to strk:

Raising an exception instead of silently creating an invalid topology is done in this PR: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/195

Good, I tested this code last night then we have no invalid topologies any more.

[strk]

Great to hear an exception helps avoiding the invalidity. I'd still keep the ticket open as it's still impossible to add a single-segment line into a valid topology.

See also #2038 for a similar case

[strk]

Also #3280 was due to the same problem

[strk]

An experimental code handling edge merges is here: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/196

[strk]

For the record, Dr.JTS confirmed the GEOS bug with RelateComputer: ​https://github.com/libgeos/geos/issues/968#issuecomment-2041134101

It's to be noted that fixing the GEOS bug would still not give us a solution to the problem of being able to load the incoming line into the existing topology.

[Sandro Santilli <strk@…>]

In 1f5caaf/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.

References #5699 in stable-3.4 branch

[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

[Sandro Santilli <strk@…>]

In 63bb999/git:

Snap all edges to incoming node

Closes #5699
Closes #5711

Includes regress tests for both tickets.

[strk]

For the record: the test put in place for this ticket passed just fine with GEOS-3.8 (pre-OverlayNG) and without the change of snapping all edges.

[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]

Replying to strk:

For the record: the test put in place for this ticket passed just fine with GEOS-3.8 (pre-OverlayNG) and without the change of snapping all edges.

The reason for this is just because GEOS-3.8 is unable to detect the invalidity. Follow up discussion in ​https://trac.osgeo.org/postgis/ticket/5722#comment:18