ST_MakeValid outputs invalid geometries

[dmiranda]

Calling ST_MakeValid on certain geometries outputs garbage.

The resulting geometries are invalid, and their bounding boxes go all the way to the lat,long=(0,0) (the "made valid" polygons are thousands of kilometers larger than the original geometries).

I believe this issue to be of high priority because the behaviour is unexpected and in most cases there are no warnings to be seen. In my particular case, this issue prevents the use of ST_MakeValid altogether.

Test environment

Postgresql 9.2.4 with Postgis 2.0.3 on Ubuntu 12.04.2

SELECT version() → "PostgreSQL 9.2.4 on x86_64-unknown-linux-gnu, compiled by gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3, 64-bit"

SELECT postgis_full_version() → "POSTGIS="2.0.3 r11128" GEOS="3.3.8-CAPI-1.7.8" PROJ="Rel. 4.8.0, 6 March 2012" GDAL="GDAL 1.9.2, released 2012/10/08" LIBXML="2.8.0" RASTER"

How to reproduce

— sample data:

CREATE TABLE test (gid serial NOT NULL, geom Geometry);

INSERT INTO test (geom) values ('0106000020E6100000010000000103000000010000000 A0000004B7DA956B99844C0DB0790FE8B4D1DC010BA74A9AF9444C049AFFC5B8C4D1DC03FC6CC6 90D9844C0DD67E5628C4D1DC07117B56B0D9844C0C80ABA67C45E1DC0839166ABAF9444C0387D4 568C45E1DC010BA74A9AF9444C049AFFC5B8C4D1DC040C3CD74169444C0362EC0608C4D1DC07C1 A3B77169444C0DC3ADB40B2641DC03AAE5F68B99844C0242948DEB1641DC04B7DA956B99844C0D B0790FE8B4D1DC0'::geometry);

— The following outputs 'f':

SELECT ST_IsValid(geom) FROM test;

— The following also outputs 'f', with no warnings:

SELECT ST_IsValid(ST_MakeValid(geom)) FROM test;

— The following outputs "t", no warnings.

SELECT ST_IsValid(ST_MakeValid(ST_MakeValid(geom))) FROM test;

— The following outputs very different bounding boxes:

SELECT Box2D(ST_MakeValid(ST_MakeValid(geom))), Box2D(geom) FROM test;

— outputs "BOX(

-41.193158194274 -41.193158194274, 6.95325424073808e-310 6.95325424070132e-310)"; "BOX(-41.193158194274 -7.34833623254846, -41.1569353108121 -7.32572934869855)"

additional information

I have not tested this with earlier versions of postgis nor with the latest svn download.

I have also found out that Box2D() returns wrong bounding boxes, but since the geometries are invalid, I am not submitting a bug report for that.

I have attached a total of 103 examples in which st_makevalid produces invalid geometries, both in CSV format and SQL dump.

[pramsey]

OK, so some interesting results… the result of ST_MakeValid on the geometry cited in the comment is this:

select st_astext(st_makevalid(geom)) from test;

 MULTIPOLYGON(((1.38241720848787e+306 1.38241720848787e+306,1.38241720848787e+306 1.38241720848787e+306,1.38241720848787e+306 1.38241720848787e+306,1.38241720848787e+306 1.38241720848787e+306,1.38241720848787e+306 1.38241720848787e+306,1.38241720848787e+306 1.38241720848787e+306),(0 1.38241720848787e+306,1.38241720848787e+306 1.38241720848787e+306,1.38241720848787e+306 2.13091231225152e-314,6.95322297557074e-310 2.12970193392818e-314,6.95322297557153e-310 1.38241720848787e+306)))

Fun, hey? But it gets better. This is a single-part multi-polygon… what happens if we strip out the multi and clean the polygon as a singleton.

select st_astext(st_makevalid(st_geometryn(geom,1))) from test;
                                                                                                                                                                                                       POLYGON((-41.1931560828767 -7.32572934869855,-41.161610776897 -7.32573074083104,-41.1569353108121 -7.32573081181504,-41.1569356001464 -7.34833623254846,-41.193158194274 -7.34833476367411,-41.1931560828767 -7.32572934869855),(-41.161610776897 -7.32573074083104,-41.1879093408465 -7.32573084378415,-41.1879095682369 -7.34254610131274,-41.1616110087225 -7.34254610942963,-41.161610776897 -7.32573074083104))

Hey presto, it works, and this output is actually valid (though looking at it in the JTS testbuilder, it still looks invalid until you zoom up quite close to see that it doesn't have a hole/hull edge coincidence, just a Very Very close hole and hull.

So, first thing is to examine what the cleaning functions are doing on multi-geometries and see if we can just plug that easy problem to start with.

[pramsey]

Fixed in trunk at r11525 and 2.0 branch at r11526

[strk]

The commenting out of lwgeom_free looks suspicious, why is that ? And can you add a small version testcase of this in the suite ?

[pramsey]

Tests added and comment on lwgeom_free. The free precedes a multi function, which wraps the singleton *lightly*, so freeing causes the internal object to go away and oops.

[strk]

Thanks, but test in r11620 is only at the PostgreSQL level, where memory management is performed with leak-free palloc system. My concern is at liblwgeom level, where NOT freeing might result in a leak, doesn't it ?

As far as I can tell, the lwgeom_as_multi function always creates new memory, not wrapping the input, check out http://trac.osgeo.org/postgis/browser/tags/2.1.0beta3/liblwgeom/lwgeom.c#L284

Maybe there's a bug in lwgeom_clone, used when the input to lwgeom_as_multi is a collection ?

Please add the test to cunit/cu_clean.c so we can more easily put under valgrind.

[dmiranda]

Hello, just to let you know, I have briefly tested the solution in trunk and the output seems ok.

I do not have enough knowledge about the inner workings of pgsql or postgis to comment on the potential memory leak.

Suppose it does leak memory, is there any test I could run to force the leak to appear?

Please let me know if I can be of any help.

[strk]

Thanks for your availability for testing this dmiranda, but there will be no leak while using this under PostGIS. The leak will only be present when using liblwgeom directly (like from QGIS or Spatialite).

[robe]

Hey guys I just noticed, did anyone patch branch/2.1? trunk is 2.2 now remember? I assume this affects branch/2.1 as well.

[strk]

Better completing it before backporting (cunit test to put under valgrind for seeing the memory problems)

[strk]

I found that there are already tests in cunit that expose the leak:

==25260== HEAP SUMMARY:
==25260==     in use at exit: 504 bytes in 10 blocks
==25260==   total heap usage: 10,408 allocs, 10,398 frees, 397,158 bytes allocated
==25260== 
==25260== 392 (40 direct, 352 indirect) bytes in 1 blocks are definitely lost in loss record 8 of 8
==25260==    at 0x4C2B6CD: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==25260==    by 0x4E5044D: lwpoly_construct (lwpoly.c:52)
==25260==    by 0x4E775CD: lwgeom_make_valid (lwgeom_geos_clean.c:1049)
==25260==    by 0x40876F: test_lwgeom_make_valid (cu_clean.c:56)
==25260==    by 0x50952A9: ??? (in /usr/lib/libcunit.so.1.0.1)
==25260==    by 0x50956ED: ??? (in /usr/lib/libcunit.so.1.0.1)
==25260==    by 0x50958D7: CU_run_suite (in /usr/lib/libcunit.so.1.0.1)
==25260==    by 0x404ADE: main (cu_tester.c:197)

The leak goes away by re-introducing the lwgeom_free call. And no memory error is shown. But the test in regress fails…

This bug is in search of a better fix. Will take a look.

[strk]

r11635 adds the unit test for this case. So right now either we get a leak or we get an invalid read. Until this bug is properly fixed.

[strk]

lwfree (contrary to lwgeom_free) seems to do what we need (shallow release of resources for the collection case).

[strk]

r11636 fixes the leak in trunk. Time to backport the whole lot.

[robe]

don't forget 2.1 when you backport

[strk]

r11637 backports to 2.1, r11638 in 2.0