Recently, a friend in a group chat asked: given a bunch of POI points, how can we automatically generate a boundary polygon that 'fits the actual extent'? The convex hull results in an area that is too large and too rounded—is there a way to get a tighter boundary? So, I'll try to introduce the definitions, algorithms, and common tools for concave hull and convex hull.
Concave Hull and Convex Hull
The convex hull can be thought of as the polygon formed by stretching a rubber band around all the points and letting it snap tight; it is the smallest convex set containing the points. In GIS, it is commonly used to compute building outlines or bounding envelopes of point sets. Convex hull algorithms are fast and produce stable results, but the shape tends to be 'bulging', and concave details are smoothed out.
The concave hull is the opposite: it also encloses all points but allows indentations along the boundary. It usually has a smaller area and longer perimeter, and it looks closer to what we would consider a 'reasonable boundary'. For example, when inferring built-up area boundaries from urban POIs, or delineating parcel extents from LiDAR point clouds, the concave hull often appears more natural than the convex hull.
As shown below, the blue line is the convex hull and the red line is the concave hull.
However, it should be noted that, unlike the convex hull, the concave hull does not have a strict definition of a 'unique optimum'. Different algorithms and parameters yield different results.
Major Algorithms
The most discussed approach in the community is to treat the concave hull as a special case of the Alpha Shape. Alpha Shape was proposed by Edelsbrunner et al. in 1983. When the alpha value is large, the shape approximates the convex hull; as alpha decreases, the boundary gradually shrinks inward and concavities appear.
Another classic approach is the algorithm proposed by Duckham et al. in 2008, published in Pattern Recognition. The idea is to efficiently generate a simple polygon from a point set to characterize its shape. There is an open-source Java implementation, and the result is shown below.
In recent years, the JTS geometry library has also added a concave hull implementation, based on 'eroding' the Delaunay triangulation of the input points: it progressively removes triangles with excessively long edges from the outer boundary, preserving an outline that hugs the point cloud. This algorithm has been ported to GEOS and exposed in PostGIS 3.3 and later via ST_ConcaveHull, which accepts parameters for both absolute length and relative ratio, and can also control whether holes are kept.
Additionally, there is the lasboundary algorithm designed for massive LiDAR point clouds, part of the LAStools toolchain. It can directly output concave hull boundaries from formats such as LAS, LAZ, and SHP, and is characterized by its ability to handle large datasets. In the R ecosystem, packages like alphahull and spatialEco can also achieve this.
Processing in QGIS
QGIS Processing Toolbox includes a built-in Concave hull tool, as shown below:
It mainly has three parameters:
- Threshold: a value from 0 to 1, default 0.3. The smaller the value, the tighter the boundary hugs the points; the larger the value, the closer it is to the convex hull. A value of 1 produces the convex hull.
- Allow holes: whether to allow holes in the result, enabled by default.
- Split multipart geometry: whether to split multipart geometries into single parts.
Computing Concave Hull in PostGIS
Starting from PostGIS 3.3, the ST_ConcaveHull function is available, using the JTS concave hull algorithm under the hood. Basic usage:
SELECT ST_ConcaveHull(ST_Collect(geom), 0.3) AS hull
FROM your_point_table;The second parameter is target_percent, similar in meaning to QGIS' Threshold: 0 yields the tightest boundary, 1 gives the convex hull. You can also specify whether to allow holes.
Point Clouds and Other Tools
For LiDAR scenarios, lasboundary is recommended. Command-line example:
lasboundary -i SerpentMound.las -o SerpentMound_boundary.shpThe tool first computes the convex hull and then shrinks it inward according to the concavity parameter to form the concave hull, outputting Shapefile or KML.
Pure Python Implementation
Beyond desktop and database tools, the easiest way via Python scripting is to use the concave_hull function built into Shapely 2.0+, which also relies on GEOS and shares a similar parameter interface with PostGIS:
from shapely import MultiPoint, concave_hull
pts = MultiPoint([
(0, 0), (0, 2), (1, 1.5), (2, 2), (2, 0),
(1, 0.2), (1.5, 1), (0.5, 1),
])
# ratio: 0 is the tightest, 1 approximates convex hull, same intuition as QGIS Threshold / PostGIS target_percent
hull = concave_hull(pts, ratio=0.3, allow_holes=False)
print(hull.wkt)Requires Shapely 2.0+ and GEOS ≥ 3.11. If your points come from a GeoPandas GeoDataFrame, you can also write gdf.unary_union.concave_hull(ratio=0.3).
Additionally, for the Alpha Shape approach, you can use the alphashape library: alphashape.alphashape(coords, alpha).
Summary
Have you used concave hull or convex hull in your projects? Which method did you use? If you have a favorite concave hull tool or lessons learned, feel free to leave a comment.