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.
- Zu jedem OSM-Objekt sammeln wir die Attribute im Hash
%attr
und verwerfen sie am Ende des Objektes. - Beim Einlesen einer Node speichern wir die Koordinaten dieser Node in den Hashes
%lon
und%lat
. - Beim Einlesen eines Ways speichern wir die Liste der Nodes, aus denen der Way besteht,
im Array
@nodeIds
. - 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
-Datensatz
(wird später als blaue Linie dargestellt), wenn die neue Entfernung unterhalb des Limits
liegt, und einen arc
-Datensatz (wird später als rote Linie
dargestellt), wenn die neue Entfernung über dem Limit liegt.
noarc
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
und nur teilweise erreichbare
Kanten arc
jeweils mit Anfangs- und Endkoordinaten:
noarc
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 einzelnennode
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.