ST_MakeValid: exception on geometry [FIXED BY GEOS-3.3.4]

[aperi2007]

Hi,

try-ing to apply ST_MakeValid on all geometries of a table apply-ing this query:

update gb.refresh_2010 set geometry2 = ST_CollectionExtract(ST_Force_Collection(ST_MakeValid(geometry)),3);

The table has two geometry field (geometry and geometry2).
Geometry2 is multipolygon.

The error I have is this:

[Errore] Righe script: 1-7 ------------------------- ERROR: IllegalArgumentException?: Operation not supported by GeometryCollection? Riga: 1

Avvertimenti: --->

W (1): GEOSBoundary('GEOMETRYCOLLECTION(LINESTRING(1634953.49423 4773448.36241,1634954.48166 4773448.34473),POLYGON((1635000 4773453.81109,1634993.92191 4773452.03831,1634989.59971 4773451.2279,1634980.41727 4773447.19096,1634975.125 4773447.975,1634955.625 4773447.975,1634953.49423 4773448.36241,1634953.49423 4773448.36241,1634953.49423 4773448.36241,1634953.49423 4773448.36241,1634944.625 4773449.975,1634944.2166 4773460.41257,1634963.39637 4773470.6778,1635000 4773490.85092,1635000 4773453.81109)),POLYGON((1634954.48166 4773448.34473,1634955.46909 4773448.32704,1634955.46909 4773448.32704,1634954.48166 4773448.34473)))') threw an error: IllegalArgumentException?: Operation not supported by GeometryCollection?

<---

[Eseguito: 28/03/2012 22.26:08] [Esecuzione: 0ms]

---

I'm using the postgis:

POSTGIS="2.0.0beta4 r9521" GEOS="3.3.3dev-CAPI-1.7.3" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.9.0, released 2011/12/29" LIBXML="2.7.8" LIBJSON="UNKNOWN" TOPOLOGY RASTER
On windows 7

---

After this , I try to another execution but postgis was crash.
This is the log.

2012-03-28 23:14:19 CEST STATEMENT:  select (geometry) from gb.refresh_2010 where st_isvalid(geometry)=false
EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

EdgeRing::getRingInternal: IllegalArgumentException: Invalid number of points in LinearRing found 3 - must be 0 or >= 4

Assertion failed: 0 != g, file geos_ts_c.cpp, line 2150



This application has requested the Runtime to terminate it in an unusual way.
Please contact the application's support team for more information.

2012-03-28 23:15:30 CEST LOG:  server process (PID 472) exited with exit code 3
2012-03-28 23:15:30 CEST LOG:  terminating any other active server processes

[strk]

Andrea: could you isolate the offending input and attach it here ? Also please file another bug for the ST_IsValid crash.

[aperi2007]

Replying to strk:

Andrea: could you isolate the offending input and attach it here ? Also please file another bug for the ST_IsValid crash.

of course.

I'm working to isolate the offending geometry. The problem is that every time I touch it, the postgres will crash. However I hope get it soon.

[robe]

Andrea,

I just put up the rc1 binaries. You might want to try those first to rule out that its an issue already fixed in the beta4-rc1 timeframe.

[aperi2007]

Hi, here is the dump with the geometry that will crash my postgres. Postgres 9.1.3 32 bit on Win7.

Now I will try with the RC1.

Andrea.

[aperi2007]

dump table with error geometry

[aperi2007]

the link: http://trac.osgeo.org/postgis/attachment/ticket/1735/errore.rar

[strk]

I filed #1738 for the crash, and attached a simple script to reproduce in there. Let's keep this one for the exception.

[aperi2007]

Replying to robe:

Andrea, I just put up the rc1 binaries. You might want to try those first to rule out that its an issue already fixed in the beta4-rc1 timeframe.

Hi, I tested the RC1. The ST:MakeValid(geometry) still give exception (and crash) with RC1.

[strk]

Crash is fixed with r9581, we still have the exception but I'm afraid it's not something we can fix before 2.0.0 final...

