Beschriftung von dynamischen Karten

Ein klassisches Problem in der Kartographie ist das Positionieren von Beschriftungen auf einer Landkarte. Dabei ist die grundsätzliche Problematik nicht auf Landkarten beschränkt, sondern findet sich in vielen anderen Bereichen wieder, bei denen Bilder beschriftet werden. Durch die zunehmende Verbreitung von interaktiven Kartenanwendungen im Internet und auf mobilen Endgeräten, die den genauen Aufenthaltsort des Benutzers kennen und auf einer Karte anzeigen können, eröffnen sich neue Anforderungen für die Beschriftung von solchen dynamischen Karten. Viele dynamische Karten zeichnen sich dadurch aus, dass sie drei Grundoperationen unterstützen: Das kontinuierliche Bewegen des Betrachtungsausschnitts, das stufenlose Ein- und Auszoomen sowie eine kontinuierliche Rotation der Karte.

Üblicherweise wird in Beschriftungsalgorithmen der Text (auch Label genannt) als Rechteck modelliert. Ziel für das Beschriften statischer Karten ist es, möglichst viele Label gleichzeitig darzustellen unter der Bedingung, dass sich keine Label überlappen. Übertragt man dieses Optimierungsziel auf dynamische Karten so entspricht dies der Maximierung der Anzahl der sichtbaren Label über alle Ansichten unter der Bedingung, dass sich die Label zu keinem Zeitpunkt überlappen. Allerdings lassen sich für dynamische Karten noch weitere Anforderungen, sogenannte Konsistenzkriterien, finden. So darf ein Label während einer Grundoperation nicht plötzlich seine Größe bzw. seine Position ändern, oder, um „Flackern“ von Labeln zu vermeiden, mehrmals sichtbar bzw. unsichtbar werden.

Statische Karten haben in der Regel eine natürliche Orientierung (oft sind sie nach Norden ausgerichtet). Anders bei Navigationsgeräten in Autos. Hier wird üblicherweise der gezeigte Kartenausschnitt immer so ausgerichtet, dass das Auto nach „oben“ fährt. Dies führt unweigerlich dazu, dass die Karte während der Fahrt rotiert wird. Wir beschäftigen uns deshalb mit der Fragestellung wie möglichst viele Label während einer Rotation sichtbar sein können ohne eines der Kosistenzkrierien zu verletzten.

Ursprüngliche Karte

Rotierte Karte (Labels teilweise ausgeblendet)

Bei dynamischen Karten, die das kontinuierliche Ein- und Auszoomen unterstützen ist es wünschenswert über den vollständigen Zoomvorgang eine maximale Anzahl an Labeln anzuzeigen. Da es beim Auszoomen unweigerlich zu Konflikten, d.h. Überlappungen, von Labeln kommt, muss bei jedem Konflikt entschieden werden, welches Label ausgeblendet wird und welches Label sichtbar bleibt. Die richtige Wahl beeinflusst maßgeblich die Qualität der Lösung.

Ungünstige Wahl. Die Label von Paris und Karlsruhe haben sehr früh einen Konflikt.

Geschickte Wahl. Der letzte Konflikt wird lange herausgezögert.

Ein weiterer Freiheitsgrad betrifft die relative Position des Labels zu dem zu beschriftenden Punkts. Ist die Position ungünstig gewählt, so kann es sehr schnell zu Konflikten führen. Wählt man eine geschicktere Position so kann man einen Konflikt sehr lange herauszögern oder sogar vermeiden.

Wir untersuchen wie man beide Probleme lösen kann unter der Bedingung, dass keine Konsistenzkriterien verletzt werden.

Ungünstige Position der Label. Es kommt sehr früh zu einem Konflikt.

Günstige Position der Label. Beim Zoomvorgang wird ein Konflikt vermieden.

Die trajektorienbasierte Kartenbeschriftung baut auf dem kontinuierlichen Rotieren von Karten auf und ist ein weiterer Schritt in Richtung einer adäquaten Darstellung von Karten auf Navigationsgeräten. Es wird angenommen, dass ausschließlich ein rechtecksförmiger Ausschnitt der vorliegenden Karte angezeigt wird und sich dieser so entlang einer Trajektorie auf der Karte bewegt, dass er sich gemäß der aktuellen Position auf der Trajektorie ausrichtet. Um eine gute Lesbarkeit zu gewährleisten, werden die Labels horizontal bezüglich des angezeigten Ausschnitts dargestellt. Fährt das Auto also eine Kurve, so rotiert nicht nur die Karte, sondern auch die Labels.

Eingenordete Karte. Die angenommene Trajektorie ist blau dargestellt und der dem Anwender gerade angezeigte Auschnitt ist als schwarzes Rechteck eingezeichnet. Es werden alle möglichen Labels dargestellt.

Ausschnitt der Karte, den der Anwender aktuell sieht. Die Labels sind horizontal bzgl. zum Ausschnitt ausgerichtet. Die Labels wurden so gewählt, dass keine Überlappungen auftreten.

Ist die Trajektorie nicht von Anfang an bekannt, so muss die Entscheidung, welche Labels angezeigt werden, online geschehen. Jedoch gerade im Anwendungsfall von Navigationsgeräten sind häufig Start und Ziel bereits im Voraus bekannt, sodass die gesamte Trajektorie für eine optimale und konsistente Wahl der Labels herangezogen werden kann. Unter dieser Annahme entwickeln wir Algorithmen, die über die gesamte Trajektorie gesehen dem Anwender möglichst viel zusätzliche Information präsentieren, ohne dass die Einzelansichten überfrachtet wirken.

1. Ken Been, Martin Nöllenburg, Sheung-Hung Poon, and Alexander Wolff.
   Optimizing Active Ranges for Consistent Dynamic Map Labeling.
   Computational Geometry: Theory and Applications, 43(3):312-328, 2010.
   Special issue of SoCG 2008
   [ html ][ pdf ]

1. Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
   Consistent Labeling of Rotating Maps.
   In: Algorithms and Data Structures, 12th International Symposium (WADS'11) volume 6844 of Lecture Notes in Computer Science, pages 451-462. Springer, 2011.
   [ html ][ pdf ]
2. Andreas Gemsa, Martin Nöllenburg, and Ignaz Rutter.
   Sliding Labels for Dynamic Point Labeling.
   In: Proceedings of the 23rd Canadian Conference on Computational Geometry (CCCG '11), pages 205-210. University of Toronto Press, 2011.
   [ pdf ]
3. Martin Nöllenburg, Valentin Polishchuk, and Mikko Sysikaski.
   Dynamic One-Sided Boundary Labeling.
   In: Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pages 310-319. ACM Press, November 2010.
   [ html ][ pdf ]