Labeling interactive maps

Abstract

Navigationssysteme, beziehungsweise digitale Kartenapps, haben sich zu alltäglichen Begleitern entwickelt. Waren digitale Karten vor einem Jahrzehnt ein wertvolles Gut - Updates für Navigationssysteme wurden für viel Geld verkauft- sind sie heute durch die Verbreitung von Google Maps und Co. eine Selbstverständlichkeit. Neben der Verfügbarkeit und der Möglichkeit einfacher Updates, ermöglichen digitale Karten eine einfache, intuitive Interaktion. Das Zoomen, Verschieben und Drehen des Kartenausschnitts zum Erkunden von Details und der Ausrichtung in Blickrichtung des Nutzers, sind wohlbekannte Funktionen. Letzteres ist vor allem bei Navigationssystemen zentral. Dort wird die Kartenausrichtung generell in Fortbewegungsrichtung gewählt. Insbesondere für die Darstellung von Kartenbeschriftung, stellen diese Möglichkeiten eine Herausforderung dar. In der vorliegende Arbeit wird ein Konzept zur Gestaltung von Beschriftungen in interaktiven Karten, die stufenloses Zoomen, Verschieben und Rotieren des Kartenausschnitts ermöglichen, vorgestellt. Dabei wird insbesondere die Beschriftung von sogenannten ”Points of Interest” - also zu beschriftenden Punkten - thematisiert. Derartige Beschriftungen sind gewöhnlich horizontal ausgerichtet und überlappen sich somit tendenziell bei der Kartenrotation. Vor allem beim Zoomen der Karte sind verschiedene Konsistenzkriterien zu beachten - so soll beispielsweise eine Beschriftung während eines kontinuierlichen Zoomens nicht mehrfach hinzugefügt und wieder entfernt werden. Außerdem sollen Beschriftungen von wichtigeren Punkten länger sichtbar sein, als solche von weniger wichtigen Punkten. Bei der Beschriftung von Gebieten gilt, dass sich die Beschriftung im Gebiet befinden und die grobe Form des Gebiets adaptieren soll. Um letzteres zu erreichen, darf die Beschriftung entlang eines Kreisbogens gebogen sein. Rotation ist in diesem Szenario einfach - die Beschriftung muss lediglich in ihrer Ausrightung umgekehrt werden, sodass sie nicht auf dem Kopf steht. Beim Zoomen des Kartenausschnitts sollten Gebiete als Ganzes oder ihre Untergebiete beschriftet werden, abhängig von der Kartenskala der Gebietsbeschriftung. Für der Beschriftung von Punkten werden sogenannte ”Disk-Label” eingeführt. Bei diesen wird für jede Beschriftung ein kreisförmiger Bereich um den zu beschriftenden Punkt reserviert. Die Beschriftung des Punkts bleibt in beliebigen Ausrichtungen der Karte vollständig in diesem Bereich enthalten. Indem als Beschriftung in einer beliebigen Kartenskala eine überschneidungsfreie Untermenge der ”Disk-Label” gewählt wird, ist die lesbare Darstellung bei Rotation gewährleistet. Beim Herauszoomen aus dem Kartenausschnitt, werden die Beschriftungen bei konstanter Größe beibehalten. Entsprechend wachsen die zugehörigen Disks relativ zur Karte - entsprechend schrumpfen die Distanzen zwischen den Disks. Bei fortschreitendem Zoomen, kommt es zu Berührungen der Disks. Dabei muss eine der beteiligten Beschriftungen muss entfernt, um bei weiterem Zoomen die überschneidungsfreiheit zu erhalten. Wird der entsprechende Zoomprozess von ”unendlich 107weit hineingezoomt” zu ”unendlich weit herausgezoomt” betrachtet, ergibt sich eine sogenannte Eliminationssequenz der Beschriftungen. Diese kann für einen Datensatz im Voraus berechnet werden und ermöglicht dann eine einfache, effiziente Ableitung einer Kartenbeschriftung für ein gegebenes Darstellungszenario. Das Problem der Berechnung der Eliminationssequenzen kann verallgemeinert in einem d-dimensionalen Hyperraum betrachtet werden. Entsprechend der Disks in 2D, wachsen d-dimensionalen Hyperbälle. Eine Eiminationssequenz ist dabei nicht eindeutig - kollidieren Bälle der selben Wichtigkeit, ist die Entscheidung welcher der beiden Bälle eliminiert wird, essentiell für den weiteren Verlauf der Sequenz. Das Ziel ist die Berechnung einer optimalen Sequenz, in der die Summe aller Eliminationszeitpunkte maximiert wird. Es wird gezeit, dass die Berechnung einer solchen optimalen Sequenz N P − hart ist. Für ein vereinfachtes Szenario - in welchem die Sequenz eindeutig ist - wird ein effizientes Berechnungsverfahren vorgestellt und analysiert. Dieses Verfahren hängt stark von einer effizienten Methode zur Berechnung des nächsten Nachbarn sowie der Suche nach Punkten mit einer maximalen Distanz zu einem gegebenen Punkt ab. Je nach Szenario können diese Operationen effizienter oder weniger effizient gelöst werden. Für 2D und für höhere Dimmensionen werden zwei verschiedene theoretische Laufzeitschranken bewiesen. Für die praktische Beschriftung von digitalen Karten, werden Punkte auf einem virtuellen Globus betrachtet. Eine Berechnung der Sequenz für 13 Millionen Punkte ist auf einem herkömmlichen Computer in etwa 15 Minuten möglich. Das ursprüngliche, unvereinfachte Problem kann mittels eines Mixed-Integer Linearen Programms für wenige Punkte exakt gelöst werden. Allerdings nur mit erheblichem Rechen- und Speicheraufwand. Eine gute Approximation der optimalen Sequenz bieten Heuristiken. Mittels dieser kann der vorgestellte Algorithmus für das vereinfachte Szenario Lösungen für das unvereinfachte Problem berechnen. In der Güte liegen die Heuristiken bei 5% − 10% unter dem Optimum. Bei Berechnungszeiten von 15 − 20 Minuten auf einem herkömmlichen Computer. Eine Gebietsbeschriftung liegt vollständig innerhalb des Gebiets und ahmt die Form des Gebiets nach, indem sie entlang eines Kreisbogens plaziert ist. Für eine gute Beschriftung ist eine entsprechende Platzierung gesucht, welche die Größe der Beschriftung maximiert. Abhängig davon kann eine maximale und minimale Kartenskala berechnet werden, bei welcher die Beschriftung lesbar dargestellt werden kann. Entsprechend kann das Gebiet bei größeren Skalen in einer weiteren Verfeinerung dargestellt, oder bei kleineren Skalen durch eine Punkt-Beschriftung oder die Darstellung eines umfassenden Gebiets ersetzt werden. Für die Berechnung einer solchen guten Beschriftung wird in der vorliegenden Arbeit ein effizienter Algorithmus vorgestellt. Dieser basiert auf einem Algorithmus von 2001, von M. Barrault in [Mat01] publiziert. Durch verschiedene Optimierungen kann diese Berechnung auf Quasi-Echtzeit verbessert werden.