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.
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.
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.
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.
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
Conference articles
- 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 ]