Skip to main content
U.S. flag

An official website of the United States government

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

July 30, 2019

This paper reports on a new Area Preserving Segment Collapse (APSC) algorithm for simplifying polygonal boundaries while preserving 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.

Publication Year 2020
Title Simplification of polylines by segment collapse: Minimizing areal displacement while preserving area
DOI 10.1080/23729333.2019.1631535
Authors Barry J. Kronenfeld, Larry Stanislawski, Barbara P. Buttenfield, Tyler Brockmeyer
Publication Type Article
Publication Subtype Journal Article
Series Title International Journal of Cartography
Index ID 70210904
Record Source USGS Publications Warehouse
USGS Organization Center for Geospatial Information Science (CEGIS)