Algorithms for Interactive Variable-Scale Maps

• Applicant: Professor Dr.-Ing. Jan-Henrik Haunert
• Subject Area: Theoretical Computer Science
• Term: from 2011 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 195378132

• Final Report Year: 2015

Final Report Abstract

We have developed algorithms for continuous map generalization, variable-scale label placement, and map-layout generation. Before we developed an algorithm, we always formalized the respective task as an optimization problem. Therefore, the project has not only resulted in efficient exact algorithms and heuristics for application in real-time visualization systems, but also in models of quality for a variable-scale map, with which we refer to a sequence or continuum of maps that covers an interval of scales or to a single map that displays different regions at different scales. Our algorithms for map-layout generation enlarge user-selected focus regions in a road network map without changing the map’s size or the displayed part of the network. They reduce the scale of non-focus regions and introduce some distortion to compensate for the scale differences in the map. The distortion is much lower, however, than with existing fish-eye projections for similar tasks. Our first algorithm relies on convex quadratic programming and produces realistically-sized maps within a few seconds. A better performance, which allows for applications in real-time systems, is obtained by a second algorithm based on least-squares optimization. For the second algorithm we had to relax some of the originally hard constraints of our model. Still, it yields solutions of high cartographic quality. Regions that are demagnified by our method obviously tend to appear cluttered in the output map. For this reason, but also to generate maps supporting continuous zooming, we have developed methods that select a subset of all road segments for a map. We have developed a probabilistic model of how humans navigate a city, which allows us to quantify the importance of every road segment. The aim is to select segments of preferably high importance while satisfying certain constraints about the output map, for example, to ensure that the network appears not too cluttered and is connected. We have studied different models of connectivity and, in some cases, have been able to prove that the selection problem is NP-hard. For several selection problems of practical relevance, however, we have found efficient exact algorithms. For the NP-hard cases we have developed approaches by integer programming, approximation algorithms, and heuristics. With respect to map labeling, we have considered the problem of placing text for points and linear objects in interactive maps that allow users to pan, zoom, and rotate continuously. Our general aim is to label as many objects as possible (on average over time in a dynamic setting) such that no two labels overlap. For this task, we have concentrated on the development of real-time-capable heuristics. Finally, we have developed a method for labeling linear objects in interactive 3D maps that provide a perspective view of a scene. Labels are displayed as billboards. Based on a model of forces, the method avoids overlaps between labels. At the same time, the method ensures that labels are close to their corresponding objects. To conclude, we have contributed many new algorithms to the rapidly growing market for web cartography, location-based services, and navigation systems. An important open question emerging from our project is how dynamic but reasonably stable (i.e., not abruptly changing) visualizations of networks can be produced.

Publications

• A probabilistic model for road selection in mobile maps. In Proc. 12th Int. Sympos. Web and Wireless Geograph. Inform. Systems (W2GIS’13), volume 7820 of Lecture Notes in Computer Sci., pages 214–222. Springer-Verlag, 2013
  T. C. van Dijk and J.-H. Haunert
  
• Road segment selection with strokes and stability. In Proc. 1st ACM SIGSPATIAL Workshop MapInteraction, pages 72–77, 2013
  T. C. van Dijk, K. Fleszar, J.-H. Haunert, and J. Spoerhase
  
• How to eat a graph: Computing selection sequences for the continuous generalization of road networks. In Proc. 22nd ACM SIGSPATIAL Int. Conf. Advances in Geograph. Inform. Systems (ACM-GIS’14), pages 243–252, 2014
  M. Chimani, T. C. van Dijk, and J.-H. Haunert
  
• Interactive focus maps using least-squares optimization. International Journal of Geographical Information Science, 28(10):2052–2075, 2014
  T. C. van Dijk and J.-H. Haunert
  
• Labeling streets in interactive maps using embedded labels. In Proc. 22nd ACM SIGSPATIAL Int. Conf. Advances in Geograph. Inform. Systems (ACM-GIS’14), pages 517–520, 2014
  N. Schwartges, A. Wolff, and J.-H. Haunert
  
• Map schematization with circular arcs. In Proc. 8th Int. Conf. Geograph. Inform. Sci. (GIScience’14), volume 8728 of Lecture Notes in Computer Sci., pages 1–17. Springer-Verlag, 2014
  T. C. van Dijk, A. van Goethem, J.-H. Haunert, W. Meulemans, and B. Speckmann
  
• Point labeling with sliding labels in interactive maps. In Proc. 17th AGILE Int. Conf. Geograph. Inform. Sci. (AGILE’14), Lecture Notes in Geoinform. and Cartography, pages 295–310. Springer-Verlag, 2014
  N. Schwartges, J.-H. Haunert, A. Wolff, and D. Zwiebler
  
• Labeling streets along a route in interactive 3d maps using billboards. In Proc. 18th AGILE Int. Conf. Geograph. Inform. Sci. (AGILE’15), Lecture Notes in Geoinform. and Cartography, pages 269–287. Springer-Verlag, 2015
  N. Schwartges, B. Morgan, J.-H. Haunert, and A. Wolff