Effiziente Verarbeitung von Anfragen nach Polygon-Enthaltensein im Kontext von OSM-Daten

Abstract

Diese Arbeit beschäftigt sich mit den Flächen-Informationen von OpenStreetMap-Daten und die effiziente Ermittlung der zu einer konkreten Koordinate vorhandenen relevanten OpenStreetMap-Flächendaten. Die Flächen liegen in OpenStreetMap als sogenannte ways und relations vor. Ein Weg ist dann eine Fläche, wenn der Weg ein Polygon bildet und mit bestimmten tags (Schlüssel-Wert-Paare) markiert ist. Eine Relation ist dann eine Fläche, wenn die Relation mit bestimmten Tags markiert ist und mindestens ein Polygon enthält, also einen geschlossen Weg oder eine Kombination von Wegen enthält, die zusammen ein Polygon bilden. Die Informationen zu einer Fläche liegen als Tags des entsprechenden Weges oder der entsprechenden Relation vor. In dieser Arbeit wurde deshalb auch ein C++-Programm entwickelt, welches bestimmte Polygone und zugehörige Flächen-Informationen aus den OpenStreetMap-Daten extrahiert. Unterstützt wird das C++-Programm durch ein Python-Skript, welches die OpenStreetMap-Daten in ein leichter parsbares Textformat exportiert. Desweiteren wurde in dieser Arbeit ein Programm entwickelt, welches die Polygone als Eingabedaten nimmt und daraus eine Datenstruktur aufbaut, die bei einer Anfrage mit einer Koordinate effizient die Polygone ermitteln kann, die diese Koordinate enthalten. Das Ergebnis auf eine Anfrage besteht aus den Polygonen in Koordinatenform und aus den zugehörigen Flächen-Informationen. Als Datenstruktur wurde ein Quadtree verwendet, der zur Reduzierung von Point-In-Polygon-Berechnungen eingesetzt wird. Das Quadtree-Programm wurde anschließend in die Anwendung MapViewer der Abteilung Algorithmik am Insitut für Formale Methoden der Informatik der Universität Stuttgart eingebaut. Dadurch lassen sich die Anfragen über eine Graphische Oberfläche stellen, wobei die Polygone aus dem Ergebnis direkt grafisch auf einer OpenStreetMap-Karte angezeigt werden.