Concave Hull

A concave hull (also called an alpha shape or chi shape) is a polygon that encloses a set of points more tightly than a convex hullConvex HullA convex hull is the smallest convex polygon that completely encloses a set of points, analogous to stretching a rubb... by allowing the boundary to curve inward where the point distribution recedes. While a convex hull always produces the smallest convex enclosure, a concave hull sacrifices convexity to better represent the actual shape of the point cloudPoint CloudA point cloud is a large set of three-dimensional data points representing the external surface of objects or terrain....

Several algorithms generate concave hulls. Alpha shapes, introduced by Edelsbrunner in 1983, use a parameter alpha to control the level of detail: smaller alpha values produce tighter, more detailed boundaries while larger values approach the convex hullConvex HullA convex hull is the smallest convex polygon that completely encloses a set of points, analogous to stretching a rubb.... The k-nearest neighbor algorithm constructs the boundary by connecting each point to its k closest neighbors, where k controls the concavity. Chi shapes use a length threshold to remove long Delaunay triangulationDelaunay TriangulationDelaunay triangulation connects a set of points into a network of non-overlapping triangles such that no point lies i... edges. The choice of parameter controls the trade-off between tightness and boundary simplicity.

Ecologists use concave hulls to define species home ranges that follow actual habitat shapes rather than the oversimplified convex polygons. Urban analysts delineate the true footprint of built-up areas from building point data. Search and rescue operations define probable search areas from last-known-position data. Retail analysts outline customer catchment areas that reflect actual spatial patterns. Cartographers generate smooth boundary representations for labeled regions on maps.

Concave hulls produce boundaries that more accurately represent the spatial extent of irregularly distributed data, avoiding the overestimation inherent in convex hulls. However, results are sensitive to the chosen concavity parameter, and there is no universally correct setting. The boundary may fragment into multiple polygons if the point distribution has gaps, and computation is more expensive than for convex hulls.