User:Maxbe/Bürgersteigrouting

Worum gehts?

Motivation

Eine der periodisch auftauchenden Diskussionen im Forum zu diesem Thema, die vielen nützlichen Ideen der Diskutierenden und der Wunsch, sowas auch mal gemacht zu haben, um mitreden zu können ;)

Das Problem

Wir haben zwei Möglichkeiten, Bürgersteige zu erfassen:

Getrennt: Man zeichnet den Bürgersteig als eigenen Weg mit highway=footway ein. Zur Unterscheidung von anderen Fusswegen, die keine Bürgersteige sind, wird diesem Fussweg noch ein Attribut "footway=sidewalk" mitgegeben. Überquert dieser Fussweg eine Strasse wird die Kreuzung wie jede andere Strassenkreuzung behandelt: Es gibt einen gemeinsamen Punkt, der zu Fussweg und Strasse gehört. Eventuell wird dieser Punkt oder der gesamte Fussweg auf dem kurzen Stück der Querung als Ampel oder Zebrastreifen gekennzeichnet oder mit zusätzlichen Beschreibungen zum Bordstein oder ertastbaren Markierungen versehen.

Zusammen mit der Strasse: Man hängt einfach noch ein Attribut "sidewalk=left/right/both" an die Strasse. Besondere Querungsmöglichkeiten werden durch einen Punkt auf der Strasse gekennzeichnet, der ebenfalls Beschreibungen zur Art des Übergangs und zum Bordstein bekommen kann.

Üblicherweise berücksichtigen Router die sidewalk-Attribute der Bürgersteige nicht, sondern folgen einfach den gemappten Linien.

• Ein Router wird bei getrennt gemappten Bürgersteigen die Fahrbahnen nur an den gemappten Übergängen überqueren. Das ist gut für Nutzer, die diese Querungen bevorzugen, z.B. weil sie auf abgesenkte Bordsteine, Ampeln, Zebrastreifen oder Schülerlotsen Wert legen. Nutzer, die die Strasse auch an anderen Stellen überqueren können, bekommen aber auch nur Routenvorschläge mit diesen besonderen Querungsmöglichkeiten und müssen Umwege in Kauf nehmen. Im Folgenden wird diese Art Routing "Seniorenrouting" genannt.
• Bei zusammen gemappten Bürgersteigen folgt der Router der Mitte der Fahrbahn. Er weiss nicht einmal, ob eine Fahrbahn überquert wird, weil Fahrbahn und Bürgersteige für ihn nur ein einziger Strich ohne seitliche Ausdehnung sind und kann deshalb die Fahrbahn an beliebigen Stellen überqueren. Das ist gut für Nutzer, die überall über Bordsteine und Fahrbahnen springen wollen, benachteiligt aber Leute die besondere Querungen bevorzugen. Im Folgenden wird das "Sportrouting" genannt.

Anm: Die Bezeichnungen "Sportrouter" und "Seniorenrouter" sind natürlich völlig unpassend, aber mir fallen keine passenderen Kurzbezeichnungen ein ...

Das Ziel

Es wäre nützlich, beide Schemata in etwas umzuwandeln, was sowohl für Sportrouter als auch für Seniorenrouter brauchbar ist.

• Dazu werden bei getrennt gemappten Bürgersteigen virtuelle Querungsmöglichkeiten über die Fahrbahn gezogen. Die befinden sich an den Stellen, die der Mapper zwar nicht als besonders geeignete Stellen erachtet hat, an denen aber das Überqueren der Fahrbahn möglich ist.
• Bei zusammen mit der Fahrbahn gemappten Bürgersteigen werden vorher die Fusswege ein paar Meter neben dem Mittelstreifen eingezeichnet. Die als Punkt markierten Querungen werden als besonders geeignete Übergänge eingetragen und es werden beliebige weitere virtuelle Querungsmöglichkeiten über die Fahrbahn gezogen.

Das ganze passiert natürlich nicht in der richtigen OSM-Datenbank, sondern nur in der internen Repräsentation der Wege im Router. Die zusätzlichen virtuellen Querungen könnten theoretisch in beliebig kleinen Abständen eingetragen werden, zur besseren Übersichtlichkeit und wegen begrenzter Rechenzeit werden sie aber nur alle paar Meter eingetragen.

• Ein Sportrouter wird sie bei getrennt gemappten Bürgersteigen verwenden. Bei zusammen mit der Fahrbahn gemappten Bürgersteigen kann er sich das Umwandeln sparen. Allerdings hätte auch er einen Vorteil von der Umwandlung: Fahrbahnquerungen sind auch für seine Nutzer lästig und sollten vermieden werden.
• Ein Seniorenrouter muss bei zusammen mit der Fahrbahn gemappten Bürgersteigen die Umwandlung durchführen, um seine Nutzer zu geeigneten Übergängen zu führen. Bei getrennt gemappten Bürgersteigen kann er die zusätzlichen Querungen ignorieren. Zumindest die Zuordnung, welche Fahrbahn von einem Bürgersteig begleitet wird, ist allerdings auch für einen Seniorenrouter nützlich: Er muss Fahrbahnen möglichst vermeiden, kann sie aber nicht grundsätzlich sperren, weil er sonst keine Strassen verwenden würde, die keinen Bürgersteig haben. Da wäre eine Regel "gehe nicht auf der Fahrbahn, ausser es lässt sich mangels Bürgersteig nicht vermeiden" brauchbar. Diese Regel ist bei zusammen mit der Fahrbahn gemappten Bürgersteigen leicht einzubauen, da steht ein sidewalk=* bei der Strasse dabei. Bei getrennt gemappten Fusswegen steht diese Eigenschaft beim Fussweg, der Bezug zur Fahrbahn muss erst hergestellt werden.

Umsetzung bei getrennt gemappten Bürgersteigen

Zuerst werden alle Fusswege mit footway=sidewalk gesucht (blau) und mit einem 10-Meter-Puffer (schraffiert) versehen. In diesem Umfeld muss die dazugehörige Strasse liegen.

Dann werden diese Strassen gesucht und markiert (rot). Die Zuordnung ist übrigens keine 1:1-Beziehung sondern eine n:m. Die Büergersteige und die Strassen sind nämlich an unterschiedlichen Stellen unterbrochen, manche Strassen haben mehrere Bürgersteige (oft haben sie mindestens zwei) und manche Bürgersteige sind an Kreuzungen um die Ecke gezogen und folgen dann einer anderen Strasse.

Ausserdem sollte die Strasse ungefähr parallel zum Bürgersteig laufen und nicht z.B. senkrecht auf ihn zu. Da "parallel" bei handgemappten Linienzügen eher nicht so exakt ist, und ausserdem beide Wege nicht auf ihrer gesamten Länge zueinander gehören müssen, wird einfach darauf geprüft, ob die Strasse weiter als 30 Meter innerhalb des 10-Meter-Puffers verläuft. Dadurch fallen auch alle Strassenstücke in Kreuzungsbereichen raus, die kürzer als 30 Meter sind. Kurze Bürgersteige werden somit auch nicht erfasst. Das schadet aber nicht, bei kurzen Strassen bringen zusätzliche virtuelle Querungen auch nur kleine Vorteile.

Dann werden alle paar Meter zusätzliche Wege von der Strasse zu den Bürgersteigen eingezeichnet. Dabei wird von der Strasse ausgegangen. Ginge man von den Bürgersteigen aus, würden sich die Wege zum linken und rechten Bürgersteig nicht an einem gemeinsamen Punkt treffen und das Ergebnis wären Zickzackquerungen, die ein paar Meter auf dem Mittelstreifen verlaufen.

Die ersten paar Meter jedes Wegestücks bleiben frei von virtuellen Querungen. Der erste und letzte Punkt des Weges ist eine Kreuzung oder Abzweigung, wo sowieso häufig eine Querung vorgesehen ist. Oft sogar eine, die der Fussgänger bevorzugt benutzen muss, weil er nicht knapp neben einer Ampel über die Strasse gehen darf.

Da einer Strasse mehrere Bürgersteige zugeordnet sein könnten, können die Verbindungen zu allen Bürgersteigen auch sehr lang werden. Um diese Wege rauszufiltern wird noch einmal auf 10 Meter Entfernung abgeprüft. Dann fallen alle Verbindungen zu Bürgersteige weg, die zu einem anderen Teil der Strasse gehören. Es fallen auch alle Verbindungen weg, wo an einer kurzen Stelle der Bürgersteig einen Bogen von der Fahrbahn weg macht.

Ausserdem wird geprüft, ob diese zusätzlichen Wege auf Hindernisse stossen. "Hindernisse" sind andere Strassen, Gebäude, alle Arten von Barrieren (Zäune, Geländer, Hecken, Mauern...), Bäche und Flächen je nach Geschmack (betretenverbotener Rasen, Gewässer, Büsche...).

Damit man nicht immer zufällig auf ein kleines regelmässiges Hindernis stösst (man legt eine Querung alle 10m und die Gemeinde hat ebenfalls alle 10 Meter einen Grünstreifen angelegt), wird alle 2 Meter getestet, ob eine Querung möglich ist und im Erfolgsfall um 10 weitergesprungen.

Da jetzt die Zuordnung bekannt ist, kann man die Fahrbahnen für Fussgänger sperren, indem man ihnen hohe Kosten zuordnet. Die virtuellen Querungen bekommen ebenfalls etwas höhere Kosten als der normale Fussweg oder ein richtiger gemappter Übergang. Der Router wird dann kleinere Umwege zu einer Ampel akzeptieren.

Ergebnis

Der Router im Bild A entspricht dem derzeit üblichen: Er läuft gerne auf Gehwegen, schliesst aber auch Fahrbahnen nicht aus. Das ist vernünftig weil man zum einen auch oft in der wirklichen Welt auf bürgersteiglose Strassen trifft und zum anderen nicht jeder Bürgersteig in OSM gemappt ist. Da die erste Kreuzung (von Osten nach Süden) für ihn nicht überquerbar ist, schickt er seinen Nutzer erst nach Osten, um ihn dann auf der Fahrbahn zurückzuleiten. Der Nutzer könnte den Trick natürlich durchschauen und gleich über die Strasse gehen. Das kann er allerdings nur, wenn er sich den weiteren Verlauf ansieht und sich nicht nach Osten schicken lässt.

Bild B zeigt einen Router, der Fahrbahnen möglichst meidet und sein Klientel auf Fusswegen durch die Stadt schickt. Da die Fahrbahn als Weg ausfällt, schickt er seinen Nutzer auch erst nach Osten und dann auf einem sicheren Weg weiter.

Bild C ist ein Router, der auch über die Fahrbahn springen kann. Von dieser Fähigkeit macht er einmal Gebrauch, nämlich kurz nach dem Start. Danach meidet er die Fahrbahn, er "weiss" ja, dass daneben ein Fussweg läuft und kann deshalb dieses Stück Strasse im Gegensatz zu bürgersteiglosen Strassenstücken vermeiden. Das Ergebnis entspricht ungefähr Bild A, nur dass das Navi seinem Nutzer die Frustration zu Beginn der Strecke erspart.

Umsetzung bei zusammen mit der Strasse gemappten Bürgersteigen

Die Wegfindung hier ist etwas filigran, deshalb nehme ich lieber kein echtes Beispiel, sondern eine fiktive Situation.

An der linken Kreuzung besteht keine Querungsmöglichkeit von Nord nach Süd. An der rechten Einmündung des Fussweges befindet sich gegenübe eine Bordsteinabsenkung, die bequemes Queren der Strasse ermöglicht.

