Opened 3 years ago

Closed 3 years ago

Last modified 3 years ago

#3402 closed defect (fixed)

geometry crosses edges with 0 tolerance

Reported by: strk Owned by: strk
Priority: blocker Milestone: PostGIS 2.2.1
Component: topology Version: 2.1.x
Keywords: Cc:

Description

The attached .zip file contains a relatively small dataset that triggers an "edge-crosses-edge" exception when loaded in the PostGIS topology.

It's to be double-checked as I saw the exception raised by PostGIS-2.1 but not by PostGIS trunk (but I might have some local changes).

Attachments (3)

01-testing.zip (11.5 KB) - added by strk 3 years ago.
02-testing.zip (6.7 KB) - added by strk 3 years ago.
reduced case
test_selfcontained.sql (5.9 KB) - added by strk 3 years ago.
self-contained test (only using literals)

Download all attachments as: .zip

Change History (22)

Changed 3 years ago by strk

Attachment: 01-testing.zip added

comment:1 Changed 3 years ago by strk

Exception confirmed with:

POSTGIS="2.1.9dev r14472" GEOS="3.6.0dev-CAPI-1.10.0 r4129" PostgreSQL 9.3.6 on x86_64-unknown-linux-gnu, compiled by gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2, 64-bit

Changed 3 years ago by strk

Attachment: 02-testing.zip added

reduced case

comment:2 Changed 3 years ago by strk

Exception confirmed with:

POSTGIS="2.2.1dev r14497" GEOS="3.6.0dev-CAPI-1.10.0 r4129" PostgreSQL 9.3.6 on x86_64-unknown-linux-gnu, compiled by gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2, 64-bit

comment:3 Changed 3 years ago by strk

Exception also confirmed with GEOS \r4128 so before the GEOSSnap fix for https://trac.osgeo.org/geos/ticket/758

Changed 3 years ago by strk

Attachment: test_selfcontained.sql added

self-contained test (only using literals)

comment:4 Changed 3 years ago by strk

Further reduction:

SELECT CreateTopology('bug3402');                                               
SELECT TopoGeo_addLinestring('bug3402',                                         
'01020000000E0000001F85EB1117273941F6285CEFAC9652411F85EB1147283941F6285CEF599652411F85EB9172283941F6285CBF4A9652411F85EB910B283941F6285C6F429652411F85EB11E8273941F6285CFF3C9652411F85EBD1DD273941F6285C8F359652411F85EBD1E5273941F6285CFF309652411F85EB11F7273941F6285C5F2E9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C9652411F85EB914A283941F6285C7F269652411F85EBD101293941F6285C8F369652411F85EB51A428394100000070CF9652411F85EBD160273941000000E0DA965241'
, 0);                                                                           
SELECT TopoGeo_addLinestring('bug3402',                                         
'01020000000E000000295C8F0217273941A4703DEAAC9652416766662647283941295C8FF259965241E17A14AE72283941333333C34A96524148E17A940B2839413E0AD77342965241F6285C0FE82739411F85EB013D965241000000C0DD273941EC51B88E3596524152B81EC5E52739418FC2F5F8309652415C8FC2F5F627394152B81E652E96524148E17A5419283941713D0AF72D96524185EB51382828394115AE47D12C965241713D0A974A2839413E0AD7832696524115AE47E101293941000000903696524133333333A428394185EB5168CF965241A4703DCA6027394152B81EE5DA965241'
, 0);

comment:5 Changed 3 years ago by strk

Further reduction, 4 vertices each line:

SELECT DropTopology('bug3402');                                                 
SELECT CreateTopology('bug3402');                                               
SELECT TopoGeo_addLinestring('bug3402',                                         
'0102000000040000001F85EB1117273941F6285CEFAC9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C9652411F85EBD160273941000000E0DA965241'
, 0);                                                                           
SELECT TopoGeo_addLinestring('bug3402',                                         
'010200000004000000295C8F0217273941A4703DEAAC96524185EB51382828394115AE47D12C965241713D0A974A2839413E0AD78326965241A4703DCA6027394152B81EE5DA965241'
, 0);

comment:6 Changed 3 years ago by strk

Further, topology contains 4-vertices edge, a 2-vertices line fails to be inserted:

SELECT DropTopology('bug3402');                                                 
SELECT CreateTopology('bug3402');                                               
SELECT TopoGeo_addLinestring('bug3402', '0102000000040000001F85EB1117273941F6285CEFAC9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C9652411F85EBD160273941000000E0DA965241' , 0);
                                                                                
SELECT TopoGeo_addLinestring('bug3402',                                         
'010200000003000000BCAABC2B192739418F7DE0E6AB96524185EB51382828394115AE47D12C96524187EB51382828394115AE47D12C965241'
, 0); 

Both vertices of the line being inserted are on a segment of the existing edge, near one of its vertices (but no closer than computed tolerance).

comment:7 Changed 3 years ago by strk

I've just realized that the line being added has actually 3 vertices, not 2 ! The distance between the second and third point (4.65661287307739e-10) is lower than the computed working tolerance (1.7542368e-08)

comment:8 Changed 3 years ago by strk

Smaller case: existing 3-vertices edge, adding 3-vertices line:

