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:


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:

  1. load

  1. create a grid table: create table hgrid10 as select CDB_HexagonGrid(ST_MakeEnvelope(-180, -90, 180, 90), 10) as geom;
  2. create a topology out of it: select createtopology('hexagon_topo'); select ST_CreateTopoGeo('hexagon_topo', st_collect(geom)) from hgrid10;

Attachments (1)

topodia.png (11.5 KB ) - added by strk 12 years ago.

Download all attachments as: .zip

Change History (19)

comment:1 by strk, 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)

I just verified the error occurs also with toTopoGeom

comment:2 by strk, 12 years ago

Simpler input:


Can't use text or the error goes away

comment:3 by strk, 12 years ago



comment:4 by strk, 12 years ago

And smaller:


Can't get it smaller than this.

comment:5 by strk, 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 strk, 12 years ago

Well, smaller (not much, just homogenized):


comment:7 by strk, 12 years ago

Further analisys points to a singe line with 3 points:


The last 2 points are _very_ close togheter.

comment:8 by strk, 12 years ago

Ok, problem is ST_Azimuth returns NULL for these input points:


You can see the points are _not_ equal. ST_Distance returns 2.8421709430404e-14.

comment:9 by strk, 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:10 by strk, 12 years ago

Filed #1791 for the ST_Azimuth issue

comment:11 by strk, 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:

  1. Bad news: the topology is invalid
  2. Good news: ValidateTopology correctly detects the invalidity

This is with the very first input in comment 6

comment:12 by strk, 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 strk, 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 strk, 12 years ago

Here's the diagram of the resulting topology, with magnified adjacencies.

In true dimensions edges 1 and 2 are almost cohincident, as are edges 3 and 4. Nodes 1 and 2 are also very close as well as nodes 4 and 5 (making edge 5 very short).

by strk, 12 years ago

Attachment: topodia.png added

comment:15 by strk, 12 years ago

Summary: ST_CreateTopoGeo creates an invalid topologyST_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 strk, 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 strk, 12 years ago

a-ah! we use ST_DWithin with tolerance 0 rather than intersection matrix… see #1625

comment:18 by strk, 12 years ago

Resolution: fixed
Status: newclosed
Summary: ST_CreateTopoGeo creates an invalid topology ?False positive "edge crosses node"

Using ST_Within rather than ST_DWithin fixes the false positive (r9683). The bug in the original submission was fixed by r9682.

Note: See TracTickets for help on using tickets.