topology.toTopoGeom fails with ERROR: XX000: SQL/MM Spatial exception - geometry crosses, when using tolerance 10 meter

[Lars Aksel Opsahl]

Hi

I am working on a case where I am testing Postgis Topology for merging new data from satellite images into a existing vector layer. The basic idea new is that new lines should snap to to existing lines based on given tolerance.

I have reduced the problem down staring with one geometry object and the adding a new object that we want adjust to the existing polygon like this.

I start with a empty layer and adds a linestring (the pink one)

select topology.toTopoGeom('0102000020E864000032..', 'topo_ar5_forest_sysdata', '1', '1');

Then I have a new linestring (the red dotted) that intersects first geo but I want use snapTo to avoid duplicated lines so I use snapto like this.

select topology.toTopoGeom('0102000020E864000019..', 'topo_ar5_forest_sysdata', '1', '10');

Then I get this error :

ERROR: XX000: SQL/MM Spatial exception - geometry crosses edge 12 CONTEXT: PL/pgSQL function totopogeom(geometry,topogeometry,double precision) line 114 at FOR over SELECT rows PL/pgSQL function totopogeom(geometry,character varying,integer,double precision) line 89 at assignment LOCATION: pg_error, lwgeom_pg.c:164

In this case it seems to work OK with for instance with 1 meter and 5 meter as tolerance, but I need to use 10 meter in this case. Both objects are valid. A bug that looks something like is discussed in ​https://trac.osgeo.org/postgis/ticket/1641 .

Attached is a sql that produce this error and image that show involved polygons.

Is i doing something wrong here or is this a bug.

Thanks

Lars

[Lars Aksel Opsahl]

Picture of the polygons

[Lars Aksel Opsahl]

SELECT PostGIS_Full_Version();

postgis_full_version

---

POSTGIS="2.3.0 r15146" GEOS="3.6.1-CAPI-1.10.1 r0" PROJ="Rel. 4.9.3, 15 August 2016" GDAL="GDAL 1.11.5, released 2016/07/01" LIBXML="2.9.4" LIBJSON="0.12" TOPOLOGY RASTER

(1 row)

[Lars Aksel Opsahl]

A picture of lines involved failed_test_2.sql

[Lars Aksel Opsahl]

Test 2 fails with another message.

XX000: Invalid edge (no two distinct vertices exist) CONTEXT: PL/pgSQL function totopogeom(geometry,topogeometry,double precision) line 114 at FOR over SELECT rows PL/pgSQL function totopogeom(geometry,character varying,integer,double precision) line 89 at assignment LOCATION: pg_error, lwgeom_pg.c:164

[Lars Aksel Opsahl]

Added create schema topo_ar5_forest and drop file if exists

[Lars Aksel Opsahl]

Added create schema topo_ar5_forest and drop file if exists

[Lars Aksel Opsahl]

Tested with postgis 2.3.4dev and the problem seems be the same there also

SELECT name, default_version,installed_version
FROM pg_available_extensions WHERE name LIKE 'postgis%' or name LIKE 'address%';
             name             | default_version | installed_version 
------------------------------+-----------------+-------------------
 address_standardizer         | 2.3.0           | [NULL]
 address_standardizer_data_us | 2.3.0           | [NULL]
 postgis                      | 2.3.4dev        | 2.3.4dev
 postgis_sfcgal               | 2.3.4dev        | [NULL]
 postgis_tiger_geocoder       | 2.3.0           | [NULL]
 postgis_topology             | 2.3.4dev        | 2.3.4dev
(6 rows)

[strk]

#1641 was about not tolerating drifts, this one seems to be the contrary: snapping too much.

I can reproduce with:

POSTGIS="2.5.0dev r15937" [EXTENSION] PGSQL="96" GEOS="3.7.0dev-CAPI-1.11.0 6daf6f83" PROJ="Rel. 4.9.3, 15 August 2016" GDAL="GDAL 2.3.0dev, released 2017/99/99" LIBXML="2.9.4" LIBJSON="0.12.1" LIBPROTOBUF="1.2.1" TOPOLOGY RASTER

Interesting enough, using tolerance 10 in the first call makes it pass, reinforcing my belief that a fixed grid works better than a moving one...

[strk]

Further simplified version of testcase:

select topology.droptopology('bug3838');
select CreateTopology('bug3838');

select TopoGeo_addLinestring('bug3838',
'LINESTRING(622617.12 6554996.14,
622612.06 6554996.7, 622609.17 6554995.51,
622606.83 6554996.14, 622598.73 6554996.23,
622591.53 6554995.96)'
, 1);

