TopologyException for Valid geoemtries

[bladeoflight16]

I have 2 supposedly valid geometries. When I try to take the difference between them:

WITH geom1 (g) AS (VALUES(ST_GeomFromEWKB(DECODE($$AQYAACAjaQAAAwAAAAEDAAAAAQAAAAkAAAB28/KWa9oWQSePXfN2Q1JBqrU4RG7aFkGksIr/f0NS
QazxLppr2hZBGx9M/nZDUkGh1GSca9oWQffnBv52Q1JBPKwR52vaFkEY6B74dkNSQTbQvkJs2hZB
3Q0983ZDUkHFuN1EbNoWQVwaKvN2Q1JBgorsxi3bFkH9c+m5dkNSQXbz8pZr2hZBJ49d83ZDUkEB
AwAAAAEAAAANAAAAKu2ZA3PaFkFrK3ILkENSQXU40QZz2hZBltlQFpBDUkGL2P81BdwWQV8rUp+P
Q1JBAN7DMgXcFkFPnWOUj0NSQVoEjjAF3BZBT9OolI9DUkFzLuHlBNwWQQjTkJqPQ1JB+gw0igTc
FkEqrXKfj0NSQWstFYgE3BZBW6CFn49DUkGkWbq1c9oWQVAZHRaQQ1JB1NJmsXPaFkF6uvkVkENS
QVXR5lJz2hZB8+xOEZBDUkHbKskEc9oWQZUalAuQQ1JBKu2ZA3PaFkFrK3ILkENSQQEDAAAAAQAA
AAcAAADqJmDJ/dsWQdMPPod2Q1JBvt4oxv3bFkHDYV98dkNSQY2/Pxf92xZBzyGTfHZDUkEbRZMb
/dsWQZ2Atnx2Q1JBA0UTev3bFkE/TmGBdkNSQaHpMMj92xZBsyAch3ZDUkHqJmDJ/dsWQdMPPod2
Q1JB$$, 'base64')))),
geom2 (g) AS (VALUES(ST_GeomFromEWKB(DECODE($$AQMAACAjaQAAAQAAABUAAACs/bu0c9oWQZJkHRaQQ1JBLBWdsnPaFkETWDAWkENSQcny71Zz2hZB
bDISG5BDUkEaHUMMc9oWQWQy+iCQQ1JBOjoNCnPaFkGJaT8hkENSQTBygHN62hZB/7NlLqlDUkHq
r690etoWQSijhy6pQ1JBQljNwnraFkFtdUI0qUNSQUVbTSF72hZB1ULtOKlDUkEY4qAle9oWQamh
EDmpQ1JBc2b09wvcFkFWqHjCqENSQfNFE/oL3BZBJbVlwqhDUkHVZcBVDNwWQeXag72oQ1JB0Dlt
oAzcFkET25u3qENSQVoTo6IM3BZBE6VWt6hDUkE/JDc5BdwWQW3ZMKqPQ1JB6eYHOAXcFkFN6g6q
j0NSQW1A6ukE3BZB8xdUpI9DUkEAP2qLBNwWQXBKqZ+PQ1JBYrkWhwTcFkGk64Wfj0NSQaz9u7Rz
2hZBkmQdFpBDUkE=$$, 'base64'))))
--SELECT ST_IsValidDetail(geom1.g), ST_IsValidDetail(geom2.g)
SELECT ST_Difference(geom1.g, geom2.g)
FROM geom1, geom2;

(Sorry for all the nasty base64. I wanted to make sure they come through exactly. You can leave the whitespace there in PostgreSQL. DECODE strips it out it properly; in fact, ENCODE is what generated it.)

I get the following error:

ERROR: GEOSDifference: TopologyException: found non-noded intersection between LINESTRING (374438 4.78778e+06, 374529 4.78777e+06) and LINESTRING (374529 4.78777e+06, 374466 4.78778e+06) at 374526.95988686144 4787774.5327140652
SQL state: XX000

You can confirm that they're reported as valid geometries by commenting/uncommenting the SELECT lines appropriately.

Note that the geom1 geometry is actually the output from a different, successful ST_Difference, so it's not actually valid, there's a bug in what it outputs.

If you pull up the geometries, you'll find this is not squeaky clean data. It comes from data that is taken over several years, and for every year, I need to figure out what the most current data is. Sometimes the data is retaken, so I need to cut out old overlaps but bring in data from new locations. I've done a ton of work trying to automatically clean this data some, but I still run into these errors all the time. Expect more reports as I run into them.

I assumed this is a GEOS problem based on the error message. If not, I will happily report elsewhere.

Full PostGIS version, if it's of any help or I should look at upgrading anything:

POSTGIS="2.1.4 r12966" GEOS="3.4.2-CAPI-1.8.2 r3921" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.9.2, released 2012/10/08" LIBXML="2.7.6" LIBJSON="UNKNOWN" TOPOLOGY RASTER

GEOS is the latest version, in spite of PostGIS being a little bit behind. I was trying to reproduce with a newer version of PostGIS, but PostgreSQL's apt repository contains an outdated GEOS. I don't have time right now to install all that again, but it is worth noting that this issue does not reproduce on GEOS 3.3.3. (Full version of that install is POSTGIS="2.1.7 r13414" GEOS="3.3.3-CAPI-1.7.4" PROJ="Rel. 4.7.1, 23 September 2009" GDAL="GDAL 1.9.0, released 2011/12/29" LIBXML="2.8.0" LIBJSON="UNKNOWN" RASTER.)

[bladeoflight16]

Sorry. That should read "so if it's not actually valid". I can't modify the description, apparently.

[strk]

The inputs in WKT form (confirmed to still trigger the exception):

 MULTIPOLYGON(((374426.89741116 4787675.8025854,374427.56662258 4787711.99283997,374426.900569702 4787675.97339609,374426.902728388 4787675.96917152,374426.975653354 4787675.87688639,374427.06518102 4787675.80060145,374427.067252051 4787675.79944476,374475.444261707 4787674.90487385,374426.89741116 4787675.8025854)),((374428.75351687 4787776.17884336,374428.756657488 4787776.34868469,374529.302733787 4787774.48939022,374529.299575299 4787774.31857999,374529.297416752 4787774.32280429,374529.224491812 4787774.41508938,374529.134964183 4787774.49137429,374529.132893285 4787774.49253091,374428.927468682 4787776.34552605,374428.923243803 4787776.34336721,374428.830958625 4787776.27044224,374428.754673643 4787776.18091454,374428.75351687 4787776.17884336)),((374527.446655853 4787674.11316295,374527.443515282 4787673.94332165,374527.272704118 4787673.94648023,374527.276928978 4787673.94863906,374527.369214133 4787674.02156407,374527.445499087 4787674.11109178,374527.446655853 4787674.11316295)))

 POLYGON((374428.926498378 4787776.345544,374428.924427348 4787776.34670069,374428.834899705 4787776.42298565,374428.761974768 4787776.5152708,374428.759816084 4787776.51949538,374430.61279467 4787876.72495747,374430.613951443 4787876.72702865,374430.690236453 4787876.81655632,374430.782521654 4787876.88948127,374430.786746533 4787876.89164011,374530.99214325 4787875.03861435,374530.994214147 4787875.03745774,374531.083741752 4787874.96117279,374531.156666663 4787874.86888768,374531.158825209 4787874.86466338,374529.305874411 4787774.65923153,374529.304717644 4787774.65716035,374529.228432662 4787774.56763266,374529.136147484 4787774.49470769,374529.131922623 4787774.49254886,374428.926498378 4787776.345544))

[strk]

Ticket retargeted after milestone deleted

[strk]

Ticket retargeted after milestone closed

[strk]

Ticket retargeted after milestone closed

[robe]

Confirmed still a problem.

[mdavis]

JTS reports that the first geometry is INVALID - at least, the WKT representation.

These are pretty tough geometries to work with - they have many extremely narrow spikes. Probably the way to handle these is to reduce precision slightly and snap the spikes off. It's a good example to research how this can be handled automatically (perhaps by overlay with a precision model).

[mdavis]

Using the original geometries in full precision (see below for WKT), JTS reports both geometries as valid, and is able to compute the difference correctly. The forthcoming OverlayNG should solve this issue in GEOS.

010600002023690000030000000103000000010000000900000076F3F2966BDA1641278F5DF376435241AAB538446EDA1641A4B08AFF7F435241ACF12E9A6BDA16411B1F4CFE76435241A1D4649C6BDA1641F7E706FE764352413CAC11E76BDA164118E81EF87643524136D0BE426CDA1641DD0D3DF376435241C5B8DD446CDA16415C1A2AF376435241828AECC62DDB1641FD73E9B97643524176F3F2966BDA1641278F5DF3764352410103000000010000000D0000002AED990373DA16416B2B720B904352417538D10673DA164196D95016904352418BD8FF3505DC16415F2B529F8F43524100DEC33205DC16414F9D63948F4352415A048E3005DC16414FD3A8948F435241732EE1E504DC164108D3909A8F435241FA0C348A04DC16412AAD729F8F4352416B2D158804DC16415BA0859F8F435241A459BAB573DA164150191D1690435241D4D266B173DA16417ABAF9159043524155D1E65273DA1641F3EC4E1190435241DB2AC90473DA1641951A940B904352412AED990373DA16416B2B720B9043524101030000000100000007000000EA2660C9FDDB1641D30F3E8776435241BEDE28C6FDDB1641C3615F7C764352418DBF3F17FDDB1641CF21937C764352411B45931BFDDB16419D80B67C764352410345137AFDDB16413F4E618176435241A1E930C8FDDB1641B3201C8776435241EA2660C9FDDB1641D30F3E8776435241

0103000020236900000100000015000000ACFDBBB473DA164192641D16904352412C159DB273DA16411358301690435241C9F2EF5673DA16416C32121B904352411A1D430C73DA16416432FA20904352413A3A0D0A73DA164189693F2190435241307280737ADA1641FFB3652EA9435241EAAFAF747ADA164128A3872EA94352414258CDC27ADA16416D754234A9435241455B4D217BDA1641D542ED38A943524118E2A0257BDA1641A9A11039A94352417366F4F70BDC164156A878C2A8435241F34513FA0BDC164125B565C2A8435241D565C0550CDC1641E5DA83BDA8435241D0396DA00CDC164113DB9BB7A84352415A13A3A20CDC164113A556B7A84352413F24373905DC16416DD930AA8F435241E9E6073805DC16414DEA0EAA8F4352416D40EAE904DC1641F31754A48F435241003F6A8B04DC1641704AA99F8F43524162B9168704DC1641A4EB859F8F435241ACFDBBB473DA164192641D1690435241

[strk]

Ticket retargeted after milestone closed

[mdavis]

This is fixed in 3.9 by OverlayNG