Algorithms for Geovisualisation

The automatic placement of symbols and labels is a cartographic task that poses challenges due to the intricate balance required between providing detailed information and maintaining map clarity. Within the working group, we develop flexible models and efficient algorithms for placing labels for different types of geo-spatial visualizations such as network maps [1] that schematize transportation networks, situation maps [2] for disaster and emergency response, as well as panoramic images [3].

[1] B. Niedermann and J.-H. Haunert (2018). An Algorithmic Framework for Labeling Network Maps. Algorithmica, 80(5), 1493-1533.

[2] S. Gedicke, L. Arzoumanidis, and J.-H. Haunert (2023). Automating the External Placement of Symbols for Point Features in Situation Maps for Emergency Response. Cartography and Geographic Information Science, 50(4):385-402.

[3] A. Gemsa, J.-H. Haunert, and M. Nöllenburg (2015). Multirow Boundary-Labeling Algorithms for Panorama Images. ACM Transations on Spatial Algorithms and Systems, 1(1):1–30.

In many areas of application, data not only has a spatial reference but also provides a temporal component. Such spatio-temporal data captures changes or events that occur over both space and time, allowing for the analysis of how phenomena evolve, move, or change. To do such analysis, interactive interfaces can help to understand and explore the data by providing suitable visualizations. The development of specialized data structures [4, 5, 6] that enable real-time computations for large amounts of data is required to provide such interactive visualizations.

[4] A. Bonerath, B. Niedermann, and J.-H. Haunert (2019). Retrieving alpha-shapes and schematic polygonal approximations for sets of points within queried temporal ranges. In: Proc. of International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '19), 249-258.

[5] A. Bonerath, B. Niedermann, J. Diederich, Y. Orgeig, J. Oehrlein, and J.-H. Haunert (2020). A time-windowed data structure for spatial density maps. In: Proc. of International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL '20), 15-24.

[6] A. Bonerath, Y. Dong, and J.-H. Haunert (2023). An efficient data structure providing maps of the frequency of public transit service within user-specified time windows. Advances in Cartography and GIScience of the ICA, 4:1.

Interactive map applications pose challenges for the visualization of spatial information. Due to basic operations such as rotating, zooming, and panning the map, the visualization of information must be adapted to changes in the map. One important criterion that needs to be taken into account is consistency [7, 8, 9]. To be able to associate successive visualizations when interacting with the map, features and labels must be represented and placed in a consistent manner.

[7] D. Peng, A. Wolff, J.-H. Haunert (2016). Continuous Generalization of Administrative Boundaries Based on Compatible Triangulations. In: Geospatial Data in a Changing World. Lecture Notes in Geoinformation and Cartography, 399-415.

[8] D. Peng, A. Wolff, and J.-H. Haunert (2020). Finding Optimal Sequences for Area Aggregation—A⋆ vs. Integer Linear Programming. ACM Transactions on Spatial Algorithms and Systems (TSAS) 7.1:1-40.

[9] S. Gedicke, A. Jabrayilov, B. Niedermann, P. Mutzel, J.-H. Haunert (2021). Point feature label placement for multi-page maps on small-screen devices. Computers & Graphics, 100:66-80.

Especially in mobile maps on small-screen devices, users often need to zoom in to an extremely large scale to access detailed information of a map. This reduces the map area available for spatial orientation and causes the larger context to be lost. One concept to overcome this problem is the use of so-called focus+context maps [10, 11, 12, 13]. Such maps introduce a focus region – typically represented as a circular lens – that shows the user's area of interest at a larger scale than the surrounding context map. One of the most challenging tasks with such maps is to create a transition between the two regions that balances smoothness and distortion.

[10] J.-H. Haunert and L. Sering (2011). Drawing Road Networks with Focus Regions. IEEE Transactions on Visualization and Computer Graphics (Proc. Information Visualization 2011), 17(12):2555–2562.

[11] T. C. van Dijk and J.-H. Haunert (2014). Interactive focus maps using least-squares optimization. International Journal of Geographical Information Science, 28:10, 2052-2075.

[12] J.-H. Haunert and T. Hermes (2014). Labeling circular focus regions based on a tractable case of maximum weight independent set of rectangles. Proc. of 2nd ACM SIGSPATIAL International Workshop on Interacting with Maps.

[13] B. Niedermann and J.-H. Haunert (2019). Focus+context map labeling with optimized clutter reduction. International Journal of Cartography, 5:2-3, 158-177.

Rather than using the simultaneous display of different map scales to maintain environmental context, the idea behind zoomless maps is to avoid zooming at all [14, 15, 16]. Such maps provide specialized interaction techniques that allow a user to explore dense maps while staying on a relatively small scale. A user can interactively browse through the information (e.g., labels) while both the map scale and the displayed map section remain fixed.

[14] S. Gedicke, B. Niedermann, J.-H. Haunert (2019). Multi-page Labeling of Small-screen Maps with a Graph-coloring Approach. In: Advances in Cartography and GIScience of the ICA, 2.

[15] S. Gedicke, A. Bonerath, B. Niedermann, and J.-H. Haunert (2021). Zoomless Maps: External Labeling Methods for the Interactive Exploration of Dense Point Sets at a Fixed Map Scale. IEEE Transactions on Visualization and Computer Graphics, 27(2):1247-1256.

[16] S. Gedicke, and J.-H. Haunert (2023). An Empirical Study on Interfaces for Presenting Large Sets of Point Features in Mobile Maps. The Cartographic Journal.

When handling with multiple sets of elements, set visualization is an important branch of information visualization. Vivid and intuitive visualizations of sets bring clarity to complex relationships and structures and illuminate patterns that would otherwise remain hidden in raw data. Developing suitable visualization techniques and deciding on the final rendering of the sets are challenging tasks [17].

[17] P. Rottmann, M. Wallinger, A. Bonerath, S. Gedicke, M. Nöllenburg, and J.-H. Haunert (2022). MosaicSets: Embedding Set Systems into Grid Graphs. IEEE Transactions on Visualization and Computer Graphics, 29(1):875-885.