Consistent pruning and simplification of administrative subdivisions in OpenStreetMap

Abstract

Appealing and efficient map representations rely on simplifying their map elements in order to reduce the amount of data and rendered objects. However, simplifications inside the well-known OpenStreetMap database are not trivial due to nesting and the associated complex dependencies among elements. A good and consistent simplification of elements in a big way is, therefore, not feasible when working on this data. This thesis aims to develop a consistent simplification strategy for administrative boundaries inside the OpenStreetMap database. In order to achieve this goal, the relevant map data inside the database gets filtered and transformed into an independent graph representation. Based on this representation, we develop different approaches to simplify, store and unpack the administrative boundaries based on their administrative levels and structure. Therefore, we introduce multiple consistent simplification approaches based on approximation and pruning, a geographical data structure for efficiently storing and accessing geographical data, and different approaches for unpacking simplified data. Furthermore, we implement a progressive web application that uses the previously defined algorithms and an evaluation proxy for analysing the interaction between components. Finally, all components are benchmarked with static and dynamic analysis regarding the different approaches.

Eine ansprechende und effiziente Kartendarstellung beruht auf der Vereinfachung der Kartenele- mente, um die Menge der Daten und zu zeichnenden Objekte zu reduzieren. Allerdings sind Vereinfachungen innerhalb der bekannten OpenStreetMap-Datenbank aufgrund der Verschachtelung und der damit verbundenen komplexen Abhängigkeiten zwischen den Datenelementen nicht trivial. Eine gute und konsistente Vereinfachung von geographischen Elementen im großen Stil ist daher nicht möglich, wenn man auf diesen Daten arbeitet. Ziel dieser Arbeit ist die Entwicklung einer konsistenten Strategie zur Vereinfachung von Ver- waltungsunterteilungen innerhalb der OpenStreetMap-Datenbank. Um dieses Ziel zu erreichen, werden die relevanten Datenelemente innerhalb der Datenbank gefiltert und in eine unabhängige Graphdarstellung transformiert. Basierend auf dieser Darstellung entwickeln wir verschiedene Ansätze, um die administrativen Grenzen auf Basis ihrer Administrationsebenen und Strukturen zu vereinfachen, zu speichern und zu entpacken. Für diesen Zweck entwickeln wir mehrere Ansätze zur konsistenten Vereinfachung auf Basis von Auslassung und Auslöschung, eine geografische Daten- struktur zur effizienten Speicherung und zum Zugriff auf geografische Daten sowie verschiedene Ansätze zum Entpacken vereinfachter Daten. Des weiteren implementieren wir eine progressive Webanwendung, welche einen Einsatzzweck für die zuvor definierten Algorithmen darstellt und einen Evaluations-Proxy zur Auswertung von Interaktionen zwischen Komponenten. Abschließend werden alle entwickelten Komponenten mittels statischer und dynamischer Analyse im Hinblick auf die verschiedenen entwickelten Ansätze analysiert und evaluiert.