Das Mapping ist recht schlicht: Drei Wege und zwei Punkte. Der obere Punkt könnte mit highway=crossing und crossing=zebra (oder Alternativen dazu mit crossing_ref=*) eingetragen sein, der untere einfach als highway=crossing, crossing=unmarked und ein paar Zusatzangaben zu kerb=* oder wheelchair=*.Im Folgenden werden diese Querungen gleich behandelt, ein Router kann natürlich in der Gewichtung oder Sperrung bestimmte Arten von Querungen bevorzugen.

Die Strassenstücke liegen bereits an den Kreuzungspunkten aufgetrennt vor. Zu diesen Strassenstücken werden parallele Bürgersteige gezogen, die ein paar Meter kürzer sind als die dazugehörige Strasse. Dadurch zerreissen die Verbindungen und müssen im Folgenden geflickt werden.

Abstand und Kürzung ist hier etwas übertrieben dargestellt. In echt würde man die Abstände natürlich verringern, oder später die Querungen mit einem Knick erzeugen, um die Fussgänger nicht im 45-Grad-Winkel über die Strasse zu schicken.

Zunächst werden die Verbindungen geflickt, die ohne Kreuzung von Strassen auskommen (C-A, B-D, E-F und G-H). Die Verbindung (J-K) schneidet zwar auch einen Weg, allerdings nur einen kleinen Fussweg und gilt deshalb auch als "bestimmt vorhanden". Im Gegensatz dazu gilt die Querung einer richtigen Strasse (C-D) als "eher nicht vorhanden" und wird nicht eingetragen.

Am Kreuzungen wird einfach der Mittelpunkt der Kreuzung (das ist dort, wo der Node in OSM liegt) mit allen beteiligten neu entstandenen Kreuzungsnachbarn verbunden (dadurch entsteht E-Mittelpunkt-K und J-Mittelpunkt-F). Sollte an einer Querung die Strasse nicht aufgetrennt worden sein (das heisst in der Regel, da ist keine Kreuzung), werden einfach die nächstgelegenen Punkte des Bürgersteigs verbunden. So entsteht die X-artige Querung an der rechten Kreuzung und der senkrechte Strich beim Zebrastreifen.

Zusätzlich können an beliebigen Stellen Querungen eingebaut werden, um die "Bürgersteig"-Eigenschaft der virtuellen Wege wieder herzustellen. Ein Seniorenrouter würde darauf verzichten, weil er sich an diesen Stellen nicht auf eine günstige Querungsmöglichkeit verlassen kann.

Eine Sonderstellung nimmt die Verbindung (C-D) ein: Die wird zwar im vorherigen Schritt als "eher nicht vorhanden" bezeichnet, dürfte aber in der Realität als "bestimmt vom Mapper vergessene Kreuzung" gelten. Möglicherweise kann man auch als Default-Wert annehmen, dass ein mit "sidewalk=*" gemappter Weg als durchgehend für den Bürger begehbarer Steig gelten darf, jedenfalls falls die Querstrassen keine allzu grossen Strassen sind. Glücklicherweise kann man diese Wege leicht erkennen und besonders behandeln: Sie befinden sich an den Endpunkten der virtuellen Bürgersteige und sie schneiden zwar eine Strasse, aber nicht die, deren Bürgersteig sie sind. (A-B), (C-G) und (D-H) gehören also nicht zu dieser Art von Verbindungen, da sie ihre eigene Strasse schneiden.

In der Realität sieht das dann so aus: Blau sind die Wege, die sicher vorhanden und begehbar sind. Die gestrichelten lila Wege sind die vermutlich ebenfalls vorhandenen Wege. Die Unterschiede zwischen dem lila Weg am Fussweg und den lila Wegen um die Kreuzung herum ergibt sich später durch unterschiedliche Gewichtungen.

An der Kreuzung links verlieren die gestrichelten Wege in der Praxis ihre Bedeutung. Derart spekulative Wege sollten ja recht hoch bestraft werden, die danebenliegenden "echt gemappten" Querungen dagegen niedrig. Der Router wird diese deshalb bevorzugen.

Ein Seniorenrouter wird die untere Kreuzung nicht auf dem kürzesten Weg queren, wenn er dazu über die südwestliche Strasse muss. Stattdessen wird er lieber drei echte Querungen nehmen.

Ergebnis

Router A macht das übliche Routing an der Strasse. Er weiss nichts von virtuellen Bürgersteigen, bevorzugt höchstens eventuell Strassen mit sidewalk=*, weil er seine Nutzer dort gut aufgehoben weiss. Wo er eine Strasse überquert, ist nicht zu erkennen, das überlässt er dem Nutzer.

Bild B zeigt einen Router, dessen Nutzer besondere Übergänge benötigen. Er kennt die Bürgersteige entlang der Hauptstrasse und verwendet diese. Er kennt auch virtuelle Querungen, nutzt auch ein davon: Der Übergang über die östliche Nebenstrasse ist nicht als besonderer Punkt eingetragen. Diese Übergänge werden allerdings so hoch bestraft, dass er wenn möglich auch einen weiteren Umweg bis zur Ampel in Kauf nimmt. Ganz ohne zusätzliche Querungen auf Basis willkürlicher Annahmen wäre das Routing aber hier nicht möglich der Router würde an der ersten Nebenstrasse scheitern.

C ist der gleiche Router wie B, allerdings wurden hier sämtliche virtuellen Querungen nur mässig mit Strafpunkten bewertet: Ein Meter auf einer virtuellen Querung zählt dreifach. Die Hauptstrasse wird auf einer willkürlichen virtuellen Querung überrquert, allerdings noch vor der Nebenstrasse, um mit möglichst wenigen Querungen auszukommen. Der Umweg zur Ampel ist aber zu weit, um gegen ein paar zusätzliche Strafpunkte zu gewinnen.

Probleme

• Das Hauptproblem sind die Daten... ;)
  • Bei getrennt gemappten Bürgersteigen ist die Idee, diese mit footway=sidewalk zu taggen nicht weit verbreitet. Umgekehrt gibt es erstaunlich viele Wege mit footway=sidewalk durch Park und Wiese, die sich beim besten Willen keiner Strasse zuordnen lassen.
  • Bei an der Strasse gemappten Bürgersteigen fehlen fast immer die Kreuzungsmöglichkeiten. highway=crossing oder crossing=* wird eher bei getrennten Wegen verwendet.

• Die Zuordnung des Bürgersteigs zur Strasse ist bei getrennt gemappten Wegen nicht klar. Die "10-Meter-Regel" passt zwar erstaunlich gut, Kann aber bei Abzweigungen im spitzen Winkel auch uneindeutig werden. An der Strasse gemappten Bürgersteige haben dieses Problem nicht.

• Kreuzungen sind bei beiden Methoden ein Problem. Man möchte dem Router nicht ganz verbieten, auf der Fahrbahn eines z.B. highway=unclassified herumzulaufen. Schliesslich gibt es auch Strassen, die tatsächlich keinen Bürgersteig haben und vielleicht muss der Nutzer des Routers dort wirklich entlanggehen. In Kreuzungsbereichen mit Bürgersteigen aussenrum möchte man die Fussgänger aber nicht auf die Fahrbahn schicken, sondern lieber mit 10-fachem Umweg die paar Meter um die Kreuzung herum. Dummerweise haben die Strassenstückchen in einer Kreuzung oft keinen Bürgersteig, weil sie nur kurze Abbiegespuren in der Mitte der Kreuzung sind und werden deshalb nicht hoch bestraft. Hier bräuchte man eine Zuordnung "Wegeknäul aus Abbiegespuren in der Mitte" zu "Ringförmiges Wegenetz um das Knäul herum".

• Hindernisse sind nicht wirklich ein Problem, der Router kann sich ja aussuchen, ob er seinem Nutzer zumuten möchte, eine Wiese zu durchqueren oder einen Zaun zu überklettern. Allerdings beschäftigen sich Router üblicherweise nicht mit Dingen, die keine "Wege" in ihrer Welt sind.
  • Um Hindernisse zu berücksichtigen, muss der Router für getrennt gemappte Bürgersteige fast sämtliche Objekte in OSM auf diese Eigenschaft prüfen und sich dann doch mit keys wie natural, landuse, building, barrier... beschäftigen. Das kosten Platz und Zeit.
  • Bei an der Strasse gemappten Bürgersteigen besteht dieses Problem nicht. Dafür kann man dort auch keine Hindernisse zwischen Bürgersteig und Strasse mappen...

• gesperrte Nebenstrassen sind auch lästig: Die würden sich eigentlich ganz gut eignen, um zumindest vom Bürgersteig auf die Fahrbahn zu gelangen, oft sogar, diese zu überqueren. Dummerweise sind aber Grundstückszufahrten (z.B. als highway=service access=private) oft auf ihrer ganzen Länge zugangsbeschränkt eingetragen, was vermutlich für das kurze Stück zwischen Bürgersteig und Fahrbahn (tatsächlich sichtbar bei getrennt gemappten Wegen, nur virtuell vorhanden bei zusammen gemappten) nicht gilt. So fallen also gerade die besten Verbindungen zwischen Bürgersteig und Fahrbahn mit abgesenktem Bordstein weg, weil nach Lage der Daten auch dort ein Betretungsverbot gilt.

Ein speziellen Problem bei gemeinsam mit der Strasse gemappten Bürgersteigen ist der weite Interpretationsspielraum beim Einmündungen und Kreuzungen ohne weitere Eigenschaften des Kreuzungspunktes. Das sind die Stellen, wo oben Formulierungen wie "eher nicht vorhandener Weg" oder "vermutlich überquerbare Strasse" verwendet werden.

Im Prinzip sind alle drei Interpretationen der nebenstehenden Abbildung irgendwie korrekt. Vermutlich dürfte es von der Strassenklasse des senkrechten Weges abhängen, ob der Bürgersteig des waagerechten Weges mit ihm verbunden ist. Ein highway=path dürfte ziemlich sicher mit dem Bürgersteig verbunden sein, ein highway=primary vielleicht nicht. Dafür hat der primary sicher eine Verbindung zur Strasse, der path vielleicht nicht. Aus den Daten lässt sich das leider nicht erschliessen und irgendwo zwischen living_street und tertiary haben wir eine Grauzone bei der Abschätzung.

Ein Sportrouter kann das durch unterschiedliche Strafpunkte bei unterschiedlicher Wahrscheinlichkeit ausgleichen. Sollte ein Bürgersteig in der Realität tatsächlich als Sackgasse enden, wird sich dort schnell ein Trampelpfad bilden, über den man vielleicht unbequem aber immerhin weiter kommt. Ein Router mit Rollstuhlfahrern als Zielgruppe braucht klarere Regeln, wenn er seine Nutzer nicht erst an günstigen Querungsmöglichkeiten vorbeirouten will um sie dann am Ende des Gehsteiges ratlos stehen zu lassen.

Ein ähnliches Problem bilden Endstücke: Falls ein Weg mit sidewalk=* endet und ein Weg ohne sidewalk=* weiterführt, könnte dort eine Verbindung zur Strasse sein, oder auch nicht. Wir wissen nicht, ob das der Mapper, der Verkehrsplaner oder der Strassenbauer vergessen hat und können nur raten.

weitere Quellen

Die Bachelorarbeit von Nathanael Lang beschäftigt sich mit Entwicklung eines Datenmodells zur Fußgängernavigation auf Basis von OpenStreetMap-Daten (PDF, 11MB) und arbeitet mit virtuellen Wegen entlang der Straßen. Ausserdem wird dort das Problem der doppelt gemappten Bürgersteige (sowohl als separater Weg als auch als Attribut der Straße) berücksichtigt.