Context Navigation

← Previous Ticket
Next Ticket →

#605 closed defect (fixed)

Crash from GEOSBuffer: RightmostEdgeFinder.cpp: Assertion `checked>0` failed

Reported by:	strk	Owned by:	geos-devel@…
Priority:	blocker	Milestone:	3.3.7
Component:	Default	Version:	3.3.6
Severity:	Critical	Keywords:
Cc:	history

Description

See http://lists.osgeo.org/pipermail/geos-devel/2012-December/006096.html

Attachments (1)

bug605.xml (1.1 KB ) - added by strk 11 years ago.

Download all attachments as: .zip

Change History (26)

comment:1 by strk, 11 years ago

Severity:	Unassigned → Critical

comment:2 by strk, 11 years ago

See also #473, same assertion there (but that specific case was fixed)

comment:3 by strk, 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:4 by strk, 11 years ago

JTS succeeds with the first reduction (scaleFactor 100000)

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

Using MCIndexSnapRounder rather than MCIndexNoder (as JTS does) fixes this case.

comment:7 by strk, 11 years ago

#544 might help here

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

Attachment:	bug605.xml added

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