[PostGIS] #5825: ST_ConcaveHull gives unexpected result with MultiPolygon

[PostGIS]

#5825: ST_ConcaveHull gives unexpected result with MultiPolygon
-----------------------+---------------------------
 Reporter:  nbvfgh     |      Owner:  strk
     Type:  defect     |     Status:  new
 Priority:  critical   |  Milestone:  PostGIS 3.5.2
Component:  liblwgeom  |    Version:  3.5.x
 Keywords:             |
-----------------------+---------------------------
 Considering following MultiPolygon:
 {{{
 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)))');
 }}}
 [[Image(https://github.com/user-
 attachments/assets/b3f34c67-3310-464a-a541-c4938f7941a0)]]

 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：
 {{{
 SELECT ST_AsText(ST_ConcaveHull(
                  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)))'),
 0.47,false));

 -- result:{ MULTIPOLYGON(((10 4,10 2,8 2,2 1,8 4,4 8,4 9,5 9,10 4)),((1
 0,0 0,2 1,1 0))) }
 }}}
 [[Image(https://github.com/user-
 attachments/assets/9d9768b2-821e-4470-ac58-16971ca961e0)]]

 Case param_pctconvex = 0.47:
 {{{
 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.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
 0,0 0,2 1,1 0))) }
 }}}
 [[Image(https://github.com/user-
 attachments/assets/9d9768b2-821e-4470-ac58-16971ca961e0)]]


 Case param_pctconvex = 0.25:
 {{{
 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.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 0,0 0,2 1,1 0))) }
 }}}
 [[Image(https://github.com/user-
 attachments/assets/325cbc1b-1244-4fd9-a823-d2c4cd14e448)]]

 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),(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))) }
 }}}
 [[Image(https://github.com/user-attachments/assets/d43d7e59-3141-47bd-
 aca1-8dd198f2aaeb)]]

 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`
-- 
Ticket URL: <https://trac.osgeo.org/postgis/ticket/5825>
PostGIS <http://trac.osgeo.org/postgis/>
The PostGIS Trac is used for bug, enhancement & task tracking, a user and developer wiki, and a view into the subversion code repository of PostGIS project.