ST_ConcaveHull Runtime

[tsw]

A concave hull query with the attached data set under Postgresql 9.4 / PostGIS 2.2 / Geos 3.5.0 runs in under a second.

The same query using the same data on Postgresql 9.6 / PostGIS 2.5.2 / GEOS 3.7.1 is still running after 30 minutes.

I've also attached a perf top screen shot to help people identify the possible source of the problem.

[tsw]

Data set used to generate error

[tsw]

screenshot of perf top while query is running

[robe]

I think we ruled this is most likely a GEOS issue related to union changes for geometries possibly this ​https://trac.osgeo.org/geos/ticket/867

so flipping to GEOS milestone.

[komzpa]

​https://www.mail-archive.com/postgis-users@lists.osgeo.org/msg07593.html

[tsw]

Discussions on GEOS Issue 982 suggests that my own testing was incomplete so this may in fact be a PostGIS issue.

dbaston commented: " FWIW, if I run ST_ConcaveHull(geom, 0.99) using GEOS master against PostGIS trunk, the query takes forever. If I run it using GEOS master against the ST_ConcaveHull implementation from PostGIS 2.3.10 it completes instantly."

[tsw]

I've further tested this today and calls to public.ST_UnaryUnion in ST_Concave hull don't make any difference as they are only applied to polygon geometries, and in this case, lines are the problem.

HOWEVER, the ST_UnaryUnion call made at the end of _st_concavehull added in response to issue 3638 is the source of this problem. If this is commented out the query runs instantly. Not sure if there is another way to address 3638, but this change causes the slowdown I document here.

[komzpa]

Good news, this form of that line returns instantly for me and will allow concave hull to still cover a polygon:

var_resultgeom := public.ST_Union(ST_CollectionExtract(param_inputgeom, 3), var_resultgeom);

Bad news, it's not returning a concave hull - lines are hanging outside of it.

[mdavis]

Concave Hull has now been implemented natively in GEOS (version 3.11 and above). This case now works with good performance.