Opened 5 hours ago

Last modified 5 hours ago

#5825 new defect

ST_ConcaveHull gives unexpected result with MultiPolygon

Reported by: nbvfgh Owned by: strk
Priority: critical Milestone: PostGIS 3.5.2
Component: liblwgeom Version: 3.5.x
Keywords: Cc:

Description

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)))');

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))) }

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))) }

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))) }

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))) }

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

Change History (1)

comment:1 by nbvfgh, 5 hours ago

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),(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(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)) }

https://github.com/user-attachments/assets/90afce55-af06-4c2c-93c5-439a9224f00f

Note: See TracTickets for help on using tickets.