geometry crosses edges with 0 tolerance

[strk]

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

[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

[strk]

reduced case

[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

[strk]

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

[strk]

self-contained test (only using literals)

[strk]

Further reduction:

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

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

[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).

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

[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.

[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).

[strk]

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

[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 !

[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.

[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).

[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.

[strk]

(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.

[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.

[strk]

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