Simplification of polylines by segment collapse: minimizing areal displacement while preserving area

ABSTRACT

This paper reports on a new Area Preserving Segment Collapse (APSC) algorithm for simplifying polygonal boundaries while preserving the polygonal area at simplified target scales and minimizing areal displacement. A general segment collapse algorithm is defined by iteratively collapsing segments to Steiner points in priority order, guided by placement and displacement functions. The algorithm is specified by defining functions that minimize areal displacement under the constraint that the areas of adjoining polygons are preserved exactly. Self-intersections can be avoided by testing for intersections with two new line segments associated with each segment collapse operation. The paper demonstrates simplification results for a sample of 10 lakes formed from alpine, Karst, glacial and arid desert processes as well as artificial dams. APSC results are compared with three other simplification routines and evaluated for area preservation, linear and areal displacement, complexity and introduction of boundary self-intersections. Results confirm that the APSC algorithm preserves area exactly and indicate that it outperforms the other tested algorithms for minimizing areal displacement while producing reasonably low measures of linear displacement. Self-intersections can occur more commonly with APSC than other algorithms but are avoided with the proposed topology check. The APSC algorithm additionally preserves polygon complexity better than other tested algorithms.

RÉSUMÉ

Ce papier présente un nouvel algorithme appelé APSC (Area Preserving Segment Collapse) pour simplifier les limites polygonales tout en préservant les surfaces à une échelle cible et en minimisant la surface de déplacement. Nous définissons un algorithme de réduction de segment en regroupant de façon récursive des segments aux points de Steiner par ordre de priorité et guidé par des fonctions de positionnement et de déplacement. L’algorithme est spécifié en définissant des fonctions qui minimisent la surface de déplacement sous la contrainte que les surfaces des polygones adjacents soient exactement préservées. Les intersections de la ligne avec elle-même peuvent être évitées en testant les intersections avec deux nouveaux segments de ligne associés à chaque opération de réduction de segment. Le papier présente des résultats de simplification pour un échantillon de 10 lacs formés à partir de processus alpin, karstique, glacier et de désert aride ainsi que des barrages artificiels. Les résultats de l’APSC sont comparés avec trois autres algorithmes de simplification et sont évalués sur des critères de préservation de surface, de déplacement linéaire et surfacique, de complexité et de création d’intersection de la ligne avec elle-même. Les résultats confirment que l’algorithme APSC préserve exactement la surface et montre qu’il surpasse les autres algorithmes testés pour minimiser le déplacement surfacique tout en produisant des valeurs raisonnablement faibles pour le déplacement linéaire. L’auto-intersection peut se produire plus souvent avec l’APSC qu’avec d’autres algorithmes mais ces intersections sont évitées grâce à un contrôle topologique. De plus l’algorithme APSC préserve mieux la complexité des polygones que les autres algorithmes testés.

KEYWORDS:

• Cartographic generalization
• Steiner points
• area preservation

Acknowledgements

The authors appreciate reviewer comments that strengthen the current version of this manuscript.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes on contributors

Barry J. Kronenfeld is Associate Professor of Geography at Eastern Illinois University. His research investigates innovative techniques for modeling, visualizing and analyzing spatial patterns in human and physical landscapes. Recent projects include cartogram construction, spatial interaction, and modeling of gradation in area-class maps. He is currently serving as coordinator for the Professional Science Master's degree program at EIU.

Lawrence V. Stanislawski is a researcher for the Center of Excellence for Geospatial Information Science at the U.S. Geological Survey in Rolla, Missouri. His research interests include multiscale representation and automated generalization of geospatial data, geomorphometry, machine learning and high-performance computing of big data.

Barbara P. Buttenfield is Professor of Geography at University of Colorado-Boulder, a Faculty Research Affiliate at U.S. Geological Survey's Center for Excellence in Geospatial Science. She is Director of the Meridian Lab, a small campus research facility working on projects relating to visualization and modeling of geographic information and technology. Her research focuses on multi-scale geospatial database design, uncertainty representation in environmental modeling, and terrain analysis for natural hazards response.

Tyler Brockmeyer is a Missouri University of Science and Technology Computer Science Graduate. He worked for the U.S. Geological Survey in Rolla Missouri during the writing of this paper. Currently, he is working for Bayer in their Crop Science division.

ORCID

Barry J. Kronenfeld http://orcid.org/0000-0002-9518-2462

Lawrence V. Stanislawski http://orcid.org/0000-0002-9437-0576

Barbara P. Buttenfield http://orcid.org/0000-0001-5961-5809

Additional information

Funding

Dr. Buttenfield’s research forms a portion of work for the Grand Challenge Initiative ‘Earth Lab’ for the Data Harmonization Project, funded by the University of Colorado. https://www.colorado.edu/earthlab/science-projects.