XX000: SQL/MM Spatial exception - point not on edge

[Lars Aksel Opsahl]

When running attached before_error.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_114','0102000020A2100000120000008E53A2AC61982F40170E0A24A94351400E3838CC09982F407BF5CA22A943514048E6043900982F409D8968D7A643514055EB02C9FE972F4074BCD8DBA6435140D43BAE82F0972F40ABF5EA43A7435140D069DEF2F0972F40B57E5352A8435140B5307558F1972F40804063C8A8435140BC0B4C20E3972F40040DE7D9AA435140F47186EBE7972F4056886B4AAB435140BD034595F5972F4068E7269BAB4351407DB6BED907982F40FFC865B5AB43514088D6944915982F403F7EC93EAB435140CE119F9C23982F404D335902AB4351401E67157B40982F4006679C11AB4351407C88A3B24F982F40E210E5F6AA4351408A79190B5B982F409342C08AAA4351404A831F995F982F407175A428AA4351408E53A2AC61982F40170E0A24A9435140',0);

Here is the error message

ERROR:  XX000: SQL/MM Spatial exception - point not on edge
LOCATION:  pg_error, lwgeom_pg.c:332

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 create a topology with data

[Lars Aksel Opsahl]

If we create the topology with a tolerance , then it runs with out any errors but I try to avoid using tolerances and instead remove tiny areas based on different rules later.

[Lars Aksel Opsahl]

I did some more testing here and adding a tolerance like 1e-07 works in this, but fails for other cases.

[Lars Aksel Opsahl]

This seems to be related to adding closed line that already seems to covered by existing edges and where there also are two other edges in the database.

Here is a simplified test with the same error.

Here is the before error code

SELECT topology.CreateTopology ('ticket_5698', 4258 , 0);

SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A21000000B0000002576190B5B982F40D536C08AAA435140B7CCA3B24F982F40A2FBE5F6AA4351405EAB157B40982F40C4519D11AB4351405E0E9F9C23982F408F275902AB43514023D3944915982F408072C93EAB435140B4FABED907982F40BEB366B5AB43514053004595F5972F40ABDB269BAB43514020B686EBE7972F4014736C4AAB435140E64F4C20E3972F40C3F7E7D9AA4351404D2D7558F1972F40C13463C8A84351406866DEF2F0972F40F6725352A8435140');
SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A2100000040000006866DEF2F0972F40F6725352A84351406D38AE82F0972F40EDE9EA43A74351408C2F03C9FE972F4032A7D9DBA64351407DBD073900982F40E03769D7A6435140');
SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A210000003000000FFFB9BAC61982F40000E0A24A9435140E57F1F995F982F40B269A428AA4351402576190B5B982F40D536C08AAA435140');
SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A2100000030000007DBD073900982F40E03769D7A64351400E3838CC09982F407BF5CA22A9435140FFFB9BAC61982F40000E0A24A9435140');
SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A21000001C000000D412270433962F40295FD1A5B943514036B4FB6948962F406ACCD48CB9435140B030DD535D962F40FC45BFB5B9435140DFA5A11773962F40886198A1B94351405EE0D91486962F404F29F862B94351403A932FD597962F40EE0FF710B9435140142B8B33A9962F401E4435ACB84351403EA30FDCEB962F40AB5150E8B64351409E8286930E972F401C61152AB643514005AC4A1932972F4062C3277BB54351402F9D966656972F40F3F92CE1B4435140AED41D2B7D972F40006D4C65B4435140A31AAF518F972F4009741E18B4435140F9FAEC7DA1972F40E3F687C1B3435140AFC36D09B2972F405F97625BB343514065B2143DC4972F40C70C6801B3435140D75A15E8E8972F40AB01E16BB24351404BCA2E31FA972F40ADB16B15B2435140E7733E3B0B982F40A92AB4B0B1435140F09455CE1B982F409DA4F32AB1435140DA260BD22A982F40F3FD8B7AB04351400A41B7F536982F408DFCE5BBAF43514081CF914542982F40F6361BF8AE4351406E5AD0C84C982F406C4A072BAE4351406F75407156982F406D96B35DAD4351409D6F67B65D982F40AA1F2B7DAC435140D4C5DBFC5F982F40461AA97FAB4351402576190B5B982F40D536C08AAA435140');
SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A2100000050000006866DEF2F0972F40F6725352A8435140BF3E78E2D4972F402F5A18C5A8435140377EBB1CC3972F4057E58320A94351400335ACCE8B972F408DACCE07AA4351402DD62D1E81972F405D3E341CAA435140');

Then we add this line which is closed,

