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

Paulo Raposo*

*Corresponding author for this work

Research output: Contribution to journalArticleAcademicpeer-review

45 Citations (Scopus)


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. © 2013

Original languageEnglish
Pages (from-to)427-443
Number of pages17
JournalCartography and geographic information science
Issue number5
Publication statusPublished - 1 Nov 2013
Externally publishedYes


  • generalization
  • hexagons
  • line simplification
  • scale specificity
  • tessellation
  • vertex clustering
  • n/a OA procedure


Dive into the research topics of 'Scale-specific automated line simplification by vertex clustering on a hexagonal tessellation'. Together they form a unique fingerprint.

Cite this