Opened 7 years ago

Closed 6 years ago

Last modified 6 years ago

#3838 closed defect (fixed)

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

Reported by: Lars Aksel Opsahl Owned by: strk
Priority: medium Milestone: PostGIS 2.5.0
Component: topology Version: 2.3.x
Keywords: totopogeom, ERROR: XX000: SQL/MM Spatial exception - geometry crosses Cc: aperi

Description

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

Attachments (7)

Screen Shot 2017-09-09 at 11.28.36.png (36.9 KB ) - added by Lars Aksel Opsahl 7 years ago.
Picture of the polygons
Screen Shot 2017-09-09 at 13.53.55.png (44.7 KB ) - added by Lars Aksel Opsahl 7 years ago.
A picture of lines involved failed_test_2.sql
failed_test.sql (11.1 KB ) - added by Lars Aksel Opsahl 7 years ago.
Added create schema topo_ar5_forest and drop file if exists
failed_test_2.sql (28.0 KB ) - added by Lars Aksel Opsahl 7 years ago.
Added create schema topo_ar5_forest and drop file if exists
brokensnap.png (15.4 KB ) - added by strk 6 years ago.
Recursive topo snap
break_up_reduce_1.png (30.5 KB ) - added by Lars Aksel Opsahl 6 years ago.
Existing data and new line to add
break_up_reduce_2.png (45.6 KB ) - added by Lars Aksel Opsahl 6 years ago.
The result off adding the new line using breaking up single line pieces and zero tolerance

Download all attachments as: .zip

Change History (26)

by Lars Aksel Opsahl, 7 years ago

Picture of the polygons

comment:1 by Lars Aksel Opsahl, 7 years ago

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)

by Lars Aksel Opsahl, 7 years ago

A picture of lines involved failed_test_2.sql

comment:2 by Lars Aksel Opsahl, 7 years ago

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

by Lars Aksel Opsahl, 7 years ago

Attachment: failed_test.sql added

Added create schema topo_ar5_forest and drop file if exists

by Lars Aksel Opsahl, 7 years ago

Attachment: failed_test_2.sql added

Added create schema topo_ar5_forest and drop file if exists

comment:3 by Lars Aksel Opsahl, 7 years ago

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)

comment:4 by strk, 6 years ago

Status: newassigned

#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…

comment:5 by strk, 6 years ago

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);

comment:6 by strk, 6 years ago

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.

by strk, 6 years ago

Attachment: brokensnap.png added

Recursive topo snap

comment:7 by strk, 6 years ago

Cc: aperi added

See the damage made by snapper:

Recursive topo snap

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

comment:8 by strk, 6 years ago

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?)

by Lars Aksel Opsahl, 6 years ago

Attachment: break_up_reduce_1.png added

Existing data and new line to add

by Lars Aksel Opsahl, 6 years ago

Attachment: break_up_reduce_2.png added

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

comment:9 by Lars Aksel Opsahl, 6 years ago

Hi

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

The logic I tested , was that before I start i reduce the tolerance I 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.

Version 0, edited 6 years ago by Lars Aksel Opsahl (next)

comment:10 by pramsey, 6 years ago

Milestone: PostGIS 2.3.4PostGIS 2.3.5

comment:11 by Lars Aksel Opsahl, 6 years ago

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.

comment:12 by strk, 6 years ago

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.

comment:13 by strk, 6 years ago

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

comment:14 by strk, 6 years ago

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

comment:15 by strk, 6 years ago

The PR also fixes #1855

comment:16 by strk, 6 years ago

The PR also fixes #1946

comment:17 by strk, 6 years ago

Resolution: fixed
Status: assignedclosed

In 16037:

Add test for topology bug #3838

Shows previous commits fix #3838

comment:18 by strk, 6 years ago

Milestone: PostGIS 2.3.5PostGIS 2.5.0

comment:19 by Lars Aksel Opsahl, 6 years ago

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.

Note: See TracTickets for help on using tickets.