Testing implementations of Visvalingam's algorithm for line generalisation

Visvalingam, Maheswari

Abstract

There are a growing number of open source and commercial implementations of the Visvalingam algorithm for line generalisation. The algorithm provides scope for implementation-specific interpretations, with different outcomes. This is inevitable and sometimes necessary and, they do not necessarily 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 unusable. This paper provides some ideas, data and sample output to help users compare the output from their implementations with those produced by Visvalingam. This may help them ascertain whether some problems they may encounter appear to be specific to their implementation or whether they are a general feature of the algorithm. This paper assesses the utility and limitations of the Mapshaper options for Visvalingam’s algorithm. Similar, but not identical, depictions of coastlines are produced by Visvalingam’s implementation and by Mapshaper. However, the programs produce very dissimilar output for the rectangular Koch island, also known as the quadratic Koch island - Mapshaper’s output is unbalanced for both its Visvalingam and Douglas-Peucker options. This suggests that the problem, which is not immediately obvious, is in some function inherited by both options. Both programs produce near identical output when Mapshaper’s Visvalingam/weighted area option was compared using coastlines. This suggests that the problem arises from Mapshaper’s treatment of equal-valued metrics; this can be changed. Implementers and users may wish to use the data and methods given in this paper to test their own implementations if and when necessary.

Citation

Visvalingam, M. Testing implementations of Visvalingam's algorithm for line generalisation

• Deposit Date: May 12, 2015
• Journal: Explorations in digital cartography discussion paper series. Discussion paper; 3
• Peer Reviewed: Not Peer Reviewed
• Book Title: Testing implementations of Visvalingam's algorithm for line generalisation
• Keywords: Visvalingam algorithm for line generalisation
• Public URL: https://hull-repository.worktribe.com/output/373618