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 datadriven. In addition, they allow for a parameterisation in combi-nation 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.

RÉSUMÉ

Les cartes en anamorphoses ont été utilisées par différents auteurs dans le contexte de la cartographie mobile. Pourtant dans la littérature sur la généralisation cartographique en temps réel, on peut constater que ce type de méthodes, qui résout des conflits cartographiques en déformant conjointement le fond de carte et les données importantes, est sous représenté. Ce papier montre comment le concept d’espace malléable peut être appliqué au processus de généralisation et incorporé à la méthodologie globale de généralisation de points. Nous utilisons deux différents algorithmes : un algorithme d’égalisation des densités et un lissage Laplacien. Les deux méthodes fonctionnent en temps réels et sont guidées par les données. De plus, elles peuvent être paramétrées soit pour une structure de quadtree soit en combinaison avec d’autres opérateurs classiques de généralisation (par exemple les opérateurs de sélection, d’agrégation ou de déplacement) basés sur un quadtree. Le quadtree est utile soit en tant qu’index spatial pour retrouver rapidement des points soit comme un estimateur de densité pour guider les opérateurs de généralisation. L’utilisation de quadtree comme index spatial partagé est un moyen qui permet de combiner la cartographie à échelle variable (les anamorphoses) avec la généralisation classique. La combinaison des deux techniques permet, pour les petites échelles, de maintenir du détail dans les zones denses et de réduire les données dans les zones clairsemées. De plus cela facilite la construction d’une approche modulaire pour la généralisation cartographique en temps réel.

KEYWORDS:

• Map generalisation
• real-time map generalisation
• quadtree
• cartogram
• Laplacian smoothing

Acknowledgements

The research reported in this paper represents part of the PhD project of the first author. The authors would like to thank Alistair Edwardes and Christian Kaiser for providing their source code for Laplacian smoothing and cartogram algorithm, respectively.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes on contributors

Pia Bereuter is a Professor of Geographic Information Science at the Institute of Geomatics Engineering, School of Architecture, Civil Engineering and Geomatics of the University of Applied Sciences and Arts Northwestern Switzerland (FHNW).

Robert Weibel is a Professor of Geographic Information Science in the Department of Geography of the University of Zurich (UZH).

ORCID

Pia Bereuter http://orcid.org/0000-0001-8127-2654

Additional information

Funding

Funding by the Swiss National Science Foundation through the project Generalisation for Portrayal in Web and Wireless Mapping (GenW2+) (grant no. 200020-138109) is gratefully acknowledged; Schweizerischer Nationalfonds zur Förderung der Wissenschaftlichen Forschung.