Variable-scale maps in real-time generalisation using a quadtree data structure and space deforming algorithms

Abstract

Variable-scale maps have been advocated by several authors in the context of mobile cartography. In the literature on real-time map generalisation, however, corresponding methods that resolve cartographic conflicts by deformation of the underlying map space together with the map foreground, are underrepresented. This paper demonstrates how the concept of a malleable space can be applied as a part of the generalisation process and incorporated into the overall methodology of point generalisation. Two different algorithms are used, a density-equalising cartogram algorithm and Laplacian smoothing. Both methods work in real-time and are data-driven. In addition, they allow for a parameterisation in combination with a quadtree data structure, as well as a combination with ’classic’ generalisation operators (e.g. selection, aggregation, displacement) based on the quadtree. The quadtree serves both as a spatial index for fast retrieval and search of points, and as a density estimator to inform generalisation operators. The use of the quadtree as a common spatial index provides a tool to combine variable-scale maps with classic generalisation. A combination of the two allows, at small map scales, the maintenance of detail in dense areas and data reduction in sparse areas. Additionally, it facilitates building a modular workflow for real-time map generalisation.