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.