[postgis-users] ST_Intersection Problems

[Sandro Santilli]

On Thu, Jul 11, 2013 at 10:09:58PM -0400, BladeOfLight16 wrote:
> TL;DR Version:
> 
> ST_Intersection is blowing up with errors about "non-noded intersections"
> and "no outgoing dirEdge" on my polygons. A bunch of sordid details about
> my data later, what can I try to make it stop throwing TopologyExceptions?

1) Make sure all your input geometries are valid (ST_IsValid, ST_MakeValid)
2) Upgrade to latest interim GEOS version (3.3.9dev r3828 is a good choice)
3) Try reducing almost-equal-but-not-really situations
   (ST_Segmentize, ST_SnapToGrid) 
4) If all of the above fails, isolate the smallest input triggering the
   problem and report it into a bug report on http://trac.osgeo.org/geos

Good luck !

(Notes on the gory details below)

> Some gory details:
> 
> The data I have comes from GPS, and it hasn't been cleaned up very much (if
> at all). Blame my client for that; I don't have any control over that end
> of things. Rather, I'm doing a lot of processing on that front. I'm calling
> ST_IsValid on every polygon that comes into the database, and if
> ST_MakeValid doesn't fix a bad shape, the shape doesn't make it into the
> database or is removed. So anything that isn't valid according to
> ST_IsValid either doesn't make it to the database or gets removed. (It's a
> Python scripted import process from shapefiles using GDAL 1.9.2.)
> 
> Anyway, I keep getting TopologyExceptions when intersecting multipolygons.
> The main one I've seen is "Found a non-noded intersection" between two line
> segments. Sometimes, it reports a pair of line segments that are identical
> (same pair of endpoints) or with all 4 endpoints the same. I suppose it
> could be rounding them off before printing them out, but I'm not sure. I

It necessarely rounds off for printing. Real coordinate values are 64bit
floating points.

> know my data isn't great, but it seems to me that ST_Intersection should be
> able to deal with non-noded intersecting boundaries on a pair of polygons
> that are known to be valid even if there really are non-identical line
> segments here. I've also just seen a new error about "no outgoing dirEdge".
> I'm pretty sure these exceptions bubble up from GEOS. I can't imagine that
> ST_Intersection is just this broken, but I don't know what could be wrong
> with my data. Are the errors saying that my input polygons are invalid? I
> don't even know what "no outgoing dirEdge" means. I've worked around some
> of these problems by trying out various processing functions, but they seem
> to keep cropping up on new shapes all the time.

All the errors you report come from GEOS.
The "no outgoing dirEdge" one is likely due to invalid input, but the
invalid input may be produced internally by GEOS itself. There are
known cases like this on trac. You can get more details about the failure
rebuilding GEOS with GEOS_DEBUG_BINARYOP defined
(see include/geos/geom/BinaryOp.h)

> At one time, I tried upgrading to a nightly build of GEOS 3.4, but since
> that didn't solve my "non-noded intersection" errors at the time, I
> abandoned it. At that time, the errors were coming from ST_Union on a bunch
> of line work, in fact. When upgrading didn't work, I ended up taking my
> line work, breaking it down into individual segments (as in 2 points per
> segment), and eliminating duplicate line segments (according to ST_Equals).
> After that, the union worked, which strengthens the argument that the
> problem has to do with duplicate line segments somewhere, at least in my
> mind.

They were probably almost identical but not really so.
Next time keep them around, but have them printed in HEXWKB form to avoid
the roundoff.

--strk;

 http://www.cartodb.com - Map, analyze and build applications with your data

                                       ~~ http://strk.keybit.net