#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)
Change History (22)
Changed 5 years ago by
Attachment: | 01-testing.zip added |
---|
comment:1 Changed 5 years ago by
comment:2 Changed 5 years ago by
comment:3 Changed 5 years ago by
Exception also confirmed with GEOS \r4128 so before the GEOSSnap fix for https://trac.osgeo.org/geos/ticket/758
Changed 5 years ago by
Attachment: | test_selfcontained.sql added |
---|
self-contained test (only using literals)
comment:4 Changed 5 years ago by
Further reduction:
SELECT CreateTopology('bug3402'); SELECT TopoGeo_addLinestring('bug3402', '01020000000E0000001F85EB1117273941F6285CEFAC9652411F85EB1147283941F6285CEF599652411F85EB9172283941F6285CBF4A9652411F85EB910B283941F6285C6F429652411F85EB11E8273941F6285CFF3C9652411F85EBD1DD273941F6285C8F359652411F85EBD1E5273941F6285CFF309652411F85EB11F7273941F6285C5F2E9652411F85EB5119283941F6285CEF2D9652411F85EB5128283941F6285CCF2C9652411F85EB914A283941F6285C7F269652411F85EBD101293941F6285C8F369652411F85EB51A428394100000070CF9652411F85EBD160273941000000E0DA965241' , 0); SELECT TopoGeo_addLinestring('bug3402', '01020000000E000000295C8F0217273941A4703DEAAC9652416766662647283941295C8FF259965241E17A14AE72283941333333C34A96524148E17A940B2839413E0AD77342965241F6285C0FE82739411F85EB013D965241000000C0DD273941EC51B88E3596524152B81EC5E52739418FC2F5F8309652415C8FC2F5F627394152B81E652E96524148E17A5419283941713D0AF72D96524185EB51382828394115AE47D12C965241713D0A974A2839413E0AD7832696524115AE47E101293941000000903696524133333333A428394185EB5168CF965241A4703DCA6027394152B81EE5DA965241' , 0);
comment:5 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
Even just adding a vertex on the existing edge where the intersection point would be, fixes the issue.
comment:11 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
Priority: | medium → blocker |
---|
comment:16 Changed 5 years ago by
Milestone: | PostGIS 2.1.9 → PostGIS 2.2.1 |
---|
comment:17 Changed 5 years ago by
Resolution: | → fixed |
---|---|
Status: | new → closed |
Exception confirmed with: