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 chi-outline, and is based on an extension of the established chi-shape algorithm. The chi-outline algorithm is simple, flexible, and as efficient as the most widely used alternatives, O(n logn) time complexity. Compared with other footprint algorithms, the chi-outline algorithm requires fewer parameters than two-step clustering-footprint generation and is not limited to simple connected polygons, a limitation of chi-shapes. Further, experimental comparison with leading alternatives demonstrates that chi-outlines match or exceed the accuracy of alpha-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. (C) 2016 Elsevier Ltd. All rights reserved.