Die automatische Positionierung von Beschriftungen ist ein Problem, das vor allem bei der Erzeugung von Karten durch Geoinformationssysteme auftritt, jedoch auch bei anderen computergenerierten Grafiken wie beispielsweise Diagrammen.
Schwierigkeit
Wenn alle Beschriftungen (z. B. von Städten und Landschaften) auf die gleiche Art angebracht werden, gibt es danach mit hoher Wahrscheinlichkeit Überlappungen, die die Lesbarkeit beeinträchtigen. Daher müssen Beschriftungen beim Anbringen verschoben, verkleinert, gedreht, gebogen oder teilweise auch weggelassen werden, um die Anzahl der Überlappungen möglichst gering zu halten. Es handelt sich also um ein Optimierungsproblem; für alle nichttrivialen Fälle ist dieses Problem NP-schwer.
Lösungsansätze
Ein einfacher Greedy-Algorithmus, der die Beschriftungen der Reihe nach platziert und die Position jeweils so wählt, dass die Überlappung minimal ist, liefert oft nicht einmal für einfache Problemstellungen zufriedenstellende Ergebnisse, ist jedoch sehr schnell.
Kompliziertere Algorithmen verwenden lokale Optimierungen. Dazu werden die Positionen der Beschriftungen mehrfach überprüft; bei jedem Durchgang wird eine Neupositionierung einer einzelnen Beschriftung ausprobiert und beibehalten, falls sich das Gesamtergebnis dadurch verbessert. Wenn ein lokales Optimum erreicht wurde, endet der Algorithmus. Dies funktioniert für nicht zu dicht beschriftete Karten relativ gut. Eine Verbesserung kann dadurch erreicht werden, dass bei jedem Durchgang zwei oder mehrere Beschriftungen auf einmal verändert werden.
Die besten Ergebnisse bei akzeptabler Geschwindigkeit erhält man mit dem Algorithmus der simulierten Abkühlung. Er funktioniert prinzipiell wie die lokale Optimierung, kann eine Veränderung aber auch dann beibehalten, wenn sie das Gesamtergebnis vorerst verschlechtert. Die Wahrscheinlichkeit dafür beträgt , wobei die Veränderung und die Temperatur beschreibt. Bei hoher Temperatur sind viele Veränderungen möglich, wodurch ein lokales Optimum verlassen werden kann; später, bei niedriger Temperatur (also bei weiter fortgeschrittener Optimierung), sind weniger verschlechternde Veränderungen möglich – das Verhalten ist hier ähnlich der lokalen Optimierung. Die Kunst ist es, eine gute Bewertungsfunktion zu entwickeln und eine gute „Abkühlungsgeschwindigkeit“ (wobei hierfür meist ein komplizierterer Algorithmus verwendet wird) zu wählen – eine zu schnelle Abkühlung liefert schlechte Ergebnisse, eine zu langsame Abkühlung braucht zu viel Zeit.
Ebenfalls verwendet werden evolutionäre Algorithmen wie z. B. die genetischen Algorithmen oder auch Konzepte aus der Graphentheorie.
Eine wichtige Optimierung ist das Aufteilen der Beschriftungen in Teilmengen, die unabhängig voneinander gelöst werden können. Zwei Beschriftungen sind Konkurrenten, wenn es eine Platzierungsmöglichkeit gibt, bei der sie sich überlappen; dann gehören sie in die gleiche Teilmenge. Für Karten mit ungleichmäßiger Verteilung der Beschriftung kann das eine große Vereinfachung bedeuten – bei einer Weltkarte kann beispielsweise Amerika unabhängig von Europa beschriftet werden.
Implementierungen
PAL ist ein quelloffene, in C++ programmierte Bibliothek für die automatische Platzierung von Beschriftungen. Es existieren neben der generischen Bibliothek Portierungen für gvSIG, QGIS und MapWindow. PAL stammt von der Westuniversität der Schweiz.
PFLP ermöglicht die Platzierung von Punktlabels und wird an der Universität Wien entwickelt.
Literatur
- N. N. Podolskaya: Automatische Ausschließung von Überlappung von Beschriftungen für interaktive bildliche Darstellungen. In: Informationstechnologien, 9, 2007, S. 45–50, (ISSN 1684-6400). Russisch: Н.Н. Подольская: АЛГОРИТМЫ АВТОМАТИЧЕСКОГО ОТБРОСА ФОРМУЛЯРОВ ДЛЯ ИНТЕРАК ТИВНЫХ ГРАФИЧЕСКИХ ПРИЛОЖЕНИЙ. Информационные технологии, 9, 2007, с. 45–50.