Characterizing the shapes of noisy, non-uniform, and disconnected point clusters in the plane

Many spatial analyses involve constructing possibly non-convex polygons, also called “footprints,” that characterize the shape of a set of points in the plane. In cases where the point set contains pronounced clusters and outliers, footprints consisting of disconnected shapes and excluding outliers are desirable. This paper develops and tests a new algorithm for generating such possibly disconnected shapes from clustered points with outliers. The algorithm is called χ-outline, and is based on an extension of the established χ-shape algorithm. The χ-outline algorithm is simple, flexible, and as efficient as the most widely used alternatives, O(n log n) time complexity. Compared with other footprint algorithms, the χ-outline algorithm requires fewer parameters than two-step clustering-footprint generation and is not limited to simple connected polygons, a limitation of χ-shapes. Further, experimental comparison with leading alternatives demonstrates that χ-outlines match or exceed the accuracy of α-shapes or two-step clustering-footprint generation, and is more robust to some forms of non-uniform point densities. The effectiveness of the algorithm is demonstrated through the case study of recovering the complex and disconnected boundary of a wildfire from crowdsourced wildfire reports.