PostGIS Spatial Database Engine UMN Mapserver Boston Geographic Information Systems    Checkout our PostGIS in Action book.  First chapter is a free download   PostGreSQL Object Relational Database Management System
GIS Books  Home   Consulting Services  About Boston GIS   Boston GIS Blog  Postgres OnLine Journal
PostGIS in Action is out in hard-copy,
download the first chapter
and SQL Primer for free. Tips and Tricks for PostGIS
  GIS Article comments Comments Rss
PostGIS Concave Hull

This is a work in progress, and demonstrates the ST_ConcaveHull function that will be available in PostGIS 2.0. The basic approach is that it first creates a convexhull of the geometry and then uses the ST_ClosestPoint function introduced in PostGIS 1.5 to cave in the hull to transform it into a concave hull. That's the basic idea, the second arguments is the percent target of convexhull. The routine will recursively shrink until it determines it can't reach the target percent or it gets lower than target.

More details can be found at http://postgis.net/docs/manual-dev/ST_ConcaveHull.html
GeometryConcave HullConvex Hull
The letter S copied from Simon's blog
routes
 CREATE TABLE s_test(geom geometry); 
		INSERT INTO s_test(geom) VALUES(ST_GeomFromText('MULTIPOINT(
(120 -224), (185 -219), (190 -234), (200 -246), (212 -256), (227 -261), 
(242 -264), (257 -265), (272 -264), (287 -263),(302 -258), (315 -250),
(323 -237), (321 -222), (308 -213), (293 -208), (278 -205), (263 -202),
(248 -199), (233 -196), (218 -193), (203 -190), (188 -185), (173 -180),
(160 -172), (148 -162), (138 -150), (133 -135), (132 -120), (136 -105), 
(146  -92), (158  -82), (171  -74), (186  -69), (201  -65), (216  -62),
(231  -60), (246  -60), (261  -60), (276  -60), (291  -61), (306  -64),
(321  -67), (336  -72), (349  -80), (362  -89), (372 -101), (379 -115),
(382 -130), (314 -134), (309 -119), (298 -108), (284 -102), (269 -100), 
(254  -99), (239 -100), (224 -102), (209 -107), (197 -117), (200 -132), 
(213 -140), (228 -145), (243 -148), (258 -151), (273 -154), (288 -156), 
(303 -159), (318 -163), (333 -167), (347 -173), (361 -179), (373 -189), 
(383 -201), (389 -215), (391 -230), (390 -245), (384 -259), (374 -271), 
(363 -282), (349 -289), (335 -295), (320 -299), (305 -302), (290 -304),
(275 -305), (259 -305), (243 -305), (228 -304), (213 -302), (198 -300), 
(183 -295), (169 -289), (155 -282), (143 -272), (133 -260), (126 -246), 
(136 -223), (152 -222), (168 -221), (365 -131), (348 -132), (331 -133), 
(251 -177), (183 -157), (342  -98), (247  -75), (274 -174), (360 -223),
(192  -85), (330 -273), (210 -283), (326  -97), (177 -103), (315 -188),
(175 -139), (366 -250), (321 -204), (344 -232), (331 -113), (162 -129), 
(272  -77), (292 -192), (144 -244), (196 -272), (212  -89), (166 -236), 
(238 -167), (289 -282), (333 -187), (341 -249), (164 -113), (238 -283),
(344 -265), (176 -248), (312 -273), (299  -85), (154 -261), (265 -287),
(359 -111), (160 -150), (212 -169), (351 -199), (160  -98), (228  -77),
(376 -224), (148 -120), (174 -272), (194 -100), (292 -173), (341 -212), 
(369 -209), (189 -258), (198 -159), (275 -190), (322  -82))') ) ;

SELECT ST_AsBinary(
geom
)
FROM  s_test ;
		
SELECT ST_AsBinary(
ST_ConcaveHull(ST_Collect(geom),0.99)
)
FROM s_test;

99% concave hull 99

SELECT ST_AsBinary(
ST_ConcaveHull(geom,0.90)
)
FROM  s_test ;
90%
concave hull 90
SELECT ST_AsBinary(
ST_ConcaveHull(geom,0.90,true)
)
FROM  s_test;

90% allowing holes
concave hull 90 holes
SELECT ST_AsBinary(
 ST_ConvexHull(ST_Collect(geom))
        )
FROM s_test ;

convex hull
Stumper Lines
stumper line
SELECT ST_AsBinary(
ST_ConcaveHull(ST_Collect(geom),0.80)
 )
 FROM stumper;

stumper line concave hull
SELECT ST_AsBinary(
 ST_ConvexHull(ST_Collect(geom))
 )
 FROM stumper; 

stumper line convex hull
Point Wave
stumper line
CREATE TABLE pointwave(gid serial primary key, geom geometry);
INSERT INTO pointwave(geom)
SELECT ST_Point(i*random(),j*random()) As the_geom 
FROM generate_series(1,100) As i 
	CROSS JOIN generate_series(-20,20) As j ;
SELECT geom FROM pointwave;
		

SELECT ST_AsBinary(
 ST_ConcaveHull(
    ST_Collect(geom),0.80
    )
   )
 FROM pointwave;

80% point wave concave hull 80%
SELECT ST_AsBinary(
 ST_ConcaveHull(
    ST_Collect(geom),0.50
    )
   )
 FROM pointwave;

50% point wave concave hull 50%
SELECT ST_AsBinary(ST_ConvexHull(ST_Collect(geom)))
 FROM stumper; 

pointwave convex hull
Point Locs (~5000 points)
stumper line

SELECT ST_AsBinary(geom) 
FROM pointlocs 
WHERE geom IS NOT NULL;
		

99%
SELECT ST_AsBinary( ST_ConcaveHull( ST_Collect(geom),0.99 ) )
FROM pointlocs
    WHERE geom IS NOT NULL;

point loc concave hull 99%
90%
SELECT ST_AsBinary( ST_ConcaveHull( ST_Collect(geom),0.90 ) )
FROM pointlocs
    WHERE geom IS NOT NULL;

point loc concave hull 90%
90% allow holes
SELECT ST_AsBinary( ST_ConcaveHull( ST_Collect(geom),0.90 ),true )
FROM pointlocs
    WHERE geom IS NOT NULL;

point loc concave hull 90%
70%
SELECT ST_AsBinary( ST_ConcaveHull( ST_Collect(geom),0.70 ) )
FROM pointlocs
    WHERE geom IS NOT NULL;

pointloc concave hull 70%
70% allow holes
SELECT ST_AsBinary( ST_ConcaveHull( ST_Collect(geom),0.70,true ) )
FROM pointlocs
    WHERE geom IS NOT NULL;

pointloc concave hull 70%
SELECT ST_AsBinary( 
    ST_ConvexHull( ST_Collect(geom)
        )
      )
FROM pointlocs
WHERE geom IS NOT NULL;

pointwave convex hull
Neighborhoods
boston neighborhoods

SELECT ST_Union(geom) FROM neighborhoods;
		

SELECT ST_AsBinary(
    ST_ConcaveHull(ST_Union(geom),0.99)
			)
FROM neighborhoods;

99%
concave hull 99 percent
SELECT ST_AsBinary(
    ST_ConcaveHull(ST_Union(geom),0.90)
			)
FROM neighborhoods;

90%
concave hull 90
SELECT ST_AsBinary(
    ST_ConcaveHull(ST_Union(geom),0.70)
			)
FROM neighborhoods;

70%
concave hull
SELECT ST_AsBinary(
    ST_ConcaveHull(ST_Union(geom),0.70)
			)
FROM neighborhoods;

50%
concave hull
SELECT ST_AsBinary(
 ST_ConvexHull(ST_Union(the_geom))
        )
FROM neighborhoods; 

convex hull
MBTA routes (about 1000 multilinestrings)
routes

SELECT ST_AsBinary(
geom
)
FROM  mbta_busroutes ;
		

Note: In some cases the 99% (such as this example) gives a better and much faster result than some of the lower compressions. This is because of GEOS topological errors we run into that force the alogrithm to fall back on the convexhull for certain regions. So as a general rule, try the 99% first. It is generally much much faster than lower percentages, for fairly huge patches of empty area, also returns an areal percentage much less than the convexhull, and is also less likely to run into topological issues

99%
SELECT ST_AsBinary(
ST_ConcaveHull(ST_Collect(geom),0.99)
)
FROM  mbta_busroutes 
;

concave hull 99
90%
SELECT ST_AsBinary(
ST_ConcaveHull(ST_Collect(geom),0.90)
)
FROM  mbta_busroutes 
;

concave hull 90
SELECT ST_AsBinary(
ST_ConcaveHull(ST_Collect(geom),0.70)
)
FROM  mbta_busroutes;

70% do not allow holes
concave hull 70
SELECT ST_AsBinary(
ST_ConcaveHull(ST_Collect(geom),0.70, true)
)
FROM  mbta_busroutes;

70% allow holes
concave hull 70 allow holes
SELECT ST_AsBinary(
 ST_ConvexHull(ST_Collect(geom))
        )
FROM mbta_busroutes ;

convex hull


Post Comments About PostGIS Concave Hull




This Document is available under the GNU Free Documentation License 1.2 http://www.gnu.org/copyleft/fdl.html & for download at the BostonGIS site http://www.bostongis.com

Boston GIS      Copyright 2019      Paragon Corporation