Geometric data for testing implementations of point reduction algorithms : case study using Mapshaper v 0.2.28 and previous versions

Visvalingam, Maheswari

Abstract

There are several 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 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 produced an unexpected loss of symmetry from both the Visvalingam and Douglas-Peucker options, making the tested versions unsuitable for some applications 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 provided in this paper, especially when the source code is not available. The teragon-test is also useful for evaluating other point reduction algorithms.

Citation

Visvalingam, M. Geometric data for testing implementations of point reduction algorithms : case study using Mapshaper v 0.2.28 and previous versions

• Deposit Date: Apr 26, 2016
• Journal: Explorations in digital cartography
• Peer Reviewed: Not Peer Reviewed
• Book Title: Geometric data for testing implementations of point reduction algorithms : case study using Mapshaper v 0.2.28 and previous versions
• Keywords: Teragon-testing implementations of point reduction algorithms by Visvalingam and Douglas-Peucker, Mapshaper
• Public URL: https://hull-repository.worktribe.com/output/436998
• Contract Date: Apr 26, 2016