SELECT DropTopology('bug3402');                                                 
SELECT CreateTopology('bug3402');                                               
SELECT TopoGeo_addLinestring('bug3402',                                         
'010200000003000000C1AABC2B192739418E7DE0E6AB9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C965241'
, 0);                                                                           
                                                                                
SELECT TopoGeo_addLinestring('bug3402',                                         
'010200000003000000BCAABC2B192739418F7DE0E6AB96524185EB51382828394115AE47D12C96524187EB51382828394115AE47D12C965241'
, 0); 

Removing the second vertex in the geometry being added does indeed fix the problem.

comment:9 Changed 3 years ago by strk

Adding the intersection point upfront also fixes the issue, suggesting that adding all intersection points first could be a good move. Same observation also made in https://trac.osgeo.org/postgis/ticket/3380#comment:3 (Ticket #3380 is also about presence of vertices within tolerance).

comment:10 Changed 3 years ago by strk

Even just adding a vertex on the existing edge where the intersection point would be, fixes the issue.

comment:11 Changed 3 years ago by strk

What I don't yet understand is how do edge crossing exactly happens. According to GEOS, these two edges cross:

010200000003000000C1AABC2B192739418E7DE0E6AB9652411F85EB5119283941F6285CEF2D96524187EB51382828394115AE47D12C965241
010200000003000000C1AABC2B192739418E7DE0E6AB96524185EB51382828394115AE47D12C96524187EB51382828394115AE47D12C965241

That is, they have a puntual interior-interior intersection according to GEOSRelate:

0F1F0F1F2

The first line geometry (call it A) is the existing edge. The second line geometry (call it B) is the line being added, with the tiny final segment.

The first and last points of the second line are equal to the first and last point of the first line:

=# select ST_Equals( ST_StartPoint(a), ST_StartPoint(b) ) from xx;
 st_equals 
-----------
 t
=# select ST_Equals( ST_EndPoint(a), ST_EndPoint(b) ) from xx;
 st_equals 
-----------
 t

So we have two lines each of 3 vertices. The start and end vertices are _the_same_. The second/middle vertex is NOT the same and not equal to any of the other two vertices:

=# select ST_Equals( ST_PointN(b,2), ST_PointN(a,2) ) from xx;
 st_equals 
-----------
 f
strk=# select ST_Equals( ST_PointN(b,2), ST_PointN(b,3) ) from xx;
 st_equals 
-----------
 f
(1 row)

strk=# select ST_Equals( ST_PointN(b,2), ST_PointN(b,1) ) from xx;
 st_equals 
-----------
 f
(1 row)

For confirmation, neither A covers middle point of B nor B covers middle-point of A:

strk=# select ST_Covers( a, ST_PointN(b,2) ) from xx;
 st_covers 
-----------
 f
(1 row)

strk=# select ST_Covers( b, ST_PointN(a,2) ) from xx;
 st_covers 
-----------
 f
(1 row)

So now the question is: how can A and B possibly have an Interior-Interior intersection ???

This sounds like a bug in GEOS.

Martin: any chance for you to try this case in JTS ? If GEOS Relate computer is wrong, this edge-crosses-edge error is a false positive !

comment:12 Changed 3 years ago by strk

Never mind, this is actually easily solved:

 *---o 
  \ /  
   X                                                                          
  / \ 
 *---o 

The "o" points are the common endpoints, the "x" is the interior-interior intersection, the "*" are the middle points of each line. So no GEOS bug here.

comment:13 Changed 3 years ago by strk

Just a note: the 4-vertices input had all vertices distance not less than 0.01 units:

0102000000040000001F85EB1117273941F6285CEFAC9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C9652411F85EBD160273941000000E0DA965241

Thus the 5e-10 distance vertex has been generated as part of the noding. For a computed tolerance of ~2e-8 such case should be avoided, and can be avoided by passing the noded input through ST_RemoveRepeatedPoint with a tolerance (or one day by using the new PrecisionModel? support in GEOS-3.5).

comment:14 Changed 3 years ago by strk

This PR fixes this ticket: https://github.com/postgis/postgis/pull/82 It changes the result of some other loading which needs to be carefully checked.

comment:15 Changed 3 years ago by strk

Priority: mediumblocker

comment:16 Changed 3 years ago by strk

Milestone: PostGIS 2.1.9PostGIS 2.2.1

comment:17 Changed 3 years ago by strk

Resolution: fixed
Status: newclosed

(In [14540]) Decimate lines on topology load

Improves snapping robustness

Updates expected results in topogeo_addlinestring for old and new snapping code (GEOS-3.3.8-, GEOS-3.3.9+)

Fixes #3402 and #3402, including automated tests for them.

comment:18 Changed 3 years ago by strk

(In [14542]) Decimate lines on topology load

Improves snapping robustness

Updates expected results in topogeo_addlinestring for old and new snapping code (GEOS-3.3.8-, GEOS-3.3.9+)

Fixes #3380 and #3402, including automated tests for them.

comment:19 Changed 3 years ago by strk

r14542 in 2.2 branch (2.2.1), r14540 in trunk (2.3.0)

Note: See TracTickets for help on using tickets.