Automatic label placement

The automatic positioning of labels is a problem that occurs through geographic information systems, especially in the production of cards, but also on other computer-generated graphics such as charts.

Difficulty

If all labels (eg cities and landscapes ) mounted in the same way, then there is a high probability of overlap that affect readability. Therefore, labels must be moved when attaching, scaled, turned, bent or partially omitted in order to keep the number of overlaps as low as possible. It is an optimization problem; for all non-trivial cases, this problem is NP-hard.

Solutions

A simple greedy algorithm that places the labels in turn and the position of each selected so that the overlap is minimal, often provides even for simple problems, satisfactory results, but is very fast.

More complicated algorithms use local optimizations. For this purpose, the positions of the labels are checked several times; with each pass re-positioning of a single label is tested and maintained if the overall results improved. When a local optimum has been reached, the algorithm ends. This works reasonably well for not too dense labeled cards. An improvement can be achieved, that can be changed for each pass, two or more labels at a time.

The best results are obtained at an acceptable speed using the algorithm of simulated annealing. It basically works as the local optimization, a change may, however, retained even if they initially worsens the overall result. The probability is, the change and the temperature described. At high temperature, many variations are possible, whereby a local optimum can be left; later, at low temperature ( ie at more advanced optimization), deteriorating changes are less possible - here the behavior is similar to the local optimization. The trick is to develop a good evaluation function and a good " cooling rate " (where this mostly a more complicated algorithm is used) to choose - a too rapid cooling will yield poor results, too slow cooling takes too much time.

Also used are evolutionary algorithms such as genetic algorithms or concepts from graph theory.

An important optimization is to split the labels into subsets, which can be solved independently. Two labels are competitors, if there is a placement option in which they overlap; then they belong to the same subset. For cards with uneven distribution of the label can mean a great simplification - at a world map for example, can America be labeled irrespective of Europe.

Implementations

PAL is an open source, programmed in C library for the automatic placement of labels. There are in addition to the generic library ports for gvSIG, QGIS and MapWindow. PAL is from the West University of Switzerland.

PFLP allows the placement of point labels and is being developed at the University of Vienna.

Reference

• Podolskaya NN Automatic exclusion of overlapping of labels for interactive visualizations. Information Technology ( ISSN 1684-6400 ), 9, 2007, p 45 - 50 In the Russian: Подольская Н.Н. АЛГОРИТМЫ АВТОМАТИЧЕСКОГО ОТБРОСА ФОРМУЛЯРОВ ДЛЯ ИНТЕРАК ТИВНЫХ ГРАФИЧЕСКИХ ПРИЛОЖЕНИЙ. Информационные технологии, 9, 2007, с. 45 - 50