Opened 12 years ago
Closed 12 years ago
#1789 closed defect (fixed)
False positive "edge crosses node"
Reported by: | strk | Owned by: | strk |
---|---|---|---|
Priority: | medium | Milestone: | PostGIS 2.0.1 |
Component: | topology | Version: | 2.0.x |
Keywords: | Cc: |
Description
I was playing with hexagon grids and knowing irrational numbers approximation would have introduced slight discrepancies I thought to take a look using PostGIS topology.
To be honest I did expect problems
Well, here's the problem: ERROR: Invalid edge (no two distinct vertices exist)
To reproduce:
- load
https://github.com/Vizzuality/cartodb/blob/develop/lib/sql/CDB_Hexagon.sql
- create a grid table: create table hgrid10 as select CDB_HexagonGrid(ST_MakeEnvelope(-180, -90, 180, 90), 10) as geom;
- create a topology out of it: select createtopology('hexagon_topo'); select ST_CreateTopoGeo('hexagon_topo', st_collect(geom)) from hgrid10;
Attachments (1)
Change History (19)
comment:1 by , 12 years ago
Summary: | ST_CreateTopoGeo: ERROR: Invalid edge (no two distinct vertices exist) → ST_CreateTopoGeo, toTopoGeom: ERROR: Invalid edge (no two distinct vertices exist) |
---|
comment:2 by , 12 years ago
Simpler input:
0106000000020000000103000000010000000700000000000000004065C0031AD965BE5554C00000000000E065C000000000008056C0FFFFFFFFFF1F67C001000000008056C00000000000C067C0051AD965BE5554C001000000002067C00734B2CB7C2B52C00200000000E065C00434B2CB7C2B52C000000000004065C0031AD965BE5554C00103000000010000000700000000000000006063C000000000008056C000000000000064C0FDE5269A41AA58C0FFFFFFFFFF3F65C0FEE5269A41AA58C00000000000E065C002000000008056C001000000004065C0041AD965BE5554C002000000000064C0011AD965BE5554C000000000006063C000000000008056C0
Can't use text or the error goes away
comment:3 by , 12 years ago
Smaller:
01050000000200000001020000000500000000000000004065C0031AD965BE5554C00000000000E065C000000000008056C0FFFFFFFFFF1F67C001000000008056C00200000000E065C00434B2CB7C2B52C000000000004065C0031AD965BE5554C0010200000004000000FFFFFFFFFF3F65C0FEE5269A41AA58C00000000000E065C002000000008056C001000000004065C0041AD965BE5554C002000000000064C0011AD965BE5554C0
comment:4 by , 12 years ago
And smaller:
0107000000020000000105000000010000000102000000030000000000000000E065C002000000008056C001000000004065C0041AD965BE5554C002000000000064C0011AD965BE5554C001050000000100000001020000000200000000000000004065C0031AD965BE5554C00000000000E065C000000000008056C0
Can't get it smaller than this.
comment:5 by , 12 years ago
For the record: the CDB_HexGrid now snaps to a grid to perfectly match hexagons, so can't use the current version for testing anymore. The simplified inputs in previous comments are still good to trigger the issue
comment:6 by , 12 years ago
Well, smaller (not much, just homogenized):
0105000000020000000102000000030000000000000000E065C002000000008056C001000000004065C0041AD965BE5554C002000000000064C0011AD965BE5554C001020000000200000000000000004065C0031AD965BE5554C00000000000E065C000000000008056C0
comment:7 by , 12 years ago
Further analisys points to a singe line with 3 points:
01020000000300000000000000009865C04FE5D4AD958655C001000000004065C0041AD965BE5554C000000000004065C0041AD965BE5554C0
The last 2 points are _very_ close togheter.
comment:8 by , 12 years ago
Ok, problem is ST_Azimuth returns NULL for these input points:
010100000000000000004065C0041AD965BE5554C0 010100000001000000004065C0041AD965BE5554C0
You can see the points are _not_ equal. ST_Distance returns 2.8421709430404e-14.
comment:9 by , 12 years ago
note that azimuth is used to order edge ends around a node. There's probably a more robust way to do that (as done in GEOS/JTS) but before going there it'll be useful to remove some code duplication (the same azimuth-based code is in ST_AddEdgeModFace and ST_AddEdgeNewFace, and a similar one is in GetNodeEdges)
comment:11 by , 12 years ago
Summary: | ST_CreateTopoGeo, toTopoGeom: ERROR: Invalid edge (no two distinct vertices exist) → ST_CreateTopoGeo creates an invalid topology |
---|
Alright so with #1791 closed ST_CreateTopoGeo succeeds at creating the topology. BUT:
- Bad news: the topology is invalid
- Good news: ValidateTopology correctly detects the invalidity
This is with the very first input in comment 6
comment:12 by , 12 years ago
Funny: magnifying the topology (scaling nodes and edges by 1e14) makes ValidateTopology happy. Trying to "manually" validate the topology I didn't find any obvious problem.
The validation with original (non scaled) topology was reporting an edge crossing a node, but I couldn't confirm _visually_. Looking too much visually also hurts (qgis segfaulted…) so will have to recheck in some better way.
comment:13 by , 12 years ago
Oh, btw, my "Bad news" above was based on being cheated by visually looking at things. After enough zoom in I saw no invalidity. Will attach a diagram of the resulting topology.
comment:14 by , 12 years ago
by , 12 years ago
Attachment: | topodia.png added |
---|
comment:15 by , 12 years ago
Summary: | ST_CreateTopoGeo creates an invalid topology → ST_CreateTopoGeo creates an invalid topology ? |
---|
As you can see the topology is good. So I guess the pointer goes back to pre-scaled topology and inspecting of whether ValidateTopology is mistaken!
comment:16 by , 12 years ago
So, validity issue report is: ("edge crosses node",2,1) But:
=# select st_relate(e.geom, n.geom), st_crosses(e.geom, n.geom) from t0.edge e, t0.node n where e.edge_id = 2 and n.node_id = 1; st_relate | st_crosses -----------+------------ FF1FF00F2 | f (1 row)
comment:17 by , 12 years ago
a-ah! we use ST_DWithin with tolerance 0 rather than intersection matrix… see #1625
comment:18 by , 12 years ago
Resolution: | → fixed |
---|---|
Status: | new → closed |
Summary: | ST_CreateTopoGeo creates an invalid topology ? → False positive "edge crosses node" |
I just verified the error occurs also with toTopoGeom