© Arnd_Drifte, photocase.com

Mit GPS-Geräten erfassen freiwillige Helfer die Straßen ihrer Heimat für den freien Openstreetmap-Atlas. Ganz pedantische kartografieren auch gleich die Eigenheiten der Parkzone ihres Viertels.

Ein Blick auf die Openstreetmap-Karte der Münchner Innenstadt (Abbildung 1) offenbart in akribischer Kleinstarbeit gesammelte und frisch gehaltene Kartendaten. Das OSM-Projekt verwöhnt nicht nur mit Straßenverläufen und -namen, sondern auch mit Bushaltestellen, Bahnlinien und Radwegen. Bei Geschäften und Restaurants, deren Standorte sich oft von einem Monat zum anderen ändern, ist Openstreetmap (OSM) mit seinem so genannten Crowdsource-Verfahren mittlerweile aktueller als so mancher professionelle Anbieter.

Abbildung 1: Das Openstreetmap-Projekt zeigt die freie Karte der Münchner Innenstadt.

Freie Datenwahl

Vorteil gegenüber kommerziellen Anbietern ist der freie Datenexport. Per Knopfdruck auf der Webseite oder programmatisch per API auf [api.openstreetmap.org] darf jedermann die XML-Daten herunterladen, auf denen die Karten basieren. Damit öffnet sich die Tür für kreative Basteleien. Das Datenmodell ist denkbar simpel: So genannte Nodes bezeichnen Wegpunkte, die ihren Standort in der realen Welt mittels Koordinaten in geografischer Breite und Länge angeben. Der Verlauf einer Straße ergibt sich dann durch das Verbinden dieser Nodes mit Wegstrecken, den so genannten Ways.

Import/Export

Abbildung 2 zeigt die XML-Darstellung der OSM-Daten der Sonnenstraße am Stachus in München. Beim Klick auf den Reiter »Export« in der Kartendarstellung erscheint der Dialog in Abbildung 5. Nach dem Auswählen der Option »XML« und dem Drücken des Submit-Buttons lädt der Webbrowser eine XML-Datei des angezeigten Bereichs herunter. Die Way-Definition im unteren Bereich von Abbildung 2 enthält Referenzen auf insgesamt elf Nodes. Die letzten beiden, »1156387191« und »361792« , sind im oberen Teil der Datei auch als Node-Definitionen sichtbar.

Abbildung 5: Die hinter der Karte stehenden XML-Daten darf jedermann herunterladen und verwenden.

Abbildung 2: Der Openstreetmap-Server exportiert die Kartendaten auf Wunsch als XML unter einer freien Lizenz.

Neben den geografischen Koordinaten »lat« und »lon« für die geografische Breite und Länge im Digitalformat listet ein Node auch noch auf, wer (»user« ) ihn wann (»timestamp« ) erfasst hat und in welchem »changeset« die Daten an den OSM-Server hochgeladen wurden.

Ways formen Straßen

Eine Straße setzt sich im XML der OSM-Datenbank aus einem oder mehreren Ways zusammen. Den Namen der Straße, zu dem ein Way gehört, führt dieser als Tag unter dem Attribut »name« . Die drittletzte Zeile in Abbildung 2 weist deshalb im XML-Tag »tag« des Way dem Schlüssel »k=”name”« den Wert »v=”Sonnenstraße”« zu.

Zu beachten ist, dass der dort gezeigte Way mit der ID 3654453 keineswegs den gesamten Verlauf der Sonnenstraße in München zeigt, sondern nur einen kleinen Abschnitt. Besonders bei längeren Straßen ist es üblich, dass mehrere Ways mit dem gleichen Tag »name« den Gesamtverlauf festlegen.

Flexible Strategie

Die im XML in Abbildung 2 sichtbaren Ways-Tags »highway« (Straßenart), »lanes« (Anzahl der Spuren), »name« (Straßenname) und »oneway« (Einbahnstraße) hat das Projekt über die Jahre standardisiert, doch es erlaubt praktisch beliebige Erweiterungen. Das Design ist so flexibel ausgelegt, damit schnell und unbürokratisch neue Funktionen hinzukommen können.

Der Nachteil dieses flexiblen Ansatzes ist ein gewisser Wildwuchs, der Anhängern normalisierter Datenbankschemata das Wasser in die Augen treibt. Damit Applikationen neu erfasste Daten weltweit verarbeiten können, müssen sich die Helfer aber zusammenraufen, und das geschieht üblicherweise auf dem OSM-Wiki und dessen Talk-Seiten [2]. Schlägt dort zum Beispiel jemand ein Schema für Briefkästen oder Geschäftsöffnungszeiten vor, entwickelt sich nach reger Diskussion oft ein neuer Standard.

Selbst ist der Mapper

Damit die Mapper selbst ihre Änderungen in der OSM-Datenbank vornehmen können, hilft eine ganze Reihe von Tools, allen voran die Online-Editoren Josm [3] und Potlatch [4]. Josm ist zwar schon etwas in die Jahre gekommen und seine im Crossplattform-Java-Look erscheinende Bedienoberfläche dürfte Ästheten eher abstoßen, doch er bietet alle notwendigen Funktionen. Betritt man Neuland mit bislang unbekannten Tags, ist Jsom sogar meist der einzige Editor mit der dafür geforderten Funktion.

Potlatch hingegen ist eine direkt im Browser laufende Flash-Applikation, die hübsch poliert daherkommt und sich mittlerweile zum Standard fürs Editieren der Karten gemausert hat.

Die heute vorgestellten Änderungen, Straßensäuberungsdaten in meiner Wahlheimat San Francisco, fallen in die Kategorie “Exoten”, deswegen kommt Josm zum Einsatz. Die in den Repositories aktueller Distributionen lungernden Jsom-Versionen sind meist veraltet. Es empfiehlt sich daher, die aktuelle Jar-Datei »josm-tested« direkt von der Projektseite [3] zu laden und mit

java -jar josm-tested.jar

zu starten, was Java in der Version 1.6 erfordert. Ein Klick auf das Icon mit dem grünen nach unten weisenden Pfeil in der Kopfleiste des Applikationsfensters (oberer Rand in Abbildung 3) öffnet ein Dialogfenster, in dem der Hobbykartograf mit der Maus einen rechteckigen Bereich auswählen kann.

Abbildung 3: Der Jsom-Editor lädt die Kartendaten eines ausgewählten Bereiches in den Arbeitsspeicher.

Wenn der Anwender jetzt auf den weiter unten liegenden »Download« -Button drückt, holt Jsom die selektierten Kartendaten vom OSM-Server und lädt sie in den Arbeitsspeicher des Editors. Der Mapper sieht anschließend im »Data-Layer« bereits definierte städtische Strukturen und kann Änderungen vornehmen oder neue Daten hinzufügen. Einen angezeigten Way klickt man mit der Maus an, bis er hell aufleuchtet.

Im Fenster »Properties« auf der rechten Seite in Abbildung 4 erscheinen dann alle auf dem Way definierten Tags (etwa »name« , das im Beispiel auf »23rd Street« gesetzt ist). Ein Klick auf den »Add« -Button öffnet ein Dialogfenster, in dem der User neue Tag-Namen und die zugehörigen Werte eintragen kann.

Abbildung 4: Mit Jsom trägt der Openstreetmap-Helfer die 2-Stunden-Parkzone auf der 23sten Straße ein.

Passt alles, lädt ein Klick auf das Icon mit dem grünen Pfeil nach oben (Kopfleiste in Abbildung 3) die Daten auf den OSM-Server hoch. Hierzu registriert sich der Mapper mit seiner E-Mail-Adresse und legt einen Useraccount mit Passwort an. Die Daten sind, ähnlich wie bei Wikipedia, ohne Prüfschritt sofort auf dem Live-Server sichtbar.

Wildwest-Parkregeln

San Francisco ist wie alle größeren Städte der Welt vollständig auf Openstreetmap erfasst. Allerdings stellt es mit seinen komplizierten Parkregeln einige Herausforderungen an touristische Autofahrer. Diese bürokratischen Vorschriften in die freie Weltkarte einzubinden, erschien mir als lohnendes Projekt.

Wer meint, geparkt würde hier nach Wildwestmanier, irrt sich. Auf der 23. Straße bei mir um die Ecke dürfen Autos ohne Anwohnerplakette montags bis freitags von 8 bis 18 Uhr nur 2 Stunden lang parken. Anwohner mit der Parkmarke Z sind davon ausgenommen. Außerdem fährt in San Francisco auf den meisten Straßen an bestimmten Tagen das Kehrauto [5] durch und während dieser angegebenen 2-Stunden-Frist darf auf der betroffenen Straßenseite niemand parken. Wer’s dennoch tut, bekommt einen Strafzettel über 55 Dollar. Das Straßenschild in Abbildung 6 zeigt die Parkbedingungen im Detail. Sie variieren oft von Kreuzung zu Kreuzung und folgen einem geheimen Plan, den wahrscheinlich nur der Kehrauto-Fahrer kennt.

