Geometric Reasoning & Spatial Optimization
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
![]() |
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 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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |
![]() |
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. |