Sie sind hier: Startseite Forschung Geometric Reasoning & Spatial Optimization

Geometric Reasoning & Spatial Optimization

AlgorithmenGeoinformation2_1160x290.jpg
 

Analyse- und Visualisierungsaufgaben in Geoinformationssystemen (GIS) und Navigationssystemen erfordern effiziente Algorithmen zur Prozessierung großer Mengen geometrischer Daten. Oft sollen Datensätze aus verschiedenen Quellen miteinander verknüpft, der Detailgrad eines Datensatzes an den Maßstab einer Analyse angepasst oder Muster in den Daten erkannt werden. Für diese Aufgaben entwickeln wir Verfahren der kombinatorischen Optimierung und der algorithmischen Geometrie. Dabei legen wir sowohl Wert auf die Bildung mathematischer Modelle als auch auf den Entwurf, die Analyse, die Implementierung und die Evaluierung neuer, praxistauglicher Algorithmen.

 

Ausgewählte Arbeiten

 

matching

Extracting spatial patterns in bicycle routes from crowdsourced data

In diesem Artikel analysieren wir anhand von GPS-Trajektorien, welche Routen im Wegenetz von Fahrradfahrern bevorzugt werden. Die GPS-Trajektorien wurden von Fahrradfahrern aufgezeichnet und der Allgemeinheit über ein Online-Portal freiwillig zur Verfügung gestellt. Anhand der GPS-Trajektorien muss zunächst ermittelt werden, welche Routen die Fahrradfahrer im Straßennetz zurückgelegt haben. Für diese Aufgabe präsentieren wir einen Map-Matching-Algorithmus, der auch für ungenaue und fehlerhafte GPS-Daten und Straßendaten plausible Ergebnisse liefert.

Sultan, J, Ben-Haim, G, and Haunert, J (2017).
Extracting spatial patterns in bicycle routes from crowdsourced data
Transactions in GIS:1-20.

 


partitioning 

Partitioning Polygons via Graph Augmentation

Flächenhafte Objekte wie Länder oder Seen werden in Geodaten oft als Polygone repräsentiert. Oft nehmen einzelne Polygone sehr große Ausmaße und komplizierte Formen an und bestehen aus Tausenden von Koordinaten. Für die Auswertung der Daten kann es daher vorteilhaft sein, die Polygone in kleinere Einheiten zu zerschneiden und somit handhabbarer zu machen. In diesem Papier stellen wir sehr effiziente Algorithmen vor, um Polygone in möglichst sinnvolle Einheiten zu partitionieren. Ein Teilpolygon wird dabei als sinnvolle Einheit betrachtet, wenn es eine kompakte Form hat und sich mit einer kurzen Trennlinie vom Rest des Polygons abtrennen lässt. Die Iberische Halbinsel ist zum Beispiel ein sinnvolles Teil Europas.

Haunert, J and Meulemans, W (2016).
Partitioning Polygons via Graph Augmentation
In: Proc. 9th International Conference on Geographic Information Science (GIScience 2016), vol. 9927, pp. 18–33, Springer-Verlag. Lecture Notes in Computer Science.

 


symmetry

A Symmetry Detector for Map Generalization and Urban-Space Analysis

Gebäude und Gruppen von Gebäuden werden von Architekten und Stadtplanern oft symmetrisch angelegt. In diesem Artikel werden effiziente Algorithmen vorgestellt, um Spiegelsymmetrien und sich wiederholende Elemente in Gebäudepolygonen zu identifizieren. Dadurch können zum Beispiel Gebäudeensembles und Gebäude mit einer wichtigen repräsentativen Funktion identifiziert werden. Die einmal erkannten Symmetrieeigenschaften von Polygonen können auch bei der Generalisierung genutzt werden, da sie charakteristische Eigenschaften darstellen, die im Zuge der Generalisierung erhalten bleiben sollen.

Haunert, J (2012).
A Symmetry Detector for Map Generalization and Urban-Space Analysis
ISPRS Journal of Photogrammetry and Remote Sensing, 74:66–77.

 


aggregation

Area aggregation in map generalisation by mixed-integer programming

Geodaten liegen oft in Form eines Mosaiks aus Polygonen vor, welche ein Untersuchungsgebiet lückenlos und ohne Überlappungen abdecken. Oft ist für jedes Polygon ein Landbedeckungstyp (z.B. Wald, Wasser oder Siedlung) gegeben. In diesem Artikel präsentieren wir Algorithmen, um die Polygone eines Mosaiks so zu größeren Polygonen zusammenzufassen, dass vorgegebene Mindestkriterien an den Flächeninhalt eingehalten werden und die Landbedeckungsinformation so gut wie möglich erhalten bleibt. Das Ergebnis ist ein Datensatz, in dem größere Landschaftsstrukturen erkennbar werden.

Haunert, J and Wolff, A (2010).
Area aggregation in map generalisation by mixed-integer programming
International Journal of Geographical Information Science, 24(12):1871–1897.

 


building

Optimal and Topologically Safe Simplification of Building Footprints

Gebäude werden in Geodaten in der Regel durch Umringpolygone repräsentiert. Da diese Polygone oft sehr detailreich sind, ist für eine effiziente Handhabung großer Datensätze oder eine übersichtliche Visualisierung eine Generalisierung erforderlich. Diese umfasst insbesondere eine geometrische Vereinfachung. Wir stellen einen neuen Ansatz zur Gebäudevereinfachung vor, der auf kombinatorischer Optimierung beruht. Dabei wird das vereinfachte Polygon durch die Auswahl einer Teilmenge der Kanten des ursprünglichen Polygons definiert. Das neue Polygon soll aus möglichst wenigen Kanten bestehen, wobei das ursprüngliche Polygon noch hinreichend genau approximiert sein muss. Zudem werden Überlappungen zwischen Polygonen oder sich selbst schneidende Polygone in der Ausgabe vermieden.

Haunert, J and Wolff, A (2010).
Optimal and Topologically Safe Simplification of Building Footprints
In: Proceedings of the 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM-GIS'10), pp. 192–201.

 


skeleton

Area collapse and road centerlines based on straight skeletons

In Navigationssystemen und topographischen Datenbanken werden Straßen durch Linien repräsentiert. Im Liegenschaftskataster und in Luftbildern sind sie jedoch in flächenhafter Form erfasst. In diesem Artikel stellen wir Algorithmen vor, um Straßenpolygone in Straßenmittellinien zu überführen. Dabei werden sogenannte Skelette für die gegeben Polygone berechnet. Ein besonderer Fokus liegt auf der Berechnung von Straßenmittellinien in Kreuzungsbereichen, welche durch existierende Skelettalgorithmen nicht realistisch wiedergegeben werden.

Haunert, J and Sester, M (2008).
Area collapse and road centerlines based on straight skeletons
GeoInformatica, 12(2):169–191.

 

Artikelaktionen