Dynamic Labeling - Active Range Optimization Problems - Experimental Results, by R. G. Cano, C. C. de Souza and P. J. de Rezende

Citing this page:

    Use the BibTeX entry:

    @Misc{csr2017,
     author = {Rafael G. Cano and Cid C. de Souza and Pedro J. de Rezende},
     title = {Dynamic Labeling -- Experimental Results},
     year = {2017},
     note = {{\sl www.ic.unicamp.br/$\sim$cid/Problem-instances/Dynamic-Labeling}}
    }

Problem description

We study labeling problems for point features on interactive maps. Such maps allow users to execute operations to alter the state of the visualization. Two of the most common operations are rotation and scaling. For readability purposes, as one of these operations is executed, labels must maintain their size, shape and orientation on the screen. This may cause labels that were previously disjoint to overlap (see Fig. 1). We handle overlaps by omitting one or more labels from the visualization during specific intervals of angles or scales.


Figure 1: Original map (left), result after a clockwise rotation (middle) and after zooming out (right).

For each label, we must determine a set of active ranges (i.e., intervals of angles or scales during which the label is visible in the visualization of the map) such that no pair of overlapping labels is ever active simultaneously. The objective is to maximize the total length of the active ranges of all labels. In order to prioritize some labels, they may also have associated weights. This problem is known as the Active Range Optimization Problem.

Besides avoiding conflicts, good visualizations must also be consistent, i.e., they must not have any unpleasant or distracting visual effects. In particular, in a good labeling, labels must not pop (i.e., repeatedly appear and disappear) on the screen. In our labeling model, popping may occur if a label has too many active ranges. In such cases, labels appear to flicker on the screen as the user rotates or scales the map. To avoid this, we limit the number of active ranges that a label can have. The KR-model is defined as a labeling model in which each label may have at most K active ranges.

Finally, in some applications, the occlusion of point features might be undesirable, since they may convey useful information even if their associated labels are inactive. In such cases, we do not allow a label to be active if it contains other point features. This additional requirement gives rise to the hard conflict model, in which neither overlaps nor point occlusions are allowed. If only overlaps are forbidden, we have the soft conflict model.

Input Instances

We used two sets of maps constructed from real-world data and made available by Gemsa et al. [1]. The first set was built from data on the most populous cities in six countries (France, Germany, United Kingdom, Italy, Japan and USA) using cartographic scales of 65pixel = 20km, 50km and 100km. The second set is based on data from restaurants in four cities (Berlin, London, New York and Paris) and uses cartographic scales of 65pixel = 20m, 50m, and 100m. Each input file specifies the position and size of all labels, and their position relative to their associated anchors.

The original instances can be downloaded at the authors' website:
http://i11www.iti.kit.edu/projects/dynamiclabeling/.

To experiment with the weighted variant of the problem, we gathered data on the population of all cities in the first set of maps. We used these values as weights to prioritize the most populous cities. It was necessary to modify some of the input files because the original ones contained cities with duplicate names (this might happen, e.g., if two cities belong to different counties or states). No changes were made to the set of labels or to their sizes and locations. We simply changed the text of each label so that they become unique.

Our modified input files can be downloaded here:
City instances (with weights) (94.5 K).

Experimental Results

We ran our experiments on an Intel Xeon CPU X3470, 2.93 GHz, with 8 GB RAM. Integer programs were solved with CPLEX 12.5.1 using traditional search with a single thread. The code was written in C++ and compiled with gcc 5.4.0. We considered both the unweighted and the weighted variants of the problem. We tested an integer programming formulation from [1] with the soft and the hard conflict models, using 1R, 2R and 3R (recall that model KR allows at most K active ranges per label). We experimented with two operations: rotation and scaling.

Our complete set of results that were reported in [2, 3] can be downloaded here:
Results (ODS format) (131.7 K),
Results (CSV format) (25.6 K).

Acknowledgments

This work was supported by Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), grant 2012/00673-2, and Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq), grants #155498/2016-9, #311140/2014-9 and #304727/2014-8.

References

  • [1] Evaluation of Labeling Strategies for Rotating Maps, A. Gemsa, M. Nöllenburg, I. Rutter, ACM Journal of Experimental Algorithmics 21 (1) (2016) 1.4:1–1.4:21.
  • [2] Fast Optimal Labelings for Rotating Maps, R. G. Cano, C. C. de Souza, P. J. de Rezende, In: WALCOM: Algorithms and Computation (WALCOM 2017), vol. 10167 of LNCS, Springer, 161–173, 2017.
  • [3] Solving Dynamic Labeling Problems to Optimality Using Solution Space Reductions, R. G. Cano, C. C. de Souza, P. J. de Rezende, submitted (2017).

Address

Rafael G. Cano, Cid C. de Souza and Pedro J. de Rezende
Universidade Estadual de Campinas
Instituto de Computação
Av. Albert Einstein, 1251
13083-852, Campinas, SP, Brazil
Phone: +55 19 3521.5877
Fax: +55 19 3521.5847
e-mail: