Was geschieht hier?

Auf der Website von openstreetmap.org können die vorliegenden Daten zu ausgewählten Regionen heruntergeladen werden. Damit die Daten aber für den Routenplaner verwendet werden können, muss aus der Datenmenge ein Graph erstellt werden, welcher das Straßennetz repräsentiert. Dieser Prozess findet während des Parsings statt.

Die Ausgangssituation

Ein Großteil der Informationen, welche in der heruntergeladenen Datei (Format: *.osm), sind für das Praktikum irrelevant. Dazu zählen z.B. Informationen, wo sich der nächste Mülleimer befindet, Wanderwege und dergleichen. Die für uns entscheidenden Daten sind die Straßen und Kreuzungen in dem von uns untersuchten Gebiet: dem Neuenheimer Feld. Die Datei enthält eingangs eine Liste mit allen Knoten des Kartenstücks ohne nähere Spezifizierung über die Bedeutung des Knotens, lediglich die Weltkoordinaten werden hier als wichtige Information angegeben. Der Knoten kann demnach eine Kreuzung, ein Mülleimer, ein Kreisverkehr, ein Hausecke, usw. repräsentieren. Nach der Auflistung der Knoten folgt eine Liste mit Streckenzügen. Jeder Streckenzug enthält 1 bis n verschiedene Knoten und erhält seine Bedeutung durch ein Tag am Ende des Linienzugs. Durch diesen Tag wird entschieden, ob der Linienzug als Straße, Wanderweg, Gebäudeumriss oder beispielsweise als Flussverlauf interpretiert wird.

Dies ist ein Beispiel für einen Knoten von vielen Knoten, welche eingangs in der Datei definiert werden. Relevant sind für uns nur die ID, welche zu Beginn gesetzt wird und die Koordinaten in Längen- und Breitengrade. Die restlichen Informationen verwerfen wir beim Einlesen der Daten.


node id="269906104" lat="49.4110246" lon="8.6665699" user="aikon" visible="true" timestamp="2008-10-11T22:18:12+01:00"

Die Daten des Streckenzugs sehen beispielsweise wie folgt aus: Durch den Tag highway wird der Streckenzug als Weg klassifiziert. Der Zusatz footway bedeutet, dass dies ein Fußgängerweg ist. Die IDs, welche vor dem Tag aufgelistet werden, sind die IDs der Knoten, welche hier verbunden werden Zwecks Übersichtlichkeit, werden hier nur zwei der n aufgelisteten Knoten angezeigt.


way id="24968600" visible="true" timestamp="2008-07-27T20:39:14+01:00" user="aikon"
    nd ref="271326293"
    nd ref="271326294"
    ...
    tag k="bicycle" v="yes"
    tag k="highway" v="footway"
/way

Das Parsing

In einem ersten Schritt werden nun alle Knoten aus der Datei eingelesen. Anschließend werden alle Streckenzüge, welche als Verkehrsstraßen markiert sind, eingelesen. Nachdem beides geschehen ist, wird überprüft, welche der Knoten in den Streckenzügen vorkommen und welche nicht. Die nichtvorkommenden Knoten werden daraufhin verworfen, um Speicherplatz zu sparen. Das Problem das an dieser Stelle auftaucht ist, dass standardmäßig ein Graph eine Menge von Knoten, vereint mit einer Menge von Kanten ist. Dabei bildet eine Kante genau ein Paar aus genau 2 Knoten. Die in der OSM Datei gegebenen Daten verhalten sich allerdings genau umgekehrt: Hier wird eine Menge von Kanten mit einer Menge von Knoten vereint, was in mehr als 2 Knoten pro Kante resultieren kann und auch vorliegt. Daher ist nach dem Einlesen der Knoten und Streckenzüge ein weiterer Schritt beim Parsen notwendig, in dem je zwei benachbarte Knoten eines Streckenzuges mit einer Kante verbunden werden.

Für diesem Schritt bleibt die Menge der Knoten identisch, jedoch wird nun eine neue Menge von Kanten erzeugt. Das Verfahren funktioniert wie folgt: es wird durch die Liste aller Streckenzüge iteriert und dabei für jeden Punkt jedes Streckenzuges seine direkten Nachbarn auf diesem Streckenzug bestimmt und für jeden Nachbarn wird dann eine neue Kante zwischen dem Nachbarn und dem derzeitigen Knoten erzeugt. Zum Schluss wird die Menge der Streckenzüge gelöscht, um Speicherplatz freizugeben.

Bei dem eben genannten Schritt kann es jedoch zu einer Schwierigkeit kommen, die abgefangen werden muss: Es sind nicht unbedingt die beiden Knoten mit dem aktuellen Knoten benachbart, die den geringsten Abstand zu ihm haben. Da die Punkte nicht äquidistant verteilt sind, muss überprüft werden, ob die beiden Punkte, die am nächsten liegen, auch tatsächlich Nachbarn sind. Das nachfolgende Bild veranschaulicht dies.

In dem Beispiel der Abbildung möchten wir die Nachbarn von S bestimmen. Der Knoten mit dem geringsten euklidischen Abstand zu S ist der erste direkte Nachbar v. Nun wird der Knoten mit dem nächstgeringsten Abstand gewählt. Ist der Abstand des nächsten Knotens zu v kleiner als zu S, dann wissen wir, dass es kein direkter Nachbar von S sein kann. Erst wenn der Abstand des Knotens zu S kleiner ist, als zu v, ist der Knoten der zweite direkte Nachbar von S.