Algorithms for Geovisualization

Zoomless Maps: Models and Algorithms for the Exploration of Dense Maps with a Fixed Scale

Die Exploration von Karten hoher Informationsdichte erfordert oft ein Zoomen zu einem sehr großen Maßstab, wodurch insbesondere auf kleinen Displays der Überblick verloren geht. In diesem Projekt entwickeln wir neue Modelle und Algorithmen für interaktive Karten, mit denen Nutzer auch auf kleineren Kartenmaßstäben arbeiten und die von ihnen gesuchte Information finden können. Damit soll die Lösung häufig vorkommender Aufgaben wie die Suche nach einem Hotel auch ohne Zoomen möglich werden.

Hulls of Polygons

In cartographic generalization, a map is transformed into a map of smaller scale. One way of generalizing map features is simplification. A simplified feature represents the same real world object but in a less complex way. (For example, when zooming to a smaller scale, geometries need to be simplified to keep a clear visualization.) In this work, we look into the simplification of polygonal objects, such as, country borders or building footprints. (The simplification of a polygonal shape represents the same object but in a less complex way.) A common goal for polygon simplification is the reduction of the polygon’s number of vertices. In this work, we further want the output polygon (1) to be crossing-free, (2) to lie in the exterior of the input polygon, (3) to be restricted to the vertices of the input polygon, (4) and to have only edges stemming from a predefined set of shortcuts. We call such a polygon a Shortcut Hull. We show how to compute Shortcut Hulls that optimize a balance between the perimeter and the covered area. We provide a dynamic programming approach to compute the optimal Shortcut Hull in polygonal time.

An Algorithmic Framework for Labeling Network Maps

Linienpläne sind schematische Karten für Transportnetze wie zum Beispiel für U-Bahn- oder Straßenbahnnetze. Im Gegensatz zu Straßenkarten liegt allerdings der Fokus auf der klaren Darstellung der Netzwerktopologie und weniger auf der akkurat geographischen Widergabe des Netzwerkes. Dementsprechend umfasst das Zeichnen von Liniennetzen zwei anspruchsvolle Schritte, nämlich das Zeichnen des Netzes selbst sowie das Platzieren von überlappungsfreien Stationsnamen.

Ausgehend von einem bereits gezeichneten Netzplan, wird in dieser Arbeit das automatische Platzieren von Stationsnamen betrachtet. Im Gegensatz zu anderen Beschriftungsproblemen dürfen Beschriftungen nicht ausgespart werden, sondern jede Station muss beschriftet werden. In der Arbeit wird ein automatischer Arbeitsablauf zur Beschriftung eines beliebigen Netzwerks präsentiert. Zwar können für diesen keine mathematischen Gütegarantien gegeben werden, allerdings belegt eine experimentelle Evaluation, dass die erzielten Ergebnisse nahezu die mathematisch optimale Lösung erreichen.

Multirow Boundary-Labeling Algorithms for Panorama Images

In diesem Artikel stellen wir effiziente Algorithmen zur Beschriftung von Panoramabildern vor. In einem Panoramabild sind wichtige Landmarken zu sehen, zum Beispiel Hochhäuser oder Berggipfel. Wir gehen davon aus, dass die Positionen dieser Landmarken im Bild und ihre Namen bekannt sind. Das Problem besteht schließlich darin, Textfelder über dem Panoramabild zu platzieren und diese über Linien mit den zugehörigen Positionen im Bild zu verbinden. Dabei dürfen sich weder die Textfelder gegenseitig überlappen, noch darf ein Textfeld die Linie eines anderen Textfelds verdecken. Grundsätzlich erlauben wir es, die Textfelder in mehrere Zeilen zu positionieren. Unser erster Algorithmus zielt jedoch auf eine Lösung ab, die mit möglichst wenigen Zeilen auskommt. Unsere weiteren Algorithmen gehen von einer begrenzten Anzahl von Zeilen aus und platzieren in diesen Zeilen eine optimal ausgewählte Teilmenge aller Textfelder – einige Punkte erhalten in diesem Fall keine Beschriftung.

Drawing Road Networks with Focus Regions

Bei der Betrachtung von Karten auf einem kleinen Display sind Nutzer oft gezwungen, einen sehr großen Maßstab zu wählen, um an die benötigte Detailinformation zu kommen. Dabei geht der größere Kontext verloren. Wir stellen in diesem Artikel ein Verfahren vor, das nur ausgewählte Teile einer Karte in einem größeren Maßstab darstellt und diese mit der kleinmaßstäbigen Darstellung einer Kontextregion kombiniert. Dadurch gelingt es, sowohl Detailinformation als auch Kontextinformation vorzuhalten. Anders als existierende Fish-Eye-Projektionen, welche diese Aufgabe nur mit großen Verzerrungen der Karte bewältigen, führt unser Ansatz zu sehr geringen Verzerrungen. Dies wird durch einen Optimierungsverfahren sichergestellt.

Temporal Map Labeling  

Durch die zunehmende Verbreitung von interaktiven Kartenanwendungen im Internet und auf mobilen Endgeräten eröffnen sich neue Anforderungen für die Beschriftung von Karten. Durch Grundoperationen wie Rotieren, Zoomen und Verschieben der Karte muss die Platzierung der Beschriftungen an die Änderungen der Karte angepasst werden. In diesem dynamischen Szenario reicht es nicht aus, die Anzahl der Beschriftungen zu maximieren, sondern es müssen weitere Anforderungen, sogenannte Konsistenzkriterien, erfüllt werden. So dürfen Beschriftungen nicht springen oder durch häufiges sichtbar bzw. unsichtbar werden "flackern''. In der Arbeit wird ein allgemeines Modell für die Beschriftung von dynamischen Karten eingeführt, das die drei genannten Operationen miteinander vereint. Hierfür wird angenommen, dass der Anwender nur einen Ausschnitt der Karte sieht - als würde er die Karte mithilfe einer Kamera betrachten. Da bereits der statische Fall für das Beschriftungsproblem aus berechnungstheoretischer Sicht sehr komplex ist, ist es nicht verwunderlich, dass in dieser Arbeit auch für den betrachteten dynamischen Fall eine hohe Berechnungskomplexität gezeigt werden kann.

Schränkt man allerdings die Anzahl gleichzeitig angezeigter Beschriftungen ein, so kann, wie in der Arbeit gezeigt wird, das Problem mithilfe sogenannter dynamischer Programmierung effizient gelöst werden. Diese Einschränkung ist insbesondere für die Anwendung auf Navigationsgeräten interessant, die zumeist nur einen kleinen Bildschirm besitzen und den Anwender nicht mit zu vielen angezeigten Zusatzinformationen überfordern sollen.

Gemsa, A, Niedermann, B, and Nöllenburg M (2013).
Trajecotry-Based Dynamic Map Labeling
Algorithms and Computation (ISAAC'13), 8283:413–423.

Barth, L, Gemsa, A, Niedermann, B, Nöllenburg M, and Strash, D (2016).
Temporal Map Labeling: A New Unified Framework with Experiments
Advances in Geographic Information Systems (ACM-GIS'16). 

Label Placement in Road Maps 

Während die Punktbeschriftung im Bereich der Algorithmik ausführlich untersucht wurde, gibt es für die automatische Beschriftung von Linienmerkmalen kaum Vorarbeiten. Bisherige Arbeiten schränken entweder die Art des betrachteten Straßennetzwerks stark ein (z.B. gitterförmige Netze) oder präsentieren ausschließlich einfache Heuristiken. Zudem wird in vielen Beschriftungsproblemen die Anzahl der Beschriftungen maximiert. Dagegen liegt der Fokus dieser Arbeit darauf, so viele Straßenabschnitte wie möglich in einem beliebigen Straßennetzwerk zu benennen. Durch diese angepasste Zielfunktion wird erreicht, dass nicht unnötig viele Beschriftungen die Karte verdecken, während der Informationsgehalt der Karte maximiert wird. In dieser Arbeit wird insbesondere eine empirisch gut funktionierende und schnelle Heuristik vorgestellt. Auf Grundlage von Echtweltdaten wird gezeigt, dass der präsentierte Algorithmus in angemessener Zeit Ergebnisse liefert, die nahe an die entsprechende mathematisch optimale Lösung herankommen.

Gemsa, A, Niedermann, B, and Nöllenburg M (2015).
Label Placement in Road Maps
Algorithms and Complexity (CIAC'15), 9079:221–234.

Niedermann, B, and Nöllenburg M (2016).
An Algorithmic Framework for Labeling Road Maps
Geographic Information Science (GISciene'16), 9927:308–322.