Automatic positioning of labels
The automatic positioning of labels is a problem that occurs primarily in the generation of maps by geographic information systems, but also with other computer-generated graphics such as diagrams .
difficulty
If all lettering (e.g. of cities and landscapes) is applied in the same way, there is a high probability that there will be overlaps afterwards, which will impair legibility. Therefore, labels have to be moved, reduced, rotated, bent or partially omitted when attaching in order to keep the number of overlaps as low as possible. So it is an optimization problem ; for all nontrivial cases this problem is NP-hard .
Possible solutions
A simple greedy algorithm , which places the labels one after the other and chooses the position in each case so that the overlap is minimal, often does not give satisfactory results even for simple problems, but it is very fast.
More complicated algorithms use local optimizations. For this purpose, the positions of the labels are checked several times; Repositioning a single label is attempted on each pass and maintained if this improves the overall result. When a local optimum has been reached, the algorithm ends. This works relatively well for cards that are not too densely labeled. An improvement can be achieved by changing two or more labels at once for each pass.
The best results at an acceptable speed are obtained with the simulated cooling algorithm . In principle, it works like local optimization, but it can also maintain a change if it initially worsens the overall result. The probability for this is , where describes the change and the temperature. Many changes are possible at high temperatures, which means that a local optimum can be left; later, at a lower temperature (i.e. with more advanced optimization), less deteriorating changes are possible - the behavior here is similar to local optimization. The trick is to develop a good evaluation function and to choose a good "cooling speed" (whereby a more complicated algorithm is usually used for this) - cooling too fast gives poor results, cooling too slow takes too much time.
Also be used evolutionary algorithms such. B. the genetic algorithms or concepts from graph theory .
An important optimization is the division of the labels into subsets that can be solved independently of each other. Two labels are competitors if there is some placement where they overlap; then they belong in the same subset. This can be a great simplification for maps with an uneven distribution of the lettering - for example, America can be labeled independently of Europe on a world map.
Implementations
PAL is an open source library programmed in C ++ for the automatic placement of labels. In addition to the generic library, there are ports for gvSIG , QGIS and MapWindow . PAL comes from the Western University of Switzerland.
PFLP enables the placement of point labels and is being developed at the University of Vienna.
literature
- NN Podolskaya: Automatic exclusion of overlapping of labels for interactive visual presentations . In: Informationstechnologien , 9, 2007, pp. 45-50, ( ISSN 1684-6400 ). Russian: Н.Н. Подольская: АЛГОРИТМЫ АВТОМАТИЧЕСКОГО ОТБРОСА ФОРМУЛЯРОВ ДЛЯ ИНТЕРАК ТИВНЫХ ГРАФИЧЕСКИХ ПРИЛОЖЕН Информационные технологии, 9, 2007, с. 45-50.