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.
RBC. Revista Brasileira de Cartografia (Online), 68:1221–1230, 2016.
online at \url http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857.
[full text]
BibTeX
@article{mauricio-rational-rbc-2016,
author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
journal = "RBC. Revista Brasileira de Cartografia (Online)",
year = "2016",
volume = "68",
pages = "1221-1230",
note = "online at \url{http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857}",
href = "\bibhref{221-mauricio-rational-rbc-2016}",
mykey = "wenlili marcus salles parallel"
}
Abstract
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 speed up the process. As result, simplified models completely free of topologically inconsistent results and round-off errors due to the use of multiple precision rational numbers. In addition, there was a considerable speedup arising from the use of parallel computing.
Full text
Read the paperThe full text opens at its existing location.
Preview the full text on this page
Citation
@article{mauricio-rational-rbc-2016,
author = "Gruppi, Maurício Gouvêa and de Magalhães, Salles V. G. and Andrade, Marcus V. A. and Franklin, W. Randolph and Li, Wenli",
title = "Using Rational Numbers and Parallel Computing to Efficiently Avoid Round-Off Errors on Map Simplification",
journal = "RBC. Revista Brasileira de Cartografia (Online)",
year = "2016",
volume = "68",
pages = "1221-1230",
note = "online at \url{http://www.lsie.unb.br/rbc/index.php/rbc/article/view/1857}",
href = "\bibhref{221-mauricio-rational-rbc-2016}",
mykey = "wenlili marcus salles parallel"
}