Robustness issues keep getting in the way :(

[strk]

The exception is caused by an invalid input passed to GEOSSymDifference, but the invalid input was the output of a previous GEOSSymDifference call !

Check this out:

with inp as ( select '010300000001000000080000000000000087523A41000000402C62524100000000B0523A41000000C01E6252410000000084523A41000000C023625241858C4F2488523A4151F8EEAC2562524111A0F52288523A414F50F3AC25625241D59FF52288523A414F50F3AC25625241000000007F523A4100000080256252410000000087523A41000000402C625241'::geometry as a , '01030000000100000004000000A871502388523A4158FEF2AC2562524100A0F52288523A414F50F3AC2562524111A0F52288523A414F50F3AC25625241A871502388523A4158FEF2AC25625241'::geometry as b ) select ST_IsValid(a) as a_valid, ST_IsValid(b) as b_valid, ST_IsValid(ST_SymDifference(a,b)) as sd_valid from inp;

NOTICE:  Self-intersection at or near point 1725064.1365604463 4819094.70235069
 a_valid | b_valid | sd_valid 
---------+---------+----------
 t       | t       | f
(1 row)

Good material for another ticket (on GEOS). Will file and report back!

[strk]

The invalid output from SymDifference? bug was filed on GEOS:  http://trac.osgeo.org/geos/ticket/523

I wonder if we could improve our code to avoid the calls to SymDifference?.

[strk]

So, GEOSSymDifference is called by BuildArea? and passed the outer rings of polygons returned by Polygonize. Supposedly these polygons should all be already noded so there would be no reason for the geos noder to complain.

The offending input to BuildArea? is this:

0105000000050000000102000000050000000000000087523A41000000402C62524100000000B0523A41000000C01E6252410000000084523A41000000C023625241858C4F2488523A4151F8EEAC2562524111A0F52288523A414F50F3AC2562524101020000000300000011A0F52288523A414F50F3AC2562524100A0F52288523A414F50F3AC25625241A871502388523A4158FEF2AC25625241010200000004000000A871502388523A4158FEF2AC25625241A0E6602488523A417108F2AC2562524121E7602488523A417108F2AC25625241A871502388523A4158FEF2AC25625241010200000002000000A871502388523A4158FEF2AC2562524111A0F52288523A414F50F3AC2562524101020000000400000011A0F52288523A414F50F3AC25625241D59FF52288523A414F50F3AC25625241000000007F523A4100000080256252410000000087523A41000000402C625241

Which is a multilinestring composed by 5 short lines.

Surprising enough, ST_Relate of the geometry to self has NO BOUNDARY INTERSECTION !!

with inp as ( select '0105000000050000000102000000050000000000000087523A41000000402C62524100000000B0523A41000000C01E6252410000000084523A41000000C023625241858C4F2488523A4151F8EEAC2562524111A0F52288523A414F50F3AC2562524101020000000300000011A0F52288523A414F50F3AC2562524100A0F52288523A414F50F3AC25625241A871502388523A4158FEF2AC25625241010200000004000000A871502388523A4158FEF2AC25625241A0E6602488523A417108F2AC2562524121E7602488523A417108F2AC25625241A871502388523A4158FEF2AC25625241010200000002000000A871502388523A4158FEF2AC2562524111A0F52288523A414F50F3AC2562524101020000000400000011A0F52288523A414F50F3AC25625241D59FF52288523A414F50F3AC25625241000000007F523A4100000080256252410000000087523A41000000402C625241'::geometry as a ) select st_relate(a, a) from inp;

 1FFFFFFF2

That's surely a problem !

[strk]

The IntersectionMatrix? bug was filed as  http://trac.osgeo.org/geos/ticket/524

[strk]

Ok, the IntersectionMatrix? was a false alarm, it's normal to have no boundary intersection for geometries w/out boundaries (due to Mod2BoundaryNodeRule), so back to the SymDifference? bug: given two valid inputs, it raises the exception.

What I was after is the fact that such input is coming from Polygonize (called by BuildArea?) so should be pretty much all fully noded. In particular Polygonize returns 3 polygons: one is the outer shell with 2 tiny holes, and the other 2 are the tiny holes on themselves.

I've noticed that the outer shell with holes is considered invalid (self intersection) but the exterior ring itself is valid!

[strk]

So, the invalid part is the fact that one of the holes is in contact with the exterior ring. There's no invalidity if the hole in contact is removed.

This makes me think that GEOSPolygonize might have given the wrong answer. Inspecting Intersection matrices further...

[strk]

Alright, according to intersection matrices the two holes touch in a point, but the shell has a _linear_ intersection with one of the holes !

This is definitely a wrong answer from ST_Polygonize. How to check if the input was correctly noded now ?

[strk]

Trying to debug the polygonize issue I tried to model the situation I saw using intersection matrices into a new simpler input. This is it:

In WKT, it is:

MULTILINESTRING((0 0, 4 0, 5 3, 4 6),(4 6, 6 6, 5 3, 6 0, 10 0, 5 10, 0 0),(4 0, 6 0))

Unfortunately such input results in an EMPTY output from ST_Polygonize, which is confusing.

[strk]

For the polygonize issue, filed:  http://trac.osgeo.org/geos/ticket/525

[strk]

Alright my WKT was also bogus (not fully noded) so we're back to this issue and the question this time is: given Polygonze returned an invalid polygon, did we feed it a validly noded input ? How to tell ? Research for monday...

[strk]

So back to the reason _why_ Polygonize is getting invalid input, I see that ST_MakeValid is trying to ensure correct input noding using a LWGEOM_GEOS_nodeLines function.

Well, the return from such function doesn't pass the ST_IsSimple test, which is probably a good way to detect proper noding.

LWGEOM_GEOS_nodeLines is running a GEOSUnion between the line and one of its endpoints. I've also tried calling GEOSUnaryUnion with no luck.

So next issue is: GEOSUnion (and GEOSUnaryUnion) incorrectly node lines.

Filed as  http://trac.osgeo.org/geos/ticket/527

[strk]

Function to check correct noding

[strk]

So finally a valid GEOS bug. ST_IsSimple wasn't a good test but the one performed by the attached CheckNoding?.sql script is, and clearly shows that UnaryUnion? is failing to produce correct noding. There's a case of linear and puntual interior/interior intersections between returned lines.

[strk]

To recap: the issue is with the heuristic used by UnaryUnion? generating invalid noding. I've tested that iterating the noding procedure can eventually handle to correctly node. Such iteration could be implemented in PostGIS ST_MakeValid to improve likelyhood of succeeding.

[strk]

I'm still on this.

MULTIPOLYGON(((1725063 4819121, 1725104 4819067, 1725060 4819087, 1725064.14183882 4819094.70208557,1725064.13656044 4819094.70235069,1725064.14210359 4819094.70227252,1725064.14210362 4819094.70227252,1725064.13656043 4819094.70235069,1725055. 4819094, 1725055 4819094, 1725055 4819094, 1725063 4819121)))

ST_MakeValid chokes with the above input, due to UnaryUnion? failing to correctly node the boundary of that multipolygon.

Noding is under testing with the GEOS IteratedNoder? which succeeds at fully noding the input with 6 iterations:

Iteration 1 # nodes created: 2
Iteration 2 # nodes created: 3
Iteration 3 # nodes created: 5
Iteration 4 # nodes created: 5
Iteration 5 # nodes created: 5
Iteration 6 # nodes created: 0

This is (theoretically) because everytime you add a node to a segment you're effectively changing the segment shape and the new shape may intersect with other segments to which the original segment wasn't intersecting. I'd like to confirm this visually with an reduced precision model.

[strk]

Alright the invalid-result-from-UnaryUnion? was finally fixed in GEOS and with that fix I can get a valid result from ST_MakeValid:

strk=# select ST_Summary(ST_MakeValid('MULTIPOLYGON(((1725063 4819121, 1725104 4819067, 1725060 4819087, 1725064.14183882 4819094.70208557,1725064.13656044 4819094.70235069,1725064.14210359 4819094.70227252,1725064.14210362 4819094.70227252,1725064.13656043 4819094.70235069,1725055. 4819094, 1725055 4819094, 1725055 4819094, 1725063 4819121)))'));
              st_summary
---------------------------------------
 GeometryCollection[B] with 2 elements
   Polygon[] with 2 rings
    ring 0 has 12 points
    ring 1 has 4 points
   LineString[] with 2 points
(1 row)

Let's keep this ticket open until GEOS-3.3.4 is out.