We consider the problem of labeling dynamic (3D) maps: we develop real-time algorithms that attach non-overlapping annotations to objects on maps which the user can pan, zoom, and rotate continuously. Existing algorithms either label static maps or only a small number of the objects. We consider the problem to label streets and to label points. We label streets either internally or externally. For internal labels, we compute potential label positions for each street, compare them, and decide for one. For external street labels, we apply a force-directed approach; labels behave like electrons. The rst algorithm for labeling points allows labels to slide along their reference points; it makes use of visibilities between labels. The other approach precomputes for each point an interval of zoom levels at which the label can be placed; labelings are queried at run time.
We deal with the problem of labeling dynamic maps. In general, a label is an annotation of an object. So, we assign labels to map objects like cities or streets. We are especially interested in labeling objects of dynamic maps. Dynamics maps are maps with which the user can interact; that is, the user can pan, zoom, or rotate the map, for example, by clicking or dragging the mouse. We particularly consider dynamic maps that provide continuous zooming. Some dynamic maps additionally allow for a 3D view.
In order to react to user interactions (and the associated changes of the map) immediately at run time, we need to developed real-time algorithms for updating labelings.
We completely neglect any type of preselection of the objects to label; our
aim is rather to label many of the e ectively given objects. Neither we want
to compute dynamically changing labelings in the sense of labelings that are
attuned to each single user at each point in time (as the user's interests might
change as well). This is, we use static weights to determine the importance of a
label. Our algorithms must be understood as a nal step in the process of map
generation.
2
(a) initial scale; sparse labeling
(b) more labels after zooming in
Fig. 1. Two maps [
A comprehensive literature review (for a very small one, see Section 2) shows that there has been an abundance of work on static label placement, for example, for printed maps. Publications dealing with labeling dynamic maps are, however, rare; those additionally dealing with a 3D view are even rarer. This is surprising as commercial products such as navigation systems already use such algorithms. The algorithms in these commercial products are not satisfactory, though, since there are often large areas that contain interesting objects but no labels; see Figure 1. This is due to the fact that most systems are very conservative: they block large areas around a labeled point in order to avoid that labels overlap when the user interacts with the map.
To sum up, we want to solve the problem of labelings with few labels (such as generated by many common navigation system) while preventing occlusions of labels as well. That is, we develop algorithms and data structures for placing many, but occlusion-free, labels on dynamic maps in real-time. We also plan to test the real-time capabilities of these algorithms and data structures. Moreover, we should try to nd out whether users accept these approaches and if they bene t from them; especially, we should try to learn if placing as many occlusionfree labels as possible helps or rather confuses the users.
In the following, we describe four work packages dealing with map labeling, namely embedded street labeling (see Section 3), active street labeling (see Section 4), city labeling (see Section 5), and POI labeling (see Section 6). For each of these packages, we characterize the problem, have a look at its contribution, outline an algorithm, and, nally, discuss the current state.
There are many papers dealing with the problem of labeling static maps. There are, however, only few papers for labeling dynamic maps. Thus, most of our approaches are extensions of static labeling algorithms.
Strijk [
Maass and Dollner [
Furthermore, Maass and Dollner [
Van Kreveld et al. [
Been et al. [
Finally, Gemsa et al. [
An embedded label looks and behaves as if it were painted on the street; see
Figure 2. Placing embedded labels is a 2D problem. (We can use the 2D algorithms
for a 3D view without any changes.) We require that each label is easy to read:
it should have a suitable reading direction and a bounded curvature. Moreover,
it must not change its size on the screen at run time due to a zooming operation.
This work package is interesting as, to the best of our knowledge, there is only
one paper dealing with dynamically placing embedded labels to streets. Our
approach is di erent to the existing approach of Maass and Dollner [
In order to save running time, we only label the currently visible part of the map, the view (or probably a slightly larger part). Any interaction with the map results in changes of the view. As a consequence, we have to check for updates to the labeling incessantly. For example, a label could leave the view due to a panning operation (see Figure 3(a)). If no further label for the corresponding street is currently displayed, we have to place a new one. If the user zooms in (see Figure 3(b)), streets grow on the screen (while labels maintain their sizes). This creates space to place further labels. On the other hand, a street shrinks if the user zooms out. Then, we have to test if the street is still large enough to host Main St. Main St.
A t e e r t S ⇒ +
B t e e r t
S SAtreet C tB ttreeS treeS tASt. C tB treeS treeS A t e e r t S − tBSt. C e e r t S
Main Street (a) panning: add new label if current label leaves the view (b) zooming: add label if street gets large enough; remove or replace label if street gets too small (c) rotation: correct reading direction if necessary the already-placed label. If not, we have to test if there is another visible part of the street at which we can place the label instead. Finally, rotating the map results in reversed labels (see Figure 3(c)). We have to correct their orientations.
Our algorithm works roughly as follows. In the rst phase of the algorithm, we compute an initial labeling. In the second phase, we react to interactions. Both phases subdivide streets rst into candidate strips and afterwards into candidates. A candidate is a part of a street that represents a position for a label. A candidate strip is a part of a street that groups together candidates with equal properties. In this case, a candidate strip is the grouping of candidates that overlap the same crossings; see Figure 4 for these notions.
For each street in the view, we determine several candidate strips. Then, we choose for every street at most one candidate strip that does not overlap any other selected strip. Lastly, we subdivide each strip into candidates, evaluate each candidate by its quality (for example, by the number of bends), and place the label at a candidate with the best quality value.
We have partly implemented this algorithm. Thus far, we generate and select candidate strips for the initial and for the dynamic phase. The current implementation runs in real-time on multi-core processors (we have not test single-core processors yet).
The subdivision of candidate strips into candidates and the implementation of the cost function is missing, though. This is complicated, as there are many (weighted) rules that could be included in the cost function. For example, we could take into account the number of bends, the angles of these bends, the centrality of a candidate on the street or the view, and so on. For all these properties, we have to nd costs and weights such that the algorithm yields aesthetic labelings. We should conduct a user study in order to verify the usefulness and aesthetics of the outputs of our approach. 4
In a navigation system, the user has the possibility to select a target. If so, the system computes a route to the speci ed target and highlights the corresponding streets. We call such a street (as long as the user has not passed through it completely yet) an active street. In this work package, we want to label streets in a 3D view. The idea is to use an embedded labeling (see Section 3) for inactive streets and to label active streets via billboards (see Figure 5(a)). A billboard is a label that is always oriented towards the user and usually placed with some distance to the referenced object. Therefore, we use leaders (for example, straight lines) to visualize the correct label{object association. We refer to the rectangle that contains the label text as head. Currently, we require that the leader touches the head in the middle of its the bottom edge. The reaction of billboards to interactions as well as the 3D view are the challenging aspects of this work package. We especially have to ensure correct depths of leaders and heads; see Figure 5(b).
A B (a) active streets labeled with billboards; leaders (centered at heads) maintain label{object associations (b) violated depths; although the reference point of A is nearer, B overlaps A's leader
As far as we know, there is no work discussing the problem of labeling streets
via billboards in a 3D view. There is, however, one single approach that labels
points via billboards [
For labeling active streets, we use a force-directed approach, that is, reference points attract their corresponding heads and heads repel each other. Brie y worded, the algorithm varies the length of the leaders at run time in order to maintain an occlusion-free labeling while the user moves through the map.
We have implemented this approach. Indeed, it works but it has some weaknesses; for example, labels shiver or, without any visual reason, a leader gets abruptly longer. It remains to test if this is a conceptual or an implementation issue. Moreover, there are many variations of the problem we can additionally take into account; for instance, we could allow several contact points.
We expect that the mixed-type of labelings will support the user's orientation signi cantly; not least because billboards prevent the distortion of label texts. We should test this assumption in a user study, though. In a pilot study with static pictures, we already found out that the mixed-type could be accepted. 5
We can distinguish two ways to display cities. On the one hand, in large-scale
maps, cities are displayed as areas. On the other hand, in small-scale maps, cities
are represented by single points. Here, we consider the point labeling problem.
In order to place a large number of labels, we allow any label to slide on its
bottom edge at running time. This problem is interesting in the 2D case as well
as in the 3D case. To the best of our knowledge, there is no other work that
establishes an algorithm for the dynamic version of that problem. Van Kreveld
et al. [
Our algorithm for the 2D case works roughly as follows. To save running time, we again only label the view (or probably a slightly larger part). This is why we have to test incessantly if there are further (so far unlabeled) reference points visible and which city labels have left the view. To make room for placing another occlusion-free label, we allow already-placed labels to slide. For that purpose, we build a simple data structure. For each label `, we store all of the labels that lie left to ` and all of the labels that lie right to `. Additionally, we store the distance between these neighbor labels and `. With the help of this data structure, we can quickly query if a new label overlaps an already-placed one and which labels are a ected if we let labels slide (in favor of the new label). In this way, we can decide either to place or to dismiss the new label.
We have so far implemented the data structure, but have yet to implement an algorithm for sliding labels. Currently, the (partial) implementation runs in real-time on multicore processors although it does not react to interactions by updating the data structure; instead it recomputes the data structure completely in each frame. In order to save running time, we could determine, for each type of interaction, a point in time at which we have to launch the update of the data structure. To reduce the running time even further, we have implemented a waiting function. This means that the algorithm does not check in each frame if an unlabeled point in the view can be labeled but the algorithm waits several frames before it checks this again.
For the 3D case, we have some initial ideas which we have not entirely developed yet. They are mainly an adaption of the 2D approach.
Both the 2D and the 3D algorithm are probably fully real-time capable. We should be caseful about the user acceptance, though. Surely, this approach is a nice add-on for the map mode, that is, when the user navigates the map on his or her own. By contrast, in the navigation mode, the navigation system provides the interactions. In this navigation mode, moving labels could possibly confuse the user rather than help. We should test this in a user study. If users do not accept sliding labels, we just can switch o the movement. This simpli ed approach is even faster and, probably, will still place more labels than algorithms of current commercial systems. We plan to verify this. 6
The result of the following work package has been published at the 16th ICA
Generalisation Workshop [
A point of interest (POI for short) is a place of special interest, for example, a hospital, a restaurant, or a gas station. In navigation systems a POI annotation is typically represented by an icon. An icon is a pictorial label; see Figure 6. Normally, an icon maintains the same size on the screen all the time. So, if the user zooms the map out, the distance between two points of the map gets smaller on the screen or, regarded the other way round, the labels grow with regard to the map background. This generally results in overlapping labels. (Other interaction types do not substantially in uence the current labeling.)
We investigate this problem under the constraint of circular icons with equal
diameters. Additionally, we aim for a consistent labeling. By this we mean that
once a label has vanished, it can only reappear if the user changes the zooming
direction. The idea is to build a data structure in a preprocessing step and to
(a) schematic represen- (b) schematic represen- (c) visualized data structure
(comtation of shrinking-cones tation of growing-cones puted by shrinking-cones heuristic)
heuristic (2D view) heuristic (2D view)
query label positions (from this data structure) at run time quickly. In the data
structure, we represent each label by an interval of zoom levels at which the
label is displayed. We can visualize the intervals (over zoom levels) as (disjoint)
cones; see Figure 7(c). In order to maximize the number of placed labels, the
goal is to maximize the sum over the lengths of all intervals. This problem is
N P-hard [
Our algorithms work roughly as follows. The rst one, see Figure 7(a), starts
with (overlapping) cones of equal heights. In order to prevent overlapping POI
labels, we just cut the cones so that no two cones intersect. This approach is an
adaption of an algorithm introduced by Been et al. [
We compared the results of our heuristics with optimal solutions (computed by the MIP). Due to the high running time of solving the MIP, we only computed the MIP35, that is, we stopped computations as soon as the result of the MIP was not worse than 35% of an optimal solution. Figure 8 shows that our heuristics are much faster than the MIP35 and still yield labelings with a nearly-optimal number of labels. Indeed, we can prove that the growing-cones heuristic yields an approximation ratio of 1=5, that is, the sum over all intervals of an optimal solution is at most ve times larger than the sum of any solution computed by the heuristic. To round o , we can also enhance our algorithms such that they can deal with priorities and even with labels of di erent sizes. Then, however, the proof for the approximation ratio of the growing-cones heuristic does not hold anymore. 1,15 1,10 1,05 1,00 0,95 0,90
MIP2325 Shrinking Cones
Growing Cones 25 50 75 100 175 200 225
249 125 150 size of point sets (a) absolute running times in seconds (log-scale!)
MIP2325 Shrinking Cones Growing Cones 25 50 75 100
125 150 size of point sets 175 200 225 249 (b) total active range height relative to MIP35 Fig. 8. Results of our experiments for synthetic data sets. We uniformly distributed 249 points in the unit square [0; 1]2. For each point set of size n = 25; 50; : : : ; 225 we randomly selected n point of the point set. For each n, we averaged the sum of all heights as well as the running time over ve trials. For n = 249, we did only one trial. We deal with the problem of labeling dynamic maps in an occlusion-free manner; we are especially interested in dynamic maps that allow for continuous zooming. The aim is to place as many labels as possible. In this work, we introduced four work packages, namely, embedded street labeling, active street labeling, city labeling, and POI labeling, sketched some solutions, and described the current state of each of the packages. All in all, wide parts of the concepts are already nished. Mainly, further implementation work is required (for example, speeding up the programs or combining the algorithms). We ideally should conduct a study dealing with the user acceptance (for example, to answer the question if sliding labels does disturb the user). The four work packages are intended to reduce the gap between theory and practice; between papers dealing with static labeling problems and navigation system that already use (poor) algorithms for labeling dynamic maps.