Institute of Theoretical Informatics, Algorithmics

Labeling of dynamic maps

Description

One of the classic problems in cartography is map labeling, i.e., the placement of textual descriptions of (point) features on a map. The underlying challenge in labeling is not limited to maps but it can also be found in many other areas in which image features need to be annotated. Due to the increased availability of interactive maps on the Internet, as well as on personal mobile devices, there are new challenges for labeling those dynamic maps. Most dynamic maps allow a subset of the following three basic continuous operations: panning, zooming, and rotating.

For labeling algorithms the text is usually modeled as a rectangle. The optimization goal for static maps is to maximize the number of visible labels, such that no two labels overlap each other. Translating this optimization goal to the setting of dynamic maps leads to maximizing the number of visible labels over all possible views, such that no two labels overlap each other. For dynamic maps there are additional consistency requirements. During the execution of one of the basic operations no label must suddenly change its size or position, or – to avoid “flickering” – change from being visible to being invisible and back multiple times.

Continuous Rotation

Static maps generally have a natural orientation (usually the northern direction faces upward). For dynamic maps this is not necessarily true. Applications such as pedestrian or car navigation often rotate the map view so that the traveling direction always faces “upward”. We investigate how to maximize the number of visible labels during one full rotation while observing the consistency requirements.

Map where the northern direction faces upward.
Rotated map.

Continuous Zooming

For dynamic maps that support continuous zooming it is desirable that during a full zoom operation the maximum possible number of labels is visible. Zooming out generally induces conflicts between labels, i.e., at some scale labels start to overlap each other. This means that for each conflict it must be determined which label stays visible and which is made invisible. These choices significantly impact the quality of the labeling.

Bad Choice. The label “Karlsruhe” and “Paris” have a conflict very soon.
Good Choice. The conflict is delayed as much as possible.

The relative position of a label to its point feature is a another aspect that impacts the quality of a labeling. A poorly chosen position can lead to many conflicts very soon, while a good position can delay or even avoid conflicts altogether.

We consider these problems and analyze them from an algorithmic point of view.

Unfavorable label position. A conflict occurs very early.
Good label position. A conflict between both labels is avoided.

Trajectory-Based Map Labeling

The trajectory-based map labeling is based on the continuous rotation of maps and it is a further step towards an appropriate presentation of maps on navigation systems. It is assumed that only a rectangular section of the map is displayed to the user and that this section moves along a trajectory on the map such that it is aligned according to its current position on the trajectory. In order to sustain readability, the labels are horizontally aligned with respect to the currently displayed section. Thus, driving along a road's curve means that not only the map rotates, but also the labels.

Map such that the nothern direction faces upwards. The given trajectory is depicted blue and the section that is currently displayed to the user is illustrated by a black rectangle. All possible labels are depicted.
Section that is currently displayed to the user. The labels are horizontally aligned with respect to that section. The labels have been chosen in such a way that there are no overlaps.


In case that the trajectory is not known from the beginning on, one needs to decide online which labels are displayed. However, in the use case of navigation systems start and destination of the planed route are often known in advance so that the complete trajectory can be used in order to obtain a consistent and optimal choice of labels. Using the assumption that the trajectory is given, we develop algorithms that present the user as much additional information as possible without cluttering single frames.

Publications

Journal articles

  1. Ken Been, Martin Nöllenburg, Sheung-Hung Poon, and Alexander Wolff.
    Optimizing Active Ranges for Consistent Dynamic Map Labeling.
    Computational Geometry: Theory and Applications, 43(3):312-328, 2010.
    Special issue of SoCG 2008
    [ html ][ pdf ]

Conference articles

  1. Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
    Consistent Labeling of Rotating Maps.
    In: Algorithms and Data Structures, 12th International Symposium (WADS'11) volume 6844 of Lecture Notes in Computer Science, pages 451-462. Springer, 2011.
    [ html ][ pdf ]
  2. Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
    Sliding Labels for Dynamic Point Labeling.
    In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG '11), pages 205-210. University of Toronto Press, 2011.
    [ pdf ]
  3. Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski.
    Dynamic One-Sided Boundary Labeling.
    In: Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 310-319. ACM Press, November 2010.
    [ html ][ pdf ]