Opened 8 years ago

Closed 8 years ago

Last modified 4 years ago

#615 closed defect (fixed)

ST_SymDifference triggers a crash in WKTWriter (?)

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

Description

For some obscure reason computing the SymDifference? between the geometries showed in here: http://trac.osgeo.org/postgis/ticket/2177

Results in a crash deep in WKTWriter (which should be unrelated).

There could be some bogus debug line around...

Change History (13)

comment:1 Changed 8 years ago by strk

It's an infinite loop entered while trying to fix invalidities produced by CommonBitsRemoval?. The code attempts a UnaryUnion? to fix, but the UnaryUnion? gets back to an invalidity

I'm surprised that UnaryUnion? doesn't drop the "too few points" geometry component:

CBR: result (after common-bits addition) is INVALID: Too few points in geometry component at or near point 16.570834296228949 46.516439037970301 (16.570834296228948546 46.516439037970300774)
CBR: result (after common-bits addition) fix_self_intersection (UnaryUnion)
CBR: result (after common-bits addition) is INVALID: Too few points in geometry component at or near point 16.570834296228949 46.516439037970301 (16.570834296228948546 46.516439037970300774)

comment:2 Changed 8 years ago by strk

It is curious to note that Union operation succeeds (but SymDifference? fails)

comment:3 Changed 8 years ago by strk

The offending geometry (portion) is this one:

01030000000100000007000000773A98D22192304099FAA9431D424740765F7CC2209230406643FDA024424740773A98D22192304098FAA9431D424740773A98D22192304097FAA9431D424740773A98D22192304096FAA9431D4247405EA791E509923040D3DDAD7E59424740773A98D22192304099FAA9431D424740

It's a simple polygon. One ring of 7 points. Only, it self-intersects: Self-intersection[16.5708285924579 46.5165180759406] And UnaryUnion? does NOT fix that

comment:4 Changed 8 years ago by strk

Buffer0 turns it to an EMPTY

comment:5 Changed 8 years ago by strk

ST_MakeValid (of PostGIS) also can't fix it (nut to crack!)

comment:6 Changed 8 years ago by strk

ST_Node can't correctly node it, so no way to polygonize. It's extent is (basically a point):

BOX(16.5704635124779 46.5165180759406,16.5708285924579 46.5183561657865)

Snapping its inputs to a grid of 1e-13 gives us something usable. 1e-14 isn't enough.

comment:7 Changed 8 years ago by strk

Looking at the log it's interesting to note that the loop isn't really infinite, but rather catches a self-intersection always at different places ! The X ordinate value of the reported intersection is always the same while the Y value seems to augment over time. Here's a short excerpt:

{{{{ CBR: removed-bits geom 1 is INVALID: Self-intersection at or near point 0.57082859245789663 0.51651807594703314 (0.57082859245789663305 0.51651807594703313953) CBR: removed-bits geom 1 is INVALID: Self-intersection at or near point 0.57082859245789663 0.51651807594704024 (0.57082859245789663305 0.51651807594704024496) ... CBR: removed-bits geom 1 is INVALID: Self-intersection at or near point 0.57082859245789663 0.51651807594735288 (0.57082859245789663305 0.51651807594735288376) ... ... CBR: removed-bits geom 1 is INVALID: Self-intersection at or near point 0.57082859245789663 0.51651807597061605 (0.57082859245789663305 0.51651807597061605293) }}}

Eventually, the stack limit is reached.

comment:8 Changed 8 years ago by strk

The previous comment wasn't formatted correctly. Here's another go:

(0.57082859245789663305 0.51651807594059562234)
(0.57082859245789663305 0.5165180759406098332)
(0.57082859245789663305 0.51651807594061693862)
(0.57082859245789663305 0.51651807594062404405)
(0.57082859245789663305 0.51651807594063114948)
(0.57082859245789663305 0.51651807594063825491)
(0.57082859245789663305 0.51651807594064536033)
(0.57082859245789663305 0.51651807594065246576)
(0.57082859245789663305 0.51651807594065957119)
(0.57082859245789663305 0.51651807594066667662)
...
(0.57082859245789663305 0.51651807597058052579)
(0.57082859245789663305 0.51651807597058763122)
(0.57082859245789663305 0.51651807597059473665)
(0.57082859245789663305 0.51651807597060184207)
(0.57082859245789663305 0.5165180759706089475)
(0.57082859245789663305 0.51651807597061605293)

I've 4225 _distinct_ numbers in there, in my log (killed before dying)

comment:9 Changed 8 years ago by strk

The segfault happens at iteration 9033 here. The final invalidity I see on removed-bits geom is:

Self-intersection at or near point 0.57082859245789663 0.51651807597262689 (0.57082859245789663305 0.51651807597262688887)

it's still the same X and the highest Y

comment:10 Changed 8 years ago by strk

Resolution: fixed
Status: newclosed

Alright I found a fix for this: running the UnaryUnion? _only_ when the given geometry is a multicomponent _and_ the invalidity found is an intersection between components (or a "too few points").

I'm not 100% sure that there's no way to enter the infinite recursion with these kind of invalidities but for now this bug is fixed. The only influence this change had on existing tests was that the test for #488 (which was found to expect a bogus result) is now giving a TopologyException?, like done by JTS itself. I think it's an acceptable change.

The fix is in r3750 for 3.3 branch and r3751 in master

comment:11 Changed 4 years ago by Sandro Santilli <strk@…>

In 89008dc/git:

Only attempt to fix self-intersection between multiple components

Doing this reduces the likelyhood of entering an infinite recursion
whereas UnaryUnion? (meant to fix that) would enter the self-intersection
attempt again. Fixes #615 for which a test is added.

This also gives us back an exception with the input of ticket #488,
which is the same behavior JTS exposes. The (bogus) test for it
is disabled by this commit.

git-svn-id: http://svn.osgeo.org/geos/trunk@3751 5242fede-7e19-0410-aef8-94bd7d2200fb

comment:12 Changed 4 years ago by Sandro Santilli <strk@…>

In 89008dc/git:

Only attempt to fix self-intersection between multiple components

Doing this reduces the likelyhood of entering an infinite recursion
whereas UnaryUnion? (meant to fix that) would enter the self-intersection
attempt again. Fixes #615 for which a test is added.

This also gives us back an exception with the input of ticket #488,
which is the same behavior JTS exposes. The (bogus) test for it
is disabled by this commit.

git-svn-id: http://svn.osgeo.org/geos/trunk@3751 5242fede-7e19-0410-aef8-94bd7d2200fb

comment:13 Changed 4 years ago by Sandro Santilli <strk@…>

In 89008dc/git:

Only attempt to fix self-intersection between multiple components

Doing this reduces the likelyhood of entering an infinite recursion
whereas UnaryUnion? (meant to fix that) would enter the self-intersection
attempt again. Fixes #615 for which a test is added.

This also gives us back an exception with the input of ticket #488,
which is the same behavior JTS exposes. The (bogus) test for it
is disabled by this commit.

git-svn-id: http://svn.osgeo.org/geos/trunk@3751 5242fede-7e19-0410-aef8-94bd7d2200fb

Note: See TracTickets for help on using tickets.