L. Tsoulos, A. Skopeliti, T. Tzamakou

National Technical University of Athens Greece



This paper presents a comparative study of simplification algorithms and their influence on two elements inherent to linear features: shape and horizontal position. Several line simplification algorithms are evaluated, which use different criteria for vertex rejection. Algorithms are applied to lines with different threshold values to produce generalization results for a number of map scales. The comparison of the results of different algorithms implies that the number of the retained points is fixed.

The evaluation of the results is performed through qualitative assessment (visual comparison) and quantitative assessment, utilizing shape distortion measures and horizontal position displacement measures.

Shape distortion measures are based on the description of the shape of cartographic line utilizing a set of parameters. Recent research resulted to a number of parameters, which describe qualitatively/quantitatively the line shape. The set of parameters (measures) adopted have been selected from a comprehensive list identified in the literature utilizing Principal Components Analysis - PCA. Taking into account the PCA results and cartographic judgment, the following measures were selected: the average magnitude angularity, the error variance and the average angularity. These measures are also used for the clustering of line segments into groups of similar complexity utilizing Cluster Analysis. The same methodology is used for the description of the generalized lines shape, leading to the objective comparison with the original lines.

Horizontal position accuracy measures that express the generalized line displacement are also used: distance measures (Average Euclidean distance, Hausdorff distance) and area displacement measures (the ratio of the area between the original and the generalized line to the length of the line etc.).

Line shape is a critical factor in the evaluation of simplification algorithms. In this study linear features are classified into similar shape groups before generalization e.g. sinuous, smooth etc. This way the influence of simplification algorithms to specific kinds of linear feature shape/character is studied.

The aim of this study is to draw specific conclusions on the results of each simplification algorithm and to establish a generalization strategy, comprised of algorithms and threshold values, appropriate for specific map scales and line features character.