SELECT topology.TopoGeo_addLinestring('ticket_5698','0102000020A2100000120000008E53A2AC61982F40170E0A24A94351400E3838CC09982F407BF5CA22A943514048E6043900982F409D8968D7A643514055EB02C9FE972F4074BCD8DBA6435140D43BAE82F0972F40ABF5EA43A7435140D069DEF2F0972F40B57E5352A8435140B5307558F1972F40804063C8A8435140BC0B4C20E3972F40040DE7D9AA435140F47186EBE7972F4056886B4AAB435140BD034595F5972F4068E7269BAB4351407DB6BED907982F40FFC865B5AB43514088D6944915982F403F7EC93EAB435140CE119F9C23982F404D335902AB4351401E67157B40982F4006679C11AB4351407C88A3B24F982F40E210E5F6AA4351408A79190B5B982F409342C08AAA4351404A831F995F982F407175A428AA4351408E53A2AC61982F40170E0A24A9435140',0);

and we get the same error

ERROR:  XX000: SQL/MM Spatial exception - point not on edge
LOCATION:  pg_error, lwgeom_pg.c:345

[Lars Aksel Opsahl]

The simple case

[strk]

I can reproduce with POSTGIS="3.5.0dev 3.4.0rc1-1039-g88c3893c7" [EXTENSION] PGSQL="150" GEOS="3.12.2dev-CAPI-1.18.2"

Further simplified:

SELECT topology.CreateTopology ('ticket_5698');

SELECT topology.TopoGeo_addLinestring('ticket_5698','LINESTRING(
15.796760167740288 69.05714853429149,
15.795906966300288 69.05725770093837)');

SELECT topology.TopoGeo_addLinestring('ticket_5698', 'LINESTRING(
15.79762019616626 69.05719853383958,
15.796760167739626 69.05714853429157)');

[strk]

According to ST_Distance the second line's end point is at a distance of ~6.68e-13 units from the start point of the first line and according to ST_Relate the lines do not intersect.

If zero-tolerance was supported the above would result in adding 2 disjoint edges.

Instead PostGIS Topology computes an internal "working tolerance" based on the floating point grid and uses that as a tolerance. The internally computed working tolerance is ~2.49e-13

Snapping the incoming line to the existing one, using the computed tolerance, results in adding a vertex to the incoming line:

LINESTRING(
  15.79762019616626 69.05719853383958, -- initially present
  15.796760167740288 69.05714853429149, -- first vertex of first line, added by snap
  15.796760167739626 69.05714853429157 -- initially present
)

The so-snapped line is then split, resulting in two segments:

LINESTRING(15.79762019616626 69.05719853383958,15.796760167740288 69.05714853429149) LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157)

It's to be noted that the second segment (from added vertex to end vertex of original line) has a length of 6.63e-13 units.

The first segment gets in the topology correctly and gets edge identifier 2.

The second segment is what triggers the problem.

This allows us to further reduce the testcase to only use the second (tiny) segment to the topology, to trigger the problem, which I confirm can be reproduced:

SELECT topology.CreateTopology ('ticket_5698');

SELECT topology.TopoGeo_addLinestring('ticket_5698','LINESTRING(
15.796760167740288 69.05714853429149,
15.795906966300288 69.05725770093837)');

SELECT topology.TopoGeo_addLinestring('ticket_5698', 'LINESTRING(
15.796760167740288 69.05714853429149,
15.796760167739626 69.05714853429157)');

[strk]

Further simplification: it is the addition of the last point of the second linestring to trigger the error:

SELECT topology.CreateTopology ('ticket_5698');

SELECT topology.TopoGeo_addLinestring('ticket_5698','LINESTRING(
15.796760167740288 69.05714853429149,
15.795906966300288 69.05725770093837)');

SELECT topology.TopoGeo_addPoint('ticket_5698',
'POINT(15.796760167739626 69.05714853429157)');

The incoming point is found to be below computed tolerance from the existing edge which wants then to be splitted by it. The code is unable to split the edge by the node.

Interesting, this query shows exactly the same problem:

=# select ST_AsText(ST_Split(
'LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837)'::geometry, 
'POINT(15.796760167739626 69.05714853429157)'::geometry));
                                                                   st_astext                                                                    
------------------------------------------------------------------------------------------------------------------------------------------------
 GEOMETRYCOLLECTION(LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837))
(1 row)

Even worse:

=# select st_astext(ST_PointN(e,2)), st_astext(st_split(e,st_pointn(e,2))) from ( select 'LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837)'::geometry e ) foo;
-[ RECORD 1 ]---------------------------------------------------------------------------------------------------------------------------------------------
st_astext | POINT(15.796760167739626 69.05714853429157)
st_astext | GEOMETRYCOLLECTION(LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837))

The above shows how ST_Split is unable to split a 3-vertices line by the central vertex.

[robe]

strk fwiw, on my

                                                     postgis_full_version
-------------------------------------------------------------------------------------------------------------------------------
 POSTGIS="3.1.9 95a641b" [EXTENSION] PGSQL="110" GEOS="3.10.3-CAPI-1.16.1" PROJ="7.2.1" LIBXML="2.9.1" LIBJSON="0.11" TOPOLOGY
(1 row)

select ST_AsText(ST_Split(
 'LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837)'::geometry,
'POINT(15.796760167739626 69.05714853429157)'::geometry));
                                                                   st_astext
------------------------------------------------------------------------------------------------------------------------------------------------
 GEOMETRYCOLLECTION(LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837))
(1 row)

select st_astext(ST_PointN(e,2)), st_astext(st_split(e,st_pointn(e,2))) from ( select 'LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837)'::geometry e ) foo;
[ RECORD 1 ]---------------------------------------------------------------------------------------------------------------------------------------------
st_astext | POINT(15.796760167739626 69.05714853429157)
st_astext | GEOMETRYCOLLECTION(LINESTRING(15.796760167740288 69.05714853429149,15.796760167739626 69.05714853429157,15.795906966300288 69.05725770093837))

So guess we need to go further back on GEOS version? I'll see if I can dig up a 3.9 or 3.6

[strk]

Bug is deep in lwgeom_split. WIP PR: ​https://git.osgeo.org/gitea/postgis/postgis/pulls/184

Regina thanks for testing, don't worry going back more for now, will go dive in code to see what's really going on.

[strk]

The problem ends up being in lwline_split_by_point_to using p4_same to check if two points are IDENTICAL while that function uses FP_EQUALS macro, for some reason I fail to understand at this moment.

We have two paths here: STOP using p4_same as known to be using fuzzy equality or fix p4_same and friends to stop doing that.

[strk]

An earlier commit in which I fixed the problems arising from those FP_EQUALS macros was [82acc2b19c244e52b796da648ad8abf803c19b9a/git] - exposing those P#D_SAME_STRICT macros to upper headers might be another solution, less traumatic

[Sandro Santilli <strk@…>]

In 5e5afc0/git:

Fix lwline_split_by_point_to determination of boundary points

Replaces tolerance-based p4d_same usage with the stricter
P4D_SAME_STRICT macro, now exposed in liblwgeom_internal.h

References #5698 in master branch (3.5.0dev)

Includes unit test

[strk]

As of [5e5afc046bb84c72b5c3831c455c86b2b5f53391/git] the initial testcase and all the subsequent all import without problems. The initial testcase results in a valid topology:

strk=# select * from validatetopology('tmp_dyrkbarjord_04_t3_a_test_issue_70_114');
NOTICE:  Checking for coincident nodes
NOTICE:  Checking for edges crossing nodes
NOTICE:  Checking for invalid or not-simple edges
NOTICE:  Checking for crossing edges
NOTICE:  Checking for edges start_node mismatch
NOTICE:  Checking for edges end_node mismatch
NOTICE:  Checking for faces without edges
NOTICE:  Checking edge linking
NOTICE:  Building edge rings
NOTICE:  Found 949 rings, 620 valid shells, 329 valid holes
NOTICE:  Constructing geometry of all faces
NOTICE:  Checking faces
NOTICE:  Checked 620 faces
NOTICE:  Checking for holes coverage
NOTICE:  Finished checking for coverage of 329 holes
NOTICE:  Checking for node containing_face correctness
 error | id1 | id2 
-------+-----+-----
(0 rows)

strk=# select topologysummary('tmp_dyrkbarjord_04_t3_a_test_issue_70_114');
                                   topologysummary                                   
-------------------------------------------------------------------------------------
 Topology tmp_dyrkbarjord_04_t3_a_test_issue_70_114 (id 249, SRID 4258, precision 0)+
 995 nodes, 1286 edges, 620 faces, 0 topogeoms in 0 layers                          +
 
(1 row)

[Sandro Santilli <strk@…>]

In 3d8226d/git:

Fix lwline_split_by_point_to determination of boundary points

Replaces tolerance-based p4d_same usage with the stricter
P4D_SAME_STRICT macro, now exposed in liblwgeom_internal.h

References #5698 in 3.4 branch (3.4.3dev)

Includes unit test for lwline_split_by_point_to
and regress test for TopoGeo_addPoint

[strk]

So it looks like this bug exists as back as 2.5. I'll only backport up to 3.3

[Sandro Santilli <strk@…>]

In 850982a/git:

Fix lwline_split_by_point_to determination of boundary points

Replaces tolerance-based p4d_same usage with the stricter
P4D_SAME_STRICT macro, now exposed in liblwgeom_internal.h

Closes #5698 in 3.3 branch (3.3.7dev)

Includes unit test for lwline_split_by_point_to
and regress test for TopoGeo_addPoint