Efficient and consistent line simplification for web mapping

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.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 12 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.