Attachments (1)
Change History (26)
comment:1 by , 11 years ago
Severity: | Unassigned → Critical |
---|
comment:2 by , 11 years ago
comment:3 by , 11 years ago
Attempts to buffer with original precision fail with this:
TopologyException: assigned depths do not match at 366818.60878326674 6133401.6729513798
Then GEOS enters the precision reduction loop, starts with scaleFactor 100000 and reduces scale factor by 10 on every iteration. Every iteration fails with a similar TopologyException. The last one before the crash is with scaleFactor=1:
TopologyException: assigned depths do not match at 364550 6129605
When trying scale factor = 0.1 we get the crash.
I'm surprised that scale factor of 10 shows more than a single decimal digit in the topology exception:
TopologyException: assigned depths do not match at 364818.32000000001 6129887.71
comment:5 by , 11 years ago
So there seems to still be some state hold that shouldn't be, in that running directly with FixedPrecision and scale 100000 succeeds in GEOS too.
comment:6 by , 11 years ago
Using MCIndexSnapRounder rather than MCIndexNoder (as JTS does) fixes this case.
comment:8 by , 11 years ago
In any case the assertion means that there are NO forward edges in a BufferSubgraph, which is probably a robustness issue on its own (so may be worth a TopologyException). What do you think Martin ?
comment:9 by , 11 years ago
Reduced input still reproducing the bug:
LINESTRING( 365851.118627503 6133776.04159448, 366074.924340233 6134077.5652318, 375141.310137443 6138794.83236084, 373718.872489144 6137668.49630618, 373346.647541771 6137433.71166638, 366752.527028152 6134568.10150752, 360775.41757528 6127074.35479882, 360762.970983925 6127054.06482593, 365851.118627503 6133776.04159448, 366074.924340233 6134077.5652318, 366360.991546586 6134339.22803017, 366752.527028152 6134568.10150752, 373346.647541771 6137433.71166638, 373718.872489144 6137668.49630618, 375295.498589261 6138886.92620252, 373718.872489144 6137668.49630618, 373346.647541771 6137433.71166638, 366826.150471738 6134600.68215773, 366384.177071635 6134356.53424428, 365851.118627503 6133776.04159448, 364105.700770721 6130589.54564699, 360283.950543384 6126559.51325796, 356474.37159831 6124718.01769267, 356917.601431696 6124368.97007825, 360279.790154604 6126555.44586471, 364105.700770721 6130589.54564699, 365851.118627503 6133776.04159448, 364105.700770721 6130589.54564699, 360283.950543384 6126559.51325796, 356027.21875 6124543 )
comment:10 by , 11 years ago
Interesting enough, a further simplification of input forces JTS (current trunk) to get as low as precisionDigits 3 (scale factor 0.0001) before it gives an answer !
Full JTS session:
===== Test Runner - JTS Topology Suite (Version 1.13.0) ===== Reading test file /home/src/geos/geos/tests/xmltester/tests/ticket/bug605.xml Running tests... Trying with original precision Original precision failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (374252.3702753792, 6136822.694844382, NaN) ] Trying with precisionDigits 12 recomputing with precision scale factor = 100000.0 precisionDigits 12 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (374252.37062, 6136822.69508, NaN) ] Trying with precisionDigits 11 recomputing with precision scale factor = 10000.0 precisionDigits 11 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (373145.0804, 6138488.8817, NaN) ] Trying with precisionDigits 10 recomputing with precision scale factor = 1000.0 precisionDigits 10 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (366695.108, 6133235.285, NaN) ] Trying with precisionDigits 9 recomputing with precision scale factor = 100.0 precisionDigits 9 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (366095.54, 6132140.7, NaN) ] Trying with precisionDigits 8 recomputing with precision scale factor = 10.0 precisionDigits 8 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (373140.4, 6138485.9, NaN) ] Trying with precisionDigits 7 recomputing with precision scale factor = 1.0 precisionDigits 7 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (366694.0, 6133233.0, NaN) ] Trying with precisionDigits 6 recomputing with precision scale factor = 0.1 precisionDigits 6 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (366430.0, 6135520.0, NaN) ] Trying with precisionDigits 5 recomputing with precision scale factor = 0.01 precisionDigits 5 failed: com.vividsolutions.jts.geom.TopologyException: assigned depths do not match [ (375800.0, 6138000.0, NaN) ] Trying with precisionDigits 4 recomputing with precision scale factor = 0.001 precisionDigits 4 failed: com.vividsolutions.jts.geom.TopologyException: depth mismatch at (365000.0, 6133000.0, NaN) Trying with precisionDigits 3 recomputing with precision scale factor = 1.0E-4 Case bug605.xml - #1 (8): http://trac.osgeo.org/geos/ticket/605 Test Failed (A buffer 1000) ... Actual: POLYGON ((360000 6130000, 370000 6140000, 380000 6140000, 370000 6130000, 360000 6130000))
by , 11 years ago
Attachment: | bug605.xml added |
---|
comment:11 by , 11 years ago
I've attached an XML test for comparing JTS and GEOS against. The input is a further reduction. The expected output is actually unknown but JTS is clearly giving a bogus answer: http://strk.keybit.net/tmp/grossbuffer.png
comment:12 by , 11 years ago
Another hint: the problem in turn seems to originate in non-noded input being feeded to PlanarGraph. Pre-noding the input also seems to fix the case (in PostGIS: ST_Buffer(ST_Node(...), 1000))
comment:13 by , 11 years ago
Alright so I think it is a perfectly legit case of a dangling edge in the topology. If the node of degree 1 (the unconnected end) of the dangling edge is the _end_ vertex of the edge, eventually the BufferSubgraph create function will start from there and produce a subgraph of that edge _only_, and that edge will be backward. And in turn that'll take us to the exception.
comment:14 by , 11 years ago
Forget the above comment, theoretically the dangling edges would be part of the same SubGraph as the other.
Adding more logging I do see weird things in the built planargraph, like this snippet:
Adding node 366650 6133180 backward edge (366700 6133200, 366650 6133180) backward edge (366700 6133300, 366650 6133180) forward edge (366650 6133180, 366520 6133030, 366360 6132920, 366190 6132830, 366000 6132790, 365800 6132780, 365610 6132810, 365420 6132870, 365260 6132970, 365110 6133100, 364990 6133260, 364910 6133440, 364860 6133630, 364900 6133800) ...
Sounds like there are 2 identical backward edges attached to that node ...
comment:15 by , 11 years ago
Instrumented the Subgraph generation with more checks and I found a case of duplicated edge:
Adding node 361600 6126500 backward edge (364830 6129900, 361600 6126500) backward edge (366100 6132100, 361600 6126500) backward edge (366650 6133180, 366650 6133170, 361600 6126500) backward edge (361600 6126500, 361620 6126560, 361630 6126550, 361620 6126530, 361600 6126500) sym node 361600 6126500 visited forward edge (361600 6126500, 361620 6126560, 361630 6126550, 361620 6126530, 361600 6126500) EQUALS previous edge!
It should never happen, right ?
comment:16 by , 11 years ago
The EQUAL case was indeed fine, as that's a closed edge starting and ending on the same node.
comment:17 by , 11 years ago
What I'm trying to understand is how it is possible to obtain only backward edges by walking all reachable _directed_ edges starting from any node, as this is what's happening here.
comment:18 by , 11 years ago
About the grossbuffer.png image I posted above: that images shows a buffer performed on a precision grid of 10000 units per side, that why it looks so weird. It would be enough to limit the precisionModel to a fraction of max extent to avoid that broken result (better an exception there...)
comment:19 by , 11 years ago
r3727 in trunk implements throwing a TopologyException rather than aborting. Has to be backported to 3.3 branch but first I wanted to further limit the precision reduction to avoid gross results
comment:20 by , 11 years ago
r3728 takes a step forward by reducing the input coordinates (snapping them to the reduced precision grid). Good results ! http://strk.keybit.net/tmp/goodbuffer.png
Unfortunately the GeometryPrecisionReducer class isn't in the 3.3 branch so the fix can't backport there that easily.
comment:21 by , 11 years ago
Resolution: | → fixed |
---|---|
Status: | new → closed |
r3730 ports the TopologyException to 3.3 branch, fixing the abort (but not the buffer result).
comment:22 by , 11 years ago
Cc: | added |
---|
See also #473, same assertion there (but that specific case was fixed)