Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation

Abstract

A new method of cartographic line simplification is presented. Regular hexagonal tessellations are used to sample lines for simplification, where hexagon width, reflecting sampling fidelity, is varied in proportion to target scale and drawing resolution. Tesserae constitute loci at which new sets of vertices are defined by vertex clustering quantization, and these vertices are used to compose simplified lines retaining only visually resolvable detail at target scale. Hexagon scaling is informed by the Nyquist–Shannon sampling theorem. The hexagonal quantization algorithm is also compared to an implementation of the Li–Openshaw raster-vector algorithm, which undertakes a similar process using square raster cells. Lines produced by either algorithm using like tessera widths are compared for fidelity to the original line in two ways: Hausdorff distances to the original lines are statistically analyzed, and simplified lines are presented against input lines for visual inspection. Results show that hexagonal quantization offers advantages over square tessellations for vertex clustering line simplification in that simplified lines are significantly less displaced from input lines. Visual inspection suggests lines produced by hexagonal quantization retain informative geographical shapes for greater differences in scale than do those produced by quantization in square cells. This study yields a scale-specific cartographic line simplification algorithm, following Li and Openshaw's natural principle, which is readily applicable to cartographic linework. Open-source Java code implementing the hexagonal quantization algorithm is available online.

Keywords:

• generalization
• line simplification
• scale specificity
• vertex clustering
• tessellation
• hexagons

Acknowledgements

The author would like to extend many thanks to Cynthia Brewer for her guidance on this and other projects. Krzysztof Janowicz and Alexander Savelyev were both instrumental in their teaching and kind help with programming in Java. Conversations with each of the following persons helped the author develop the ideas in this research, and gratitude is extended to each of them: Barbara Buttenfield, Charlie Frye, Zhilin Li, Donna Peuquet, and Alan Saalfeld. Finally, the author is grateful to the anonymous reviewers, whose comments helped improve the manuscript.