Title: Efficient and consistent line simplification for web mapping

Authors: Michela Bertolotto, Min Zhou

Addresses: School of Computer Science and Informatics, University College Dublin, Belfield, Dublin 4, Ireland. ' School of Computer Science and Informatics, University College Dublin, Belfield, Dublin 4, Ireland

Abstract: Commercial Geographical Information Systems (GISs) incorporate line simplification functionality to generate generalised versions of maps. A commonly used algorithm is the classical Ramer-Douglas-Peucker (RDP) algorithm. Such an algorithm does not guarantee the preservation of topological consistency and therefore requires a posteriori checks to rectify unwanted intersections. To overcome this problem, Saalfeld proposed a modification based on the fact that, while generalising a polyline, conflicts can only occur with vertices of other polylines that lie within its convex hull. We have developed an improved version of Saalfeld|s algorithm to detect possible self-intersections more efficiently. Although this improves the performance, especially when generalising very large data sets, the processing time is still not acceptable for real-time web mapping. Therefore, we have integrated our algorithm into a web-mapping system that relies on progressive transmission. In this paper we describe our improved algorithm and the experimental results. We also discuss the progressive transmission approach.

Keywords: map generalisation; multiple map representations; progressive vector transmission; line simplification; web mapping; GIS; geographical information systems; web GIS.

DOI: 10.1504/IJWET.2007.012051

International Journal of Web Engineering and Technology, 2007 Vol.3 No.2, pp.139 - 156

Published online: 15 Jan 2007 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article