Focus+context map labeling with optimized clutter reduction

ABSTRACT

Zooming is a basic operation that many digital maps support for exploring them interactively. Especially for maps on small screen devices, this is a helpful operation to uncover the user's region of interest possibly hidden by labels, e.g. points of interest represented by icons. However, by scaling the map larger the user loses the context. As a consequent the user might need to repeatedly zoom in and out to explore the map step by step.We present an approach that reduces the necessity of zooming by providing the user with the possibility of displacing the labels of a circular focus region. To that end, we utilize techniques from focus+context maps implementing the displacement of the labels by fish-eye projections. The visual association between labels and their point features is established by connecting lines aggregated to bundles. Our approach particularly guarantees that labels move smoothly when the user continuously shifts the focus region, which reduces distracting flickering effects while exploring the map by panning the map view. Further, when the user stops moving the focus region, mathematical programming is applied to optimize positions of the displaced labels. In an evaluation on real-world data and synthetically generated data, we show that our approach substantially increases the legibility of both the focus region and the displaced labels.

RÉSUMÉ

Le zoom est une fonction de base que propose la plupart des éditeurs de cartes pour faciliter l'exploration interactive. C'est une opération particulièrement utile pour les cartes que l'on affiche sur petits écrans pour rendre visible des zones d'intérêt possiblement cachées par des étiquettes, par exemple les points d'intérêts représentés par des symboles. Pourtant, en augmentant l'échelle de la carte l'utilisateur perd le contexte. En conséquence l'utilisateur risque de devoir faire de façon répétitive des zooms avant et arrière pour explorer la carte petit à petit. Nous présentons une approche qui diminue le besoin de zoomer en permettant à l'utilisateur de déplacer les étiquettes dans une région circulaire de focalisation. Pour cela, nous utilisons la technique utilisée pour les cartes de type focus+contexte en implémentant le déplacement des étiquettes par projection fish-eye. L'association visuelle entre les étiquettes et les objets ponctuels est assurée en connectant les lignes agrégées en grappe. Notre approche garantit en particulier le fait que les étiquettes se déplacent sans à-coups lorsque l'utilisateur modifie la zone de focus ce qui réduit les effets de scintillements qui sont gânants lorsqu'on explore une carte en effectuant des déplacements. De plus, quand l'utilisateur cesse de se déplacer, un programme mathématique est appliqué pour optimiser les positions des étiquettes. Grâce à une évaluation sur des données réelles et des données de simulation nous montrons que notre approche améliore significativement la zone de focalisation ainsi que le placement des étiquettes.

KEYWORDS:

• Label placement
• interactive maps
• fish-eye projection
• focus+context maps
• mathematical programming

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes on contributors

Benjamin Niedermann received his Diploma and doctoral degrees in informatics from Karlsruhe Institute of Technology (KIT), Germany, in 2012 and 2017. Currently, he is a postdoctoral researcher at the Institute of Geodesy and Geoinforamtion at the University of Bonn, Germany. His research interests include Geometric Algorithms and Computational Cartography with focus on label placement in maps and figures.

Jan-Henrik Haunert chairs the Geoinformation Group at the Institute of Geodesy and Geoinformation at the University of Bonn, Germany. He holds a diploma and doctoral degree from the University of Hannover, Germany, where in 2008 he defended his dissertation on map generalization by combinatorial optimization. Thereafter, he worked as a postdoctoral researcher at the algorithms group at the University of Würzburg, Germany. From 2013 to 2016 he was a professor for Geoinformatics at the University of Osnabrück, Germany, before in 2016 he took up his professorship in Bonn. His research is dealing with the development of algorithms for the analysis and visualization of spatial information. A current research focus is on developing algorithms for map labeling and map generalization for interactive maps on small screens.

Notes

1. A prototypical demo version written in JavaScript can be tested via www2.geoinfo.uni-bonn.de/html/fisheyelabeling/.

2. www.gurobi.com

3. www2.geoinfo.uni-bonn.de/html/fisheyelabeling/