Sie sind hier: Startseite Forschung Algorithms for Geovisualization

Algorithms for Geovisualization

Forschung_Visualisierung_2 

Digitale Karten sowie Visualisierungen ortsbezogener Daten sind in unserem Alltag allgegenwärtig und werden mit der weltweit steigenden Anzahl an ortsbezogenen Diensten und Smartphones zunehmend wichtiger. Angefangen vom Navigationssystem, über die kartenbasierte Suchmaschine bis hin zu digitalen sozialen Netzwerken spielen sie eine entscheidende Rolle im Umgang und der Arbeit mit räumlichen Informationen.

In der Arbeitsgruppe werden effiziente Algorithmen zur automatischen Erstellung von geobezogenen Visualisierungen im Allgemeinen sowie von interaktiven Karten im Speziellen entwickelt. Die aktuelle Forschung der Arbeitsgruppe umfasst insbesondere die automatische Platzierung von Beschriftungen in Karten sowie die Schematisierung und Generalisierung von geographischen Netzen.

 

Ansprechpartner

Dr. Benjamin Niedermann

Prof. Dr.-Ing. Jan-Henrik Haunert

 

Web-Applikationen

 

Aktuelle Projekte

 

 zoomless-maps.png

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.

Haunert, J (2018).
gepris.dfg.de/gepris/projekt/408056693

 

Ausgewählte Arbeiten

 

 metro map

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.

Niedermann, B and Haunert, J (2018).
An Algorithmic Framework for Labeling Network Maps
Algorithmica.

panorama

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.

Gemsa, A, Haunert, J, and Nöllenburg, M (2015).
Multirow Boundary-Labeling Algorithms for Panorama Images
ACM Transations on Spatial Algorithms and Systems, 1(1):1–30.

focusmap

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.

Haunert, J and Sering, L (2011).
Drawing Road Networks with Focus Regions
IEEE Transactions on Visualization and Computer Graphics (Proc. Information Visualization 2011), 17(12):2555–2562.

 Dynamic Map Labeling Without Border

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). 


 Road Labels

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.

 

 

 

Artikelaktionen