Maurício Gouvêa Gruppi, Salles V. G. de Magalhães, Marcus V. A. Andrade, W. Randolph Franklin, and Wenli Li.
Using rational numbers and parallel computing to efficiently avoid round-off errors on map simplification.
In Geoinfo 2015, XVI Brazilian Symposium on GeoInformatics. Campos do Jordão, SP, Brazil, 29 Nov – 2 Dec 2015.
[full text] [slides] [BibTeX▼]
This paper presents EPLSimp, an algorithm for map generalization that avoids the creation of topological inconsistencies. EPLSimp is based on Visvalingam-Whyatt's (VW) algorithm on which least “important” points are removed first. Unlike VW's algorithm, when a point is deleted a verification is performed in order to check if this deletion would create topological inconsistencies. This was done by using arbitrary precision rational numbers to completely avoid errors caused by floating-point arithmetic. EPLSimp was carefully implemented to be efficient, although using rational numbers adds an overhead to the computation. This efficiency was achieved by using a uniform grid for indexing the geometric data and parallel computing to speedup the process.