Abbildung 6: Dem Touristen nicht auf Anhieb verständlich: Anwohnerparken und die wöchentliche Straßenreinigung.

Parkbürokraten am Werk

Bis San Franciscos Parkregeln stadtweit in der OSM-Datenbank stehen, dürfte noch einige Zeit ins Land ziehen. In deutschen Landen ist man diesbezüglich schon weiter: Aus Abbildung 7 geht hervor, dass Mapper die Parkzonen der bayerischen Stadt Bamberg praktisch vollständig erfasst haben, der extra für Parkplatzinformationen aufgestellte Server [parking.openstreetmap.org] blendet Parkscheiben an den entsprechenden Stellen ein. Das Wiki mit dem Vorschlag für ein Straßenparktag-Format [6] listet weitere führende Städte auf.

Abbildung 7: Die Parkzonen der Bamberger Innenstadt sind schon relativ vollständig erfasst (Parking.openstreetmap.org).

Nach einer langwierigen Diskussion kristallisierten sich die Tags in Abbildung 8 für Straßenparkregeln auf der ganzen Welt heraus. Die ersten drei Tags beschreiben das Anwohnerparken, der zweite Block die Straßenreinigungszeit für die linke und der dritte Block für die rechte Straßenseite.

Abbildung 8: Nach dem Hochladen der Daten zum OSM-Server weiß die ganze Welt, wann man auf der 23rd Street in San Francisco parken darf.

Lechts und rinks

Doch wo ist “left” und wo “right”? Ways in OSM weisen immer in eine Richtung, denn sie zeigen von einem Node zum anderen. Das ist für die erfasste Straße oft irrelevant (außer bei Einbahnstraßen) und spiegelt nur die oft willkürliche Wahl des Mappers wider. Im Fall der Parkregeln in San Francisco legt die Richtung bei einseitig definierten Reinigungszeiten jedoch genau fest, wann das Kehrauto auf welcher Seite fährt.

Abbildung 4 zeigt den Editor Josm beim Einfügen eines neuen Tag mit dem Namen »parking:condition:left:maxstay« in einen Way, der Abschnitte der 23. Street mit einer maximalen Parkdauer von 2 Stunden für Autos ohne Anwohner-Marke auszeichnet. Noch eine Komplikation: Die Regel, dass das Kehrauto nur jeden zweiten Dienstag im Monat kommt, lässt sich ebenfalls über einen bereits verabschiedeten OSM-Standard ausdrücken.

Öffnungszeiten von Geschäften gehorchen ähnlichen Regeln, deswegen schlugen die OSM-Mapper kurzum vor, diese bereits existierende Syntax auch für Parkregeln zu verwenden. [7] gibt Auskunft darüber, wer dafür verantwortlich zeichnet und wann es passiert ist. Der Ausdruck »Fr[2,4]« steht so für den zweiten und den vierten Freitag im Monat.

Sofort sichtbar

Nach dem Hochladen kann jedermann die Änderung (Abbildung 8) bewundern. Der Clou ist, dass Anwendungen diese Daten frei nutzen können. Wie wäre es mit einem Skript, das Bescheid gibt, wann das Kehrauto kommt, wenn ich auf der Chattanooga Street auf der rechten Seite zwischen 23. und 24. Straße parke? Listing 1 holt dazu Daten von OSM und spuckt Sekunden später die Antwort aus:

001 #!/usr/local/bin/perl -w
002 use strict;
003 use Geo::Parse::OSM;
004 use Graph::Directed;
005 use LWP::UserAgent;
006
007 my @bbox = qw( -122.4374  37.74754
008                -122.42096 37.75894 );
009 my $url = "http://api.openstreetmap.org/" .
010   "api/0.6/map?bbox=" . join ',', @bbox;
011
012 my $mapfile = "map.osm.gz";
013
014 my( $street_on, $street_cross1,
015     $street_cross2, $side ) = @ARGV;
016 die "usage: $0 street cross1 cross2 side"
017   if !defined $side;
018
019 my $ua = LWP::UserAgent->new();
020 $ua->default_header("Accept-Encoding",
021                     "gzip");
022 if( ! -f $mapfile or -M $mapfile > 7 ) {
023   my $rsp = $ua->mirror( $url, $mapfile );
024   $rsp->is_success or die $rsp->message();
025 }
026
027 my $osm = Geo::Parse::OSM->new( $mapfile );
028
029 my %on_nodes = ();
030
031 street_nodes( $osm, $street_on, sub {
032   $on_nodes{ $_[0] } = 1;
033 } );
034
035 my $cross1_node = cross_find( $osm,
036       \%on_nodes, $street_cross1 );
037 my $cross2_node = cross_find( $osm,
038       \%on_nodes, $street_cross2 );
039
040 my( $nodes, $flip_order) =
041   find_path_on_way( $osm, $street_on,
042          $cross1_node, $cross2_node );
043
044 $side = flipside( $side, $flip_order );
045
046 my $parking = parking($osm, $nodes, $side);
047
048 print "Street Cleaning: ",
049       street_cleaning( $parking ), "\n";
050
051 ###########################################
052 sub street_nodes {
053 ###########################################
054   my( $osm, $name, $cb ) = @_;
055
056   $osm->seek_to( 0 );
057   $osm->parse( sub {
058     my($n) = @_;
059     if( exists $n->{tag}->{name} and
060       $n->{tag}->{name} eq $name ) {
061       for my $n ( @{ $n->{chain} } ) {
062         $cb->( $n ) or last;
063       }
064     }
065   }, only => "way");
066 }
067
068 ###########################################
069 sub cross_find {
070 ###########################################
071   my($osm, $on_nodes, $cross_street) = @_;
072
073   my $found;
074   street_nodes( $osm, $cross_street, sub {
075     my($n) = @_;
076     if( exists $on_nodes->{ $n } ) {
077       $found = $n;
078       return 0; # stop iteration
079     }
080     return 1; # continue iteration
081   });
082
083   return $found;
084 }
085
086 ###########################################
087 sub find_path_on_way {
088 ###########################################
089   my( $osm, $way_name, @nodes ) = @_;
090
091   my $g = Graph::Directed->new();
092
093   $osm->seek_to(0);
094   $osm->parse(sub {
095     my($n) = @_;
096     if( exists $n->{tag}->{name} and
097         $n->{tag}->{name} eq $way_name ) {
098       $g->add_path( @{ $n->{chain} } );
099     }
100   }, only => "way" );
101
102   my $flip_order = 0;
103
104   my @path = $g->SP_Dijkstra( @nodes );
105
106   if( !@path ) {
107       @nodes = reverse @nodes;
108       @path = $g->SP_Dijkstra( @nodes );
109       $flip_order = 1;
110   }
111
112   return( \@path, $flip_order );
113 }
114
115 ########################################
116 sub parking {
117 ########################################
118   my( $osm, $nodes, $side ) = @_;
119
120   my %to_match = map { $_ => 1 } @$nodes;
121   my %results  = ();
122
123   $osm->seek_to( 0 );
124   $osm->parse( sub {
125     my($w) = @_;
126
127     my @matches =
128       grep { exists $to_match{$_} }
129            @{ $w->{chain} };
130
131     return if @matches < 2;
132
133     for my $tag ( keys %{ $w->{tag} } ) {
134       if( $tag =~
135           /parking:condition:$side:.*/ ) {
136         $results{$tag} = $w->{tag}->{$tag};
137       }
138     }
139   }, only => "way");
140
141   return \%results;
142 }
143
144 #######################################
145 sub street_cleaning {
146 #######################################
147   my( $parking ) = @_;
148
149   for my $key ( keys %$parking ) {
150     if( $key =~ /(.*)\:reason/ ) {
151       if( $parking->{ $key } eq
152           "street_cleaning" ) {
153         return $parking->{ $1 .
154             ":time_interval" };
155       }
156     }
157   }
158
159   return undef;
160 }
161
162 ########################################
163 sub flipside {
164 ########################################
165   my($side, $flip_order) = @_;
166
167   if( $flip_order ) {
168     if( $side eq "left" ) {
169       $side = "right";
170     } else {
171       $side = "left";
172     }
173   }
174
175   return $side;
176 }

$ ./street-cleaning "Chattanooga Street"?
"23rd Street"
 "24th Street" right
Street Cleaning: We[2,4] 08:00-10:00

Das Skript lädt sich dafür zunächst eine XML-Datei des Stadtteils Noe Valley in San Francisco von dem OSM-Projekt-Server herunter. Wie die Abbildung 5 zeigt, liegt das zu betrachtende Viertel zwischen -122,43738 und -122,42098 Grad geografischer (und wegen der negativen Werte westlicher) Länge und zwischen 37,74754 und 37,7589 Grad nördlicher Breite. Zeile 9 im Listing 1 formt daraus eine URL für das API des OSM-Servers, Zeile 23 spiegelt die komprimierte XML-Datei unter »map.osm.gz« auf der lokalen Platte.

Die If-Bedingungen in Zeile 22 prüfen dann, ob die Datei eventuell schon existiert, und auch, ob sie nicht älter als eine Woche ist. Zusätzlich unterbinden sie eine erneute Übertragung relativ neuer Daten. Der Zusatzheader »Accept-Encoding« in Zeile 20 signalisiert dem Server, dass der Client sich eine per Gzip komprimierte Datei wünscht. Die XML-Daten durchforstet das Modul Geo::Parse::OSM vom CPAN, dessen Methode »parse()« einen Callback annimmt, den sie jedes Mal anspringt, wenn sie ein gesuchtes Element findet. Zu beachten ist, dass »parse()« nichts mehr findet, falls es schon durchgelaufen ist, und nur ein »seek_to(0)« den Parser für eine neue Suche wieder auf Anfang der Datei setzt.

Um im Straßenlabyrinth einen oder mehrere OSM-Ways zu finden, die sich zwischen zwei Querstraßen auf einer Hauptstraße befinden, legt der Aufruf von »street_nodes()« in Zeile 31 erst alle Node-Nummern der Hauptstraße als Schlüssel im Hash »%on_street« ab.

Die Funktion »street_nodes()« ab Zeile 52 klappert mit der Einschränkung »only => “way”« alle Ways der XML-Datei ab, sucht nach einem, der im »name« -Tag den Wert der Hauptstraße führt, und springt mit seiner Referenznummer den hereingereichten Callback an. Gewappnet mit den Nodes der Hauptstraße bestimmen die Aufrufe von »cross_find()« (definiert ab Zeile 69) in den Zeilen 35 und 37 die Nodes, auf denen die auf der Kommandozeile angegebenen Querstraßen die Hauptstraße schneiden. Nun stehen die Nodes N2 und N5 fest (Abbildung 9). Es kann aber vorkommen, dass die Verbindungsstrecke zwischen zwei Kreuzungen aus mehreren Ways besteht.

Abbildung 9: Nodes zwischen Querstraßen ermittelt der Dijkstra-Algorithmus.

Von N2 aus muss der Algorithmus sich nun in eine Richtung bewegen – hoffend, dass er bei N5 ankommt und nicht in der Sackgasse bei N1 endet.

Edsger W. Dijkstra hilft

Algorithmus-Urgestein Edsger W. Dijkstra hat das Problem 1959 gelöst [8]. Das CPAN-Modul Graph bietet das Verfahren als Methode »SP_Dijkstra()« an. Sie nimmt zwei zu verbindende Nodes entgegen und berechnet auf Basis des bislang definierten gerichteten Graphen (Directed Acyclic Graph, DAG) den kürzesten Weg von N2 nach N5 (Abbildung 9).

Die ab Zeile 87 definierte Funktion »find_path_on_way()« implementiert das Verfahren. Erst erzeugt sie ein neues Objekt vom Typ Graph::Directed und legt über den von »parse()« angesprungenen Callback für alle gefundenen Ways mit dem Straßennamen mit jeweils allen in der Datenstruktur »chain« enthaltenen Nodes einen Pfad im DAG an. Findet die Methode »SP_Dijkstra()« keinen Weg von A nach B, zeigen die willkürlich gewählten Richtungspfeile zwischen den Nodes wohl in die verkehrte Richtung, Zeile 107 dreht dann die Reihenfolge der Nodes um. In der Variablen »flip_order« merkt sich die Funktion das, später weiß das Hauptprogramm, dass “links” in diesem Fall nicht “links” in Richtung der Ways-Richtung meint, sondern “rechts”.

Die Funktion »parking()« durchforstet den Pfad aus Nodes und speichert das letzte auf den Ways gefundene Park-Tag – in der Annahme, dass die Parkzone innerhalb eines Straßenblocks unverändert bleibt, was für die Straßenreinigung stimmt, bei anderen Parkinformationen aber falsch wäre.

Fand eine Richtungsumkehr statt, ändert die Funktion »flipside()« , definiert ab Zeile 163 und aufgerufen in Zeile 44, den String »left« in »right« und umgekehrt. Die Funktion »street_cleaning()« ab Zeile 145 spürt nur eventuell vorhandene Parking-Tags auf, extrahiert die richtige Straßenseite (»left« /»right« ) und gibt sie aus, und schon ist klar, wann die Kehrmaschine kommt.

Ausblick

Ich werde nun in meinem Viertel “Noe Valley” fleißig Parkdaten sammeln und zu OSM hochladen. Mir schwebt eine Webapplikation vor, auf der ich den aktuellen Stellplatz meines Zweitautos Perly Perlman eintrage und die mich per Mail warnt, falls das Kehrauto mit der Strafzettelwespe [9] im Schlepptau kommt. Das könnte sich bezahlt machen.