Einfache Erreichbarkeitsanalyse mit OSM-Daten

Im deutschen OpenStreetMap-Forum wurde die Frage nach einer Erreichbarkeitsanlayse mit OSM-Daten gestellt:

[…] zeigt mir anhand eines Startpunktes und einer einstellbaren Zeit alle Strassen, an die anhand der eingestellten Parameter erreichen kann. Ich würde gerne selber so ein Tool bauen, finde aber keine richtigen Anhaltspunkte dazu.

1. Wir beschaffen die Daten:

Wir holen die Innenstadt von Köln ab (ca. 40Mb):

wget -O data.osm http://www.overpass-api.de/api/xapi?map?bbox=6.938,50.920,6.978,50.951

2. Wir erzeugen einen Routing-Graphen:

Die OSM-Datei enthält in dieser Reihenfolge Einträge für Changesets, für Nodes, für Ways und für Relationen. Wir interessieren uns nur für die Nodes und die Ways.

  1. Zu jedem OSM-Objekt sammeln wir die Attribute im Hash %attr und verwerfen sie am Ende des Objektes.
  2. Beim Einlesen einer Node speichern wir die Koordinaten dieser Node in den Hashes %lon und %lat.
  3. Beim Einlesen eines Ways speichern wir die Liste der Nodes, aus denen der Way besteht, im Array @nodeIds.
  4. Nach dem Einlesen eines Ways erfolgt die eigentliche Arbeit:
    • aus den Attributen wird bestimmt, ob dieser Way für uns überhaupt interessant ist; uninteressante Ways werden verworfen.
    • aus den Attributen wird bestimmt, wie schnell wir auf dem Way unterwegs sind, und zwar getrennt nach Vorwärts- und Rückwärtsrichtung: wenn wir Einbahnstraßen berücksichtigen, ist die Geschwindigkeit in Rückwärtsrichtung 0.
    • Danach wird der Way in Teilstücke zerschnitten, für jedes Teilstück wird die Länge berechnet, aus Länge und Geschwindigkeit die Länge in Zeiteinheiten, sodann diese Graphkante ausgegeben als Datensatz mit den Ids der beiden Knoten und der berechneten Länge (sowie der Quelle der Daten, also Id des Ways, die Richtung und den benutzten Abschnitt des Ways). Außerdem wird je benutzter Node ein Datensatz mit den Koordinaten dieser Node geschrieben.

Die gleiche Datenvorverarbeitung und der gleiche Routing-Graph werden auch von der einfachen Routensuche genutzt.

Diesen Ablauf implementiert das Perl-Skript analyze.pl (~60 Zeilen Code).

Wir rufen das Skript auf:

./analyze.pl <data.osm >database.csv

Und erhalten eine Textdarstellung des Routing-Graphen in der Datei database.csv (~2.1Mb).

Der Graph enthält Knoten mit Id und Koordinaten:

node n743325638 6.9722186 50.9463142

und gerichtete Kanten mit Angabe der verbundenen Knoten, der Entfernung, und der Quelle der Daten, bestehend aus OSM-Way-Id, Richtung und Segmentnummer:

arc n743325638 n743325592 10.0407049925005 w59865404 f 0

3. Wir führen die Erreichbarkeitsanalyse durch:

Wir setzen die Entfernung des Startknotens (von sich selbst) auf 0 und erzeugen eine Liste der Knoten, die bereits ein Entfernung haben (welche aber möglicherweise noch verbessert wird), deren Nachbarn aber noch analysiert werden müssen. Diese Liste besteht zu Anfang nur aus dem Startknoten.

Aus dieser Liste entnehmen wir jeweils den Knoten mit der geringsten Entfernung. Wir verfolgen alle von diesem Knoten ausgehenden Kanten und bestimmen die Entfernung zu den erreichten Knoten als Summe aus unserer Entfernung und der Länge der benutzen Kanten. Falls der erreichte Knoten bereits eine Entfernung hatte, bekommt er als neue Entfernung das Minimum aus alter und neuer Entfernung.

Wenn wir einen Knoten zum ersten Male erreichen, nehmen wir ihn in unsere Liste auf.

Für jede benutzte Kante erzeugen wir einen Datensatz, und zwar einen arc-Datensatz (wird später als blaue Linie dargestellt), wenn die neue Entfernung unterhalb des Limits liegt, und einen noarc-Datensatz (wird später als rote Linie dargestellt), wenn die neue Entfernung über dem Limit liegt.

Wurde mindestens ein noarc-Datensatz erzeugt, wird für den Ausgangsknoten ein inner-Datensatz erzeugt; dieser wird später als blauer Punkt dargestellt.

Diesen Ablauf wiederholen wir, bis unsere List nur noch Knoten enthält, der Entfernung größer ist als unser Limit. Für jeden dieser Konten wird ein outer-Datensatz erzeugt, der später als roter Punkt dargestellt wird.

Diesen Ablauf implementiert das Perl-Skript reachable.pl (~80 Zeilen Code).

Wir rufen das Skript mit der Startposition und maximalen Entfernung (in Zeiteinheiten) auf:

./reachable.pl 50.936 6.948 500 <database.csv >reachable.txt

und erhalten die Erreichbarkeitsanalyse in der Datei reachable.txt (~240Kb).

Diese enthält den Startknoten start, gerade noch erreichbare Knoten inner und nicht mehr erreichbare Knoten outer, jeweils mit Angabe der Koordinaten:

start 6.9479894 50.9358304
inner 6.9510076 50.9330590
outer 6.9394997 50.9355044

Außerdem die erreichbaren Kanten arc und nur teilweise erreichbare Kanten noarc jeweils mit Anfangs- und Endkoordinaten:

arc 6.9479894 50.9358304 6.9470897 50.9358754
noarc 6.9510076 50.9330590 6.9525011 50.9332148

4. Wir machen das Ergebnis der Analyse sichtbar:

Dazu dient uns eine HTML-Seite reachable.htm (~150 Zeilen HTML und JavaScript).

Wir legen diese HTML-Seite reachable.htm und unsere Erreichbarkeitsanalyse reachable.txt in ein Verzeichnis auf einem Webserver, rufen die Seite auf, und erfreuen uns des Ergebnisses. Und danach dürfen wir spielen.

5. Einschränkungen:

Die wenigen Codezeilen implementieren natürlich nur eine rudimentäre Erreichbarkeitsanalyse. Beispiele von Einschränkungen sind:

  • Bei Flächen (area=yes) laufen wir nur am Rand entlang;
  • Nutzungsbeschränkungen (access=*) und Abbiegerestriktionen werden ignoriert.
  • Weil Ways an jedem einzelnen node aufgetrennt werden, hat der Graph mehr Knoten und Kanten als nötig; dies verlangsamt den Algorithmus.
  • Würde der Graph binär gespeichert, wäre das Einlesen deutlich schneller.
  • Die Bearbeitungsliste @nodesToBeAnalyzed wird für jeden Knoten neu erzeugt und sortiert. Mit einer geschickten Datenstruktur (Heap oder Ordered Hash) würde der Algorithmus deutlich an Geschwindigkeit gewinnen.

Diese Liste ist nicht vollständig.

6. Nutzung: