Context Navigation

← Previous Ticket
Next Ticket →

#5795 closed defect (fixed)

ST_NewEdgesSplit can cause invalid topology

Reported by:	Björn Harrtell	Owned by:	strk
Priority:	medium	Milestone:	PostGIS 3.5.1
Component:	topology	Version:	3.2.x
Keywords:		Cc:

Description

Seems like the is a bug in st_newedgessplit (if I use st_modedgessplit no invalidity is created). If I run this:

select topology.droptopology('test_topo');
select topology.createtopology('test_topo', 0, 0);
select topology.st_addisonode('test_topo', 0, st_geomfromtext('POINT(0 0)'));
select topology.st_addisonode('test_topo', 0, st_geomfromtext('POINT(10 10)'));
select topology.st_addisoedge('test_topo', 1, 2, st_geomfromtext('LINESTRING(0 0, 10 0, 10 10)'));
select topology.st_addedgenewfaces('test_topo', 2, 1, st_geomfromtext('LINESTRING(10 10, 0 10, 0 0)'));
select topology.st_newedgessplit('test_topo', 1, st_geomfromtext('POINT(5 0)'));
select * from topology.validatetopology('test_topo');

Results in:

invalid next_right_edge	2	-4

postgis_full_version:

POSTGIS="3.4.2 c19ce56" [EXTENSION] PGSQL="160" GEOS="3.12.1-CAPI-1.18.1" PROJ="9.4.0 NETWORK_ENABLED=OFF URL_ENDPOINT=https://cdn.proj.org USER_WRITABLE_DIRECTORY=/tmp/proj DATABASE_PATH=/usr/share/proj/proj.db" LIBXML="2.9.14" LIBJSON="0.17" LIBPROTOBUF="1.4.1" WAGYU="0.5.0 (Internal)" TOPOLOGY

Change History (13)

comment:1 by Björn Harrtell, 5 weeks ago

Looks like next_right_edge for edge 2 is set to -3 but should be -4.

comment:2 by Björn Harrtell, 5 weeks ago

Work in progress at https://github.com/postgis/postgis/pull/780, for now only test case reproduction.

comment:3 by Björn Harrtell, 5 weeks ago

Tentative fix now at https://github.com/postgis/postgis/pull/780 but needs more verification.

comment:4 by Björn Harrtell, 5 weeks ago

Expanding on the example to this:

select topology.droptopology('test_topo');
select topology.createtopology('test_topo', 0, 0);
select topology.st_addisonode('test_topo', 0, st_geomfromtext('POINT(0 0)'));
select topology.st_addisonode('test_topo', 0, st_geomfromtext('POINT(10 10)'));
select topology.st_addisoedge('test_topo', 1, 2, st_geomfromtext('LINESTRING(0 0, 10 0, 10 10)'));
select topology.st_addedgenewfaces('test_topo', 2, 1, st_geomfromtext('LINESTRING(10 10, 0 10, 0 0)'));
select topology.st_newedgessplit('test_topo', 1, st_geomfromtext('POINT(5 0)'));
select topology.st_newedgessplit('test_topo', 4, st_geomfromtext('POINT(10 5)'));
select topology.st_addedgenewfaces('test_topo', 3, 4, st_geomfromtext('LINESTRING(5 0, 10 5)'));
select topology.st_newedgessplit('test_topo', 7, st_geomfromtext('POINT(7.5 2.5)'));
select topology.st_newedgessplit('test_topo', 5, st_geomfromtext('POINT(10 2.5)'));
select topology.st_addedgenewfaces('test_topo', 5, 6, st_geomfromtext('LINESTRING(7.5 2.5, 10 2.5)'));

Cause "SQL Error [XX000]: ERROR: Backend error (no ring edges for edge -12): Corrupted topology: ring of edge -12 is topologically non-closed" both before and after fix, so fix is no good.

It can be reduced to:

select topology.droptopology('test_topo');
select topology.createtopology('test_topo', 0, 0);
select topology.st_addisonode('test_topo', 0, st_geomfromtext('POINT(0 0)'));
select topology.st_addisonode('test_topo', 0, st_geomfromtext('POINT(10 10)'));
select topology.st_addisoedge('test_topo', 1, 2, st_geomfromtext('LINESTRING(0 0, 10 0, 10 10)'));
select topology.st_addedgenewfaces('test_topo', 2, 1, st_geomfromtext('LINESTRING(10 10, 0 10, 0 0)'));
select topology.st_newedgessplit('test_topo', 1, st_geomfromtext('POINT(5 0)'));
select topology.st_newedgessplit('test_topo', 4, st_geomfromtext('POINT(10 5)'));
select topology.st_addedgenewfaces('test_topo', 3, 4, st_geomfromtext('LINESTRING(5 0, 10 5)'));
select topology.st_newedgessplit('test_topo', 7, st_geomfromtext('POINT(7.5 2.5)'));
select * from topology.validatetopology('test_topo');

Resulting in invalid "next_left_edge 5 -9" with fix and "invalid next_right_edge 2 -6".

comment:5 by Björn Harrtell, 5 weeks ago

Found another potential fix, is ready at https://github.com/postgis/postgis/pull/780.

comment:6 by strk, 5 weeks ago

Version:	3.4.x → 3.2.x

Corrupted topology errors are expected once the starting topology is invalid. I've tested this bug to exist also in PostGIS-3.2 so it would be nice to backport till there. I bet it's also in 3.0 but I cannot easily test that one.