Implications of Weighting Metrics for Line Generalization with Visvalingam's Algorithm

Visvalingam's algorithm was designed for caricatural line generalization. A distinction must be made between the algorithm and its operational definition, which includes the metric used to drive it. When the algorithm was first introduced, it was demonstrated using the concept of the effective area of triangles. It was noted that alternative metrics could be used and that the metrics could be weighted, for example to take account of shape.

Ordnance Survey (Great Britain) and others are using Visvalingam's algorithm for generalizing coastlines and other natural features, with complex parameter-driven functions to weight the original metric. This paper shows how free software and data were used to scrutinize the implications of one of Matthew Bloch's simple and transparent weighting functions. The results look promising, when compared with manually produced mid and small-scale maps; and encourage further research focussed on weighting functions and related topics, such as self-intersection of lines and model-based generalization. The paper discusses why weights were used in some projects. It comments on their range of applicability and reiterates the original guidance provided for the use of weights. It also demonstrates how weights can undermine the algorithm's capacity to draw caricatures with very few points. The paper provides sufficient background and links to the authors’ test data and to open source software for the benefit of others wishing to undertake research in line generalization using Visvalingam's algorithm.     

National Mapping Profiles

This paper provides the background necessary for a clear understanding of forthcoming papers relating to the Visvalingam algorithm for line generalization, for example on the testing and usage of its implementations. It distinguishes the algorithm from implementation-specific issues to explain why it is possible to get inconsistent but equally valid output from different implementations. By tracing relevant developments within the now-disbanded Cartographic Information Systems Research Group (CISRG) of the University of Hull, it explains why (a) a partial metric-driven implementation was, and still is, sufficient for many projects but not for others; (b) why the effective area (EA) is a measure derived from a metric; (c) why this measure (EA) may serve as a heuristic indicator for in-line feature segmentation and model-based generalization; (d) how metrics may be combined to change the order of point elimination; and (e) how Tobler's rule-of-thumb is useful for scale-related filtering of EA. The issues discussed in this paper also apply to the use of other metrics. It is hoped that the background and guidance provided in this paper will enable others to participate in further research based on the algorithm.     

Teragons for Testing Implementations of Point Reduction Algorithms

There are several open source and commercial implementations of the Visvalingam algorithm for line generalization. The algorithm provides scope for implementation-specific interpretations, with different outcomes. This is inevitable and sometimes necessary and, it does not imply that an implementation is flawed. The only restriction is that the output must not be so inconsistent with the intent of the algorithm that it becomes inappropriate. The aim of this paper is to place the algorithm within the literature, and demonstrate the value of the teragon-test for evaluating the appropriateness of implementations; Mapshaper v 0.2.28 and earlier versions are used for illustrative purposes. Data pertaining to natural features, such as coastlines, are insufficient for establishing whether deviations in output are significant. The teragon-test revealed an unexpected loss of symmetry from both the Visvalingam and Douglas-Peucker options, making the tested versions unsuitable for some applications, especially outside of cartography. This paper describes the causes, and discusses their implications. Mapshaper 0.3.17 passes the teragon test. Other developers and users should check their implementations using contrived geometric data, such as the teragon data used in this paper, especially when the source code is not available for inspection. The teragon-test is also useful for evaluating other point reduction algorithms.