Abstract
We consider the problem of labeling point objects in interactive maps where the user can pan and zoom continuously. We allow labels to slide along the point they label. We assume that each point comes with a priority; the higher the priority the more important it is to label the point. Given a dynamic scenario with user interactions, our objective is to maintain an occlusion-free labeling such that, on average over time, the sum of the priorities of the labeled points is maximized. Even the static version of the problem is known to be NP-hard.
We present an efficient and effective heuristic that labels points with sliding labels in real time. Our heuristic proceeds incrementally; it tries to insert one label at a time, possibly pushing away labels that have already been placed. To quickly predict which labels have to be pushed away, we use a geometric data structure that partitions screen space. With this data structure we were able to double the frame rate when rendering maps with many labels.
Video
We have implemented our heuristic. For our tests, we used a world map from Natural Earth, providing 7,322 cities with priorities. We used four different priorities with the following color coding. The redder a point, the more important it is to label this point and the larger the point's label. Additionally, we have implemented some camera paths. In the following two videos, we show a camera path where all types of interaction (panning, zooming in, zooming out) are executed.
The first video gives an impression of how our heuristic works.
It shows a slightly larger part of the map than
the navigation system would. The extension of the virtual display is indicated by a violet rectangle.
The video shows the interactions in slow motion.
With these two tricks, the viewer can better observe the manifold changes of the labeling.
If the video does not work, you can download it (35.6 MB, DivX-compressed).
The second video reflects a natural speed of interaction; it shows only
the virtual display (e.g., of a navigation system).
If the video does not work, you can download it (17.7 MB, DivX-compressed).
The labelings of the two videos differ a little. This is due to the fact that the order of the tested reference points varies. This, in turn, follows from the speed of the movement.