Generalisierung und räumliche Optimierung / blauer Hintergrund
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.
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.
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.
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.
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.
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.
Kontakt
Prof. Dr.-Ing. Jan-Henrik Haunert
Leitung der Arbeitsgruppe
2.008
Meckenheimer Allee 172
53115 Bonn