Characterizing the shapes of noisy, non-uniform, and disconnected point clusters in the plane. (May 2016)

• Record Type: Journal Article
• Authors: Zhong, Xu; Duckham, Matt
• Is Part Of: Computers, environment and urban systems. Volume 57(2016)
• Page Start: 48
• Page End: 58
• Publication Date: 2016-05
• Subjects: Footprint -- Non-convex -- Delaunay triangulation -- Clustering -- α-Shape -- χ-Shape -- DBSCAN; City planning -- Data processing -- Periodicals; Regional planning -- Data processing -- Periodicals; 303.4834
• DOI: 10.1016/j.compenvurbsys.2016.01.003
• Languages: English
• ISSNs: 0198-9715

Abstract

Abstract: 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. Highlights: A new algorithm, called "χ-outline", was developed for generating disconnected shapes from clustered points with outliers. χ-outlines were compared with two state-of-the-art alternatives: α-shapes and a two-step DBSCAN plus χ-shapes technique. χ-outlines were verified through the case study of recovering boundary of wildfires from crowdsourced wildfire reports. χ-outlines are more accurate than the alternatives especially when the density of point clusters varies systematically.