select topology.TopoGeo_addLinestring('bug3838',
'LINESTRING(622608 6554988, 622596 6554984)'
, 10);

[strk]

Relevant debug lines:

DEBUG:  [lwgeom_topo.c:_lwt_AddLine:5691] Working tolerance:10
DEBUG:  [lwgeom_topo.c:_lwt_AddLine:5706] Noded: LINESTRING(622608 6554988,622596 6554984)
DEBUG:  [lwgeom_topo.c:_lwt_toposnap:451] It took 4/6 iterations to properly snap
DEBUG:  [lwgeom_topo.c:_lwt_AddLine:5759] Snapped: LINESTRING(622591.53 6554995.96,622598.73 6554996.23,622606.83 6554996.14,622609.17 6554995.51,622617.12 6554996.14,622612.06 6554996.7,622596 6554984)

Basically the recursive snapping with a tolerance of 10 ends up snapping to 4 of the 6 vertices in the intersecting edge, generating an invalid edge.

[strk]

Recursive topo snap

[strk]

See the damage made by snapper:

It may help to rewrite the snapping algorithm, maybe porting portions of ​https://git.osgeo.org/gogs/rttopo/librttopo/src/master/src/rtt_tpsnap.c

[strk]

We're effectively having a kind of a bogus call, in that a tolerance of 10 units is requested while there are geometries entered that have vertices closer than 10 units between themselves, which make the requested precision NOT respected. I'm thinking what we could do here is either raise an error mentioning that the present topology has a denser grid or we could lower the tolerance ourselves internally upon hitting a robustness issue (excessive snapping?)

[Lars Aksel Opsahl]

Existing data and new line to add

[Lars Aksel Opsahl]

The result off adding the new line using breaking up single line pieces and zero tolerance

[Lars Aksel Opsahl]

Hi

I have tested something like this (see attachments just added).

The logic I tested , was that before I start to reduce the tolerance, I try to add simple pieces of lines like this.

1) If I get a exception I try to adde each single piece of the line. This means that if the line has 5 points, I try add 4 line pieces in a separate operations using the original tolerance.

2) If I still get a exception on a line piece with only 2 points, the I try to reduce the tolerance in steps 1 meter down to zero meter.

With this approach I also fails to add all lines, here is description of the attachments above.

I start with this break_up_reduce_1 (light yellow existing data, red new lines add)

The I get this result break_up_reduce_2.png (The green lines are valid edges, the light red dotted lines are line pieces that I failed to add)

After using the approach above I end with non closed polygons because I fails to add the red red dotted part of the new data, so I end with a non closed polygons.

So for me it seems fail even if I add a single line with two points and tolerance 0. It does not happen often but it happens.

[Lars Aksel Opsahl]

The case where we have less distance between the points in the data and input, than the tolerance we use is quite important to handle, because we get data from different sources. One source we use is users who are actually drawing on the screen, in this case we testing input based on images. The data we are updating are mostly in it's original form draw by user using in some way.

[strk]

The point is: if you tolerate 10 meters, you should not allow lines with points closer than 10 meters each other. Those lines, even if drawn by users, can be cleaned up before being sent to the topology, using ST_RemoveRepeatedPoints or ST_Simplify. An already-built topology can also be cleaned to a target tolerance by using the same functions and ST_ChangeEdgeGeom.

That said, the snapping method used during topology building (implemented in GEOS) is not stable enough, so it would be useful to rewrite it.

[strk]

My work in progress is now also a merge request on GitLab mirror: ​https://gitlab.com/postgis/postgis/merge_requests/4

[strk]

As of commit 0911624e7570fb026cea56772ac746e64bf3a457 the merge request fixes both failed_test.sql and failed_test_2.sql in addition to my simplified reduction above *and* ticket #3718

[strk]

The PR also fixes #1855

[strk]

The PR also fixes #1946

[strk]

In 16037:

Add test for topology bug #3838

Shows previous commits fix #3838

[Lars Aksel Opsahl]

Thanks starting to be more robust now so I did a bigger test with the new code.

I started with a simple feature data set of 92746 polygons (11657424 points) and another dataset of 8754 polygons (846345 points). Then I convert both data sets to Postgis Topology and then I try to merge the small data set into big data by using snapto in Postgis Topology. I then get problem with for 747 of these points. Most of this errors will not cause problems for the because we already have line there, but some failing snapto will cause polygons not to close .

I will create new bug report with more example.