OpenStreetMap-Projekt: Teil2 – Von den Rohdaten zum gerichteten Graphen

Im 2. Teil des Projektes soll es darum gehen, einen gerichteten Graphen aus den in Teil 1 in die Datenbank eingelesenen OpenStreetMap-Daten zu erstellen, mit dem später z.B. eine Wegsuche realisiert werden kann.

Bild1: Beispiel-Darstellung von einigen Wegen nach OSM-Schema

Bild1: Beispiel-Darstellung von einigen Wegen nach OSM-Schema

In Bild1 ist  Beispielhaft ein Ausschnitt aus einer möglichen Karte aus den Rohdaten zu sehen, die allerdings für eine Wegsuche viele unnötige Knoten enthält und deren Datenstruktur für unsere Zwecke nicht sonderlich praktisch ist. Wir brauchen für die Wegsuche nur die Weglänge zwischen zwei verbundenen End- oder Kreuzungs-Knoten.

Die Knoten 3, 4, 6, 9 und 10 brauchen wir nicht.
Prinzipiell ist auch Knoten 1 nicht notwendig, wenn der rote Weg eine Einbahnstraße ist und der braune jedoch nicht oder auf einer der beiden Straßen eine Geschwindigkeitsbeschränkung gilt, wird er doch wieder gebraucht. In den Open-Streetmap-Daten sind auch Brücken durch einen eigenen Weg eingezeichnet. Damit kosten uns Brücken und Tempobeschränkungen zusätzliche Verbindungen, ich nehme das in diesem Fall aber in Kauf, um später Tempobeschränkungen und Einbahnstraßen berücksichtigen zu können.

Bild2: Optimierte Wegdarstellung durch die Verbindungs-Tabelle

Bild2: Optimierte Wegdarstellung durch die Verbindungs-Tabelle

Die Verbindungs-Tabelle enthält also eine Zeile für jeden Startknoten, Endknoten und der Wegstrecke dazwischen, wie in Bild2 (die natürlich notwendige Entfernung zwischen den Knoten fehlt hier). Weil wir Einbahnstraßen berücksichtigen wollen, werden Verbindungen, die keine Einbahnstraßen sind, werden in beide Richtungen einmal abgelegt. Das ist zwar nicht effizient, vereinfacht aber unserer Arbeit. Optimieren können wir auch noch, wenn erst mal alles läuft, wie wir uns das vorstellen.

Zunächst muss die eine Tabelle verbindungen mit diesem SQL-Skript angelegt werden. Zum Erstellen der Verbindungstabelle nutze ich dann eine Stored Procedure. Die arbeitet direkt in der Datenbank und ist deshalb recht schnell. Ihr Ablaufdiagramm ist im Bild3 zu sehen. Zu Beginn wird eine sehr aufwändige Abfrage ausgeführt, die einen Großteil der Informationen ausliest, die später benötigt werden und mit einem Cursor zeilenweise abgearbeitet wird. In ihr wird festgelegt, welche Wege überhaupt berücksichtigt werden. Wenn wir einen Routenplaner für Autos wollen, ist es wohl eher nicht so hilfreich Fußwege und Treppen in der Karte zu haben.

Bild3: Ablaufdiagramm zum Erstellen der Verbindungen

Bild3: Ablaufdiagramm zum Erstellen der Verbindungen

Das hier bereitgestellte Skript berücksichtigt bereits Einbahnstraßen, das macht die Abfrage zu Beginn zwar noch aufwändiger, allerdings ist es für Autofahrer einfach nicht interessant Einbahnstraßen in Gegenrichtung zu befahren.

Mit dem Befehl

CALL erstelleVerbindungen();

kann die Datenbank gefüllt werden. Das dauert wieder ziemlich lange. Alleine das Erstellen der ersten Abfrage nimmt bei mir für Baden-Württemberg bereits über 3 Minuten in Anspruch, aber erst danach werden auch Daten geschrieben. Diese Procedure kann sicherlich noch optimiert werden, ich habe mich damit nicht mehr genauer beschäftigt, als sie in brauchbarer Zeit das gewünschte Ergebnis geliefert hatte.

[Update 24.10.] Ich habe noch einen Fehler im Skript entdeckt, der lustige Fehler produziert hat. Einige Straßen, wie die Europabrücke über den Rhein bei Karlsruhe hatten in Baden-Württemberg nur einen Wegpunkt. Das hatte den Effekt, dass große Strecken mit Entfernung 0 in die Verbindungsliste eingetragen wurden, die eigentlich nicht mal verbunden waren. So lässt sich natürlich keine ordentliche Wegsuche realisieren. Der Fehler ist aber nun behoben.

Kommentare

One Kommentar zu “OpenStreetMap-Projekt: Teil2 – Von den Rohdaten zum gerichteten Graphen”

  1. Peter am October 18th, 2009 10:40

    Die Scripte kann man nicht runterladen. Server Error. Guck mal nach dem “chmod”. Ansonsten bin ich ziemlich beeindruckt, was du so “in der freizeit” machst.

Schreibe einen Kommentar