Generalisierung und räumliche Optimierung

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.

Wenn der Detailgrad von Geodaten für eine Analyse zu hoch oder zu niedrig ist, muss er mit geeigneten Berechnungsmethoden angepasst werden. Detaillierte Daten zu einzelnen Gebäuden eignen sich beispielsweise wenig für die Raumplanung. Aus Gebäudedaten lassen sich jedoch automatisch Siedlungspolygone ableiten, die für die Raumplanung benötigt werden [1]. Zur Lösung dieses Problems und ähnlicher Aufgaben werden Methoden der Computational Geometry und der kombinatorischen Optimierung benötigt. Wir entwickeln Algorithmen zur Gruppierung (Clustering) von geometrischen Objekten und zur Aggregation der Objekte innerhalb jeder Gruppe zu einem einzelnen Objekt. In ähnlicher Weise entwickeln wir Algorithmen zur Vereinfachung, d. h. zur Reduzierung des Detailgrads einzelner geometrischer Objekte [2,3].

[1] P. Rottmann, A. Driemel, H. Haverkort, H. Röglin, and J.-H. Haunert. Bicriteria aggregation of polygons via graph cuts. In Krzysztof Janowicz, and Judith A. Verstegen, editors, volume 208 of Leibniz International Proceedings in Informatics (LIPIcs). 11th International Conference on Geographic Information Science (GIScience 2021) - Part II, pages 6:1-6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

[2] A. Bonerath, J.-H. Haunert, J. S. B. Mitchell, and B. Niedermann. Shortcut hulls: vertex-restricted outer simplifications of polygons. Computational Geometry Theory and Applications, 112:101983, 2023.

[3] J.-H. Haunert and A. Wolff. Optimal and topologically safe simplification of building footprints. In Proc. 18th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS '10), pages 192-201. 2010.

Einen besonderen Fokus legen wir auf die Gruppierung und Aggregation von Polygonen, die ein Gebiet lückenlos und ohne Überschneidungen abdecken. Die Eingabepolygone können Verwaltungseinheiten darstellen, die zu größeren Gebietseinheiten zusammengefasst werden sollen. Diese Aufgabe wird in der Literatur als Districting oder Regionalisierung bezeichnet. Dabei sind oft mehrere Kriterien hinsichtlich der Größe der Ausgabegebiete, ihrer geometrischen Kompaktheit, ihrer Konnektivität sowie ihrer Homogenität bezüglich quantitativer Merkmale zu berücksichtigen [4].

[4] J. Oehrlein and J.-H. Haunert. A cutting-plane method for contiguity-constrained spatial aggregation. Journal of Spatial Information Science, 15(1):89-120, 2017.

Wir betrachten auch Cluster-, Aggregations- und Vereinfachungsaufgaben speziell im Zusammenhang mit der Generalisierung [5,6], die in der Kartografie die Reduzierung des Detailgrads eines Modells der realen Welt bedeutet. Die Generalisierung ist erforderlich, um aus einem detaillierten Modell Karten mit unterschiedlichen Maßstäben zu erstellen. Clustering und Aggregation werden auch im Kontext des Datenschutzes benötigt. So können beispielsweise Daten auf Haushaltsebene in größere Einheiten geclustert werden, um die Daten zu anonymisieren [7].

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

[6] S. Gedicke, J. Oehrlein, and J.-H. Haunert. Aggregating land-use polygons considering line features as separating map elements. Cartography and Geographic Information Science, 48(2):124-139, 2021.

[7] J.-H. Haunert, D. Schmidt, and M. Schmidt. Anonymization via clustering of locations in road networks (short paper). In Proc. 11th International Conference on Geographic Information Science (GIScience '21). 2021.

Wenn der Detaillierungsgrad der thematischen oder geometrischen Informationen in einem Datensatz zu gering ist, besteht ein gängiger Ansatz darin, den Datensatz aus anderen Datenquellen anzureichern. Zu diesem Zweck entwickeln wir Methoden des Datenabgleichs und der Datenintegration [8].

[8] M. Sester, J. Jokar~Arsanjani, R. Klammer, D. Burghardt, and J.-H. Haunert. Integrating and generalising volunteered geographic information. In D. Burghardt, C. Duchene, and W. Mackaness, editors, Lecture Notes in Geoinformation and Cartography. Abstracting Geographic Information in a Data Rich World. Springer-Verlag, Berlin, Germany, 2014.

02_generalization_05_Triangulierte-Netze_02quadrat_600x600.jpg

Mit ähnlichen methodischen Ansätzen aus der algorithmischen Geometrie und der kombinatorischen Optimierung entwickeln wir in Zusammenarbeit mit Partnern aus der physikalischen Geodäsie und der Informatik Algorithmen zur Berechnung kompakter Repräsentationen von Oberflächen. Unser Ziel ist es, optimale Darstellungen der Meeresoberfläche in Form von triangulierten unregelmäßigen Netzen [9,10] zu berechnen. Diese wollen wir nutzen, um bessere Rekonstruktionen der historischen Meeresoberfläche zu ermöglichen und die Forschung zu den Folgen des Klimawandels zu unterstützen. Außerdem entwickeln wir kombinatorische Optimierungsmethoden für die Planung geodätischer Beobachtungen [11].