Journal
COMPUTERS ENVIRONMENT AND URBAN SYSTEMS
Volume 57, Issue -, Pages 48-58Publisher
ELSEVIER SCI LTD
DOI: 10.1016/j.compenvurbsys.2016.01.003
Keywords
Footprint; Non-convex; Delaunay triangulation; Clustering; alpha-Shape; chi-Shape; DBSCAN
Categories
Funding
- ARC [LP120200584]
- Australian Research Council [LP120200584] Funding Source: Australian Research Council
Ask authors/readers for more resources
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available