[Talk-de] Routing Fehler A3-B58

[Bernd Raichle]

On Thursday, 25 June 2009 06:16:55 +0200,
Marcus Wolschon <Marcus at Wolschon.biz> writes:
 > 2009/6/24 Bernd Raichle <bernd at dante.de>:
 > > On Wednesday, 24 June 2009 14:44:23 +0200,
 > > marcus.wolschon at googlemail.com <marcus.wolschon at googlemail.com> writes:
 > > > On Wed, 24 Jun 2009 12:50:37 +0200, Claudius <claudius.h at gmx.de> wrote:
 > > > > Am 24.06.2009 12:25, marcus.wolschon at googlemail.com:
 > > > > Du sagst also, dass wir die fuer die Router einfachere Taggingvariante
 > > > > verwenden sollen? Ist die Unterstuetzung fuer Abbiegerelationen denn so
 > > > > schwer?
 > > >
 > > > Ja ist es. Denn das sind Einschraenkungen/Kosten-Funktionen an Knoten
 > > > statt Kanten was die meisten Routing-Algorithmen incl. den beliebten
 > > > Dijstra und A* nicht vorsehen.
 > >
 > > Ist es das wirklich? (Ich meine die _schwere_ Unterstuetzung
 > > ... wegen Knoten statt Kanten ...)
 > >
 > > Wenn man Durchfahrtsbeschraenkungen (wie Einbahnstrasse etc.; fuer
 > > eine Kante geltend) und Abbiegerelationen (wie Linksabbiegen verboten,
 > > nur geradeaus etc.; fuer eine Kantenfolge mit 2 und mehr Kanten
 > > geltend) als Kosten umsetzt, gebe ich dir recht.  Diese Dinge sind
 > > aber _harte_ Ausschlusskriterien, d.h. im Dijkstra sorgen die
 > > Durchfahrtsbeschraenkungen und Abbiegerelationen schon beim Erweitern
 > > des Suchbaums, dass ich diese und jene Kante gar nicht erst als
 > > Folgekante in Betracht ziehe (a la Gewicht=unendlich).  Damit bleibe
 > > ich doch weiterhin kanten-orientiert und verwende die Knoten nur dazu
 > > herauszufinden, welche Kante mit welche verbunden ist.
 > 
 > Du hast Dijkstra nicht verstanden.

Ich habe Dijkstra sehr wohl verstanden ... und mehr als einmal
implementiert.

 > Zu jedem spaeteren Zeitpunkt kannst du eine guenstigere Route
 > bis zum Knoten finden. Dann kommst du aber nachtraeglich
 > aus einer anderen Richtung in die Kreuzung rein.

Klar, ist so.  Und damit das eine verboten und das andere erlaubt ist,
darf man nicht die einzelne Kante ansehen, sondern eine Folge von 2
und mehr Kanten (bei komplizierteren Kreuzungen mit getrennt gemappten
Richtungsfahrbahnen und kleinen Verbindungszwischenkanten kommt man
fuer einen verbotenen U-Turn leicht auf mindestens 3 Kanten).  Die
verbotenenen Kantenfolgen abzulegen und bei der Auswahl der moeglichen
Folgekanten im Dijkstra zu nutzen ist zwar aufwendig, aber doch nicht
so schwer zu implementieren.


[...]
 > > > > Mal abgesehen davon: Was wuerde es denn dem Router bringen, wenn ich den
 > > > > gemeinsamen Abschnitt der Autobahnauf-/abfahrt mit oneway=no taggen
 > > > > wuerde. Er koennte doch immer noch von der Abfahrt auf die Auffahrt
 > > > > routen.
 > > >
 > > > Mein Beispiel war von der Autobahn in die Auffahrt, zurueck bis zur
 > > > Abfahrt und dort wieder auf die Autobahn. Das ist ein ganz anderer Fall.
 > >
 > > ... dann doch lieber ein paar zusaetzliche "oneway=yes" spendieren,
 > > bevor man solch ein Routing-Ergebnis erhaelt ;-)
 > 
 > Es steht dir frei das jederzeit auch explizit zu taggen.

Solange es nicht kompliziert ist, tagge ich Dinge mittlerweile lieber
explizit.  Jede Redundanz in den Daten sorgt dafuer, dass Fehler (wie
falsche Richtungen etc.) angemeckert und somit gefunden werden koennen.

 > Die uralte Diskussion war, dass eine Autobahn-Ausfahrt immer
 > implizit oneway=yes ist weil eben alle oder die meisten Ways
 > davon Einbahnstrassen sind.

"immer" .... "alle oder die meisten" ... zeigt doch schon, dass ich
doch lieber beim expliziten Taggen von so einfachen Dingen bleibe :-).


 > > (Wobei man bei deinem beschriebenen Beispiel dieselbe Kante in
 > > derselben Richtung mehrfach befaehrt, was fast immer unsinnig ist und
 > > nur bei komplizierteren Abbiegebeschraenkungen vorkommen duerfte.)
 > 
 > Das wuerde jedes Mal passieren, wenn man einfach seine Ausfahrt verpasst
 > ohne das implizite oder explizite oneway=yes auf der Ausfahrt/Einfahrt.

Bei einer Routenberechnung _vor_ der Fahrt duerfte dieses Ergebnis
nicht berechnet werden, da die Gesamtkosten bei so einem "Schlenker"
schlechter sind als bei einer korrekten Ausfahrt.

Bei einer Routenfuehreung _wahrend_ der Fahrt ist solch ein Ergebnis
nach einem Re-Routing natuerlich moeglich :-)


Schon vor einiger Zeit gab es die Idee, die "link"-Kanten zu
ueberpruefen, indem man die Richtung und evtl. vorhandene
"oneway"-Tags mit den Ausfahrts-/Auffahrts-Winkel auf die jeweiligen
Autobahn-Kanten vergleicht.  Zu grosse Winkel oder falsche Richtungen
sind Anzeichen, dass da korrigiert werden muss.


Gruss,
  -bernd