ST_ConcaveHull of MultiPolygon returns disconnected result

[nbvfgh]

Considering following MultiPolygon:

SELECT ST_GeomFromText('MULTIPOLYGON (((0 0, 1 0, 2 1, 1 1, 0 0)), 
					((8 2, 8 4, 10 4, 10 2, 8 2)),
					((4 9, 5 9, 5 8, 4 8, 4 9)))');

We calculate its concave shell with ST_ConcaveHull(geom, param_pctconvex, param_allow_holes)：
As described in the document, the param_pctconvex controls the concaveness of the computed hull. A value of 0 produces a hull with maximum concaveness (but still a single polygon). And often values between 0.3 and 0.1 produce reasonable results.

Case param_pctconvex = 0.47:

WITH mp AS(
	SELECT ST_GeomFromText('MULTIPOLYGON (((0 0, 1 0, 2 1, 1 1, 0 0)), 
		                      ((8 2, 8 4, 10 4, 10 2, 8 2)),
		                      ((4 9, 5 9, 5 8, 4 8, 4 9)))'
	) geom
)
SELECT ST_AsText(ST_ConcaveHull(mp.geom, 0.47,false)),
	   ST_ConcaveHull(mp.geom, 0.47,false) from mp;

-- result:{ MULTIPOLYGON(((10 4,10 2,8 2,2 1,8 4,4 8,4 9,5 9,10 4)),((1 1,2 1,1 0,0 0,1 1))) }

Case param_pctconvex = 0.25:

WITH mp AS(
	SELECT ST_GeomFromText('MULTIPOLYGON (((0 0, 1 0, 2 1, 1 1, 0 0)), 
		                      ((8 2, 8 4, 10 4, 10 2, 8 2)),
		                      ((4 9, 5 9, 5 8, 4 8, 4 9)))'
	) geom
)
SELECT ST_AsText(ST_ConcaveHull(mp.geom, 0.25,false)),
	   ST_ConcaveHull(mp.geom, 0.25,false) from mp;

-- result:{ MULTIPOLYGON(((8 4,4 8,4 9,5 9,5 8,8 4)),((2 1,8 4,10 4,10 2,8 2,2 1)),((1 1,2 1,1 0,0 0,1 1))) }

Case param_pctconvex = 0:

WITH mp AS(
	SELECT ST_GeomFromText('MULTIPOLYGON (((0 0, 1 0, 2 1, 1 1, 0 0),(0 0, 1 1, 2 1, 0 0)), 
		                      ((8 2, 8 4, 10 4, 10 2, 8 2)),
		                      ((4 9, 5 9, 5 8, 4 8, 4 9)))'
	) geom
)
SELECT ST_AsText(ST_ConcaveHull(mp.geom, 0,false)),
	   ST_ConcaveHull(mp.geom, 0,false) from mp;

-- result:{ MULTIPOLYGON(((0 0,1 0,2 1,1 1,0 0)),((8 2,8 4,10 4,10 2,8 2)),((4 9,5 9,5 8,4 8,4 9))) }

The above three examples do not meet expectations. When param_pctconvex is set to 0, it even degenerates into three original polygons

Version Info:
GEOS="3.13.0-CAPI-1.19.0

[nbvfgh]

To add, when converted into a set of points, the result is as expected.

WITH mp AS(
	SELECT ST_GeomFromText('MULTIPOLYGON (((0 0, 1 0, 2 1, 1 1, 0 0)), 
		                      ((8 2, 8 4, 10 4, 10 2, 8 2)),
		                      ((4 9, 5 9, 5 8, 4 8, 4 9)))'
	) geom
)
SELECT ST_AsText(ST_ConcaveHull(ST_Points(mp.geom), 0,false)),
	   ST_ConcaveHull(ST_Points(mp.geom), 0,false) from mp;

-- result: { POLYGON((4 8,4 9,5 9,5 8,10 4,10 2,8 2,1 0,0 0,1 1,2 1,8 4,4 8)) }

[dr-jts]

This is a limitation of the current algorithm. It can produce disconnected results for low threshold values.

It is possible to fix this, at the cost of some performance. It requires checking that the internal triangulation remains connected after each triangle "erosion".

[nbvfgh]

Thanks for your prompt reply.