Die Aufgabenstellung ist, den Routing-Engines Wege über Plätze anzubieten, damit sie sich nicht “immer an der Wand lang” hangeln müssen.
Bereits existierende Wege sind schwer zu berücksichtigen, die habe ich ausgeblendet. Die Ebenen behandelt man jede für sich; U-Bahneingänge, Rolltreppen usw., alles was Ebenen verbindet übernimmt man als POI (schwarz) in die Aufgabenstellung; Indoor-Routing ist kein Thema, solange die Wände in den Gebäuden nicht erfasst sind; ich gehe auch davon aus, dass man inenrhalb von Gebäuden die Flure und Gänge als Wege einzeichnen wird, denn das ist einfacher, als Wände einzuzeichnen.
Die Aufgabenstellung hier gehört zu den weiter oben beschriebenen fiesen, weil es sehr viel Punkte gibt und fast keine Hindernisse: die Lösung enthält deshalb auch nach dem Filtern zu viele Wege. Ohne eine Generalisierung ist die Lösung praktisch nicht einsetzbar. Und die Generalisierung ist eine wirklich unangenehme (und auch undankbare) Aufgabe.
@wegavision: sorry für die Entführung des Threads. Ich höre jetzt auch auf, da ich die benötigte Generalisierung nicht leisten kann.
Vielleicht könnte man recht eng zusammen liegende Punkte (<20m?) zu einem Punkt zusammenfassen und nur damit rechnen (Clustering). Im Frankfurt Beispiel scheint diese Situation ja an einigen Stellen aufzutreten, was die Zahl der Kanten unnötig nach oben treibt.
Auch könnte man als Optimierungsziel die Gesamtlänge aller Wege minimieren, indem man z.B. zusätzliche Punkte einfügt. Jeder der schon einmal einen Interkonti-Flug mit Zubringerflug absolviert hat, kennt bestimmt dieses Hub-and-Spoke Prinzip. Gleiches kenn man auch vom Paketdienstleister, wo das Päckchen von Verteilzentrum zu Verteilzentrum wandert bis es irgendwann einmal beim Empfänger ankommt. Das ist aber leider alles andere als trivial… Haben wir eigentlich schon Winter??
Ich bin mir nicht sicher, ob clustern nicht nur der Optik dient. Ich habe einen Platz, an dem drei Punkte links sind und drei rechts. An der Wand sind die schon vom Polygon verbunden (4 Wege). Dann kommen 9 virtuelle Linien dazu, die die beiden Seiten verbinden:
Bei ungünstigem Clustern spart man sich keine einzige Verbindung, es sieht nur hübscher aus. Der Router hat die gleiche Arbeit mit dem nun aufgeteilten “Interkonti-Flug” quer über den Platz.
Selbst bei optimaler Clusterung hat man noch 11 Verbindungen zu bearbeiten. Erst wenn man es schafft, die zusätzlichen Punkte in die vorhandenen zu legen, oder sich von der Verbindung an der Wand verabschiedet (was vermutlich dumm ist, das ist die einzige, die von einem vernunftbegabten Wesen eingetragen wurde), kann man mehr erreichen.
Bringt ihr hier nicht ein paar Aufgaben durcheinander? Man muss doch 2 Fälle unterscheiden:
Der Platz ist Transit für eine längere Route (“Drüberrouten”). Das könnte durch “virtuelle Wege” zwischen den äußeren Verbindungsknoten in der Routing-Karte gespeichert werden. Dabei reicht ein einziger virtueller Weg für ein Zugangsknoten-Verbindungspaar, der die entsprechende Längen-Metrik und Typ trägt. Nur die müssen gespeichert werden, nicht der Wegverlauf dazwischen. Damit ist die Berechnung einer Optimalroute im Gesamtnetz der Karte möglich.
Start/Ziel oder der aktuelle Standort befindet sich auf dem Platz. Dazu gibt es unendlich viele Möglichkeiten, entsprechend unbegrenzt viele mögliche Routen. Das kann nicht im Vorfeld schon in Routingkarten gespeichert werden. Die Möglichkeiten werden erst handhabbar, passend eingeschränkt, wenn Start/Ziel oder Standort als zusätzlicher Knoten dem Graphen hinzugefügt wird. Das muss der Router vor Ort bzw. anhand einer konkreten Route entscheiden.
Vielleicht finden wir eine Lösung für (1), und für (1a). Letzteres ist der Fall, dass ich zu einem gemappten Punkt auf dem Platz möchte, beispielsweise eine Imbissbude, die frei auf dem Platz steht. Oder ein Treppenabgang zur U-Bahn.
(2) Lässt sich weder durch virtuelle gemappte Wege noch durch automatisiert zusätzlich eingetragene Lösen, da muss jemand einen Router schreiben.
Das ist aber wieder Fall 2, kein Transit, sondern Ziel auf Platz. Ich weiss nicht, ob es sich lohnt für diese Fälle den Platz mit virtuellen Wegen zu versehen. Der Router muss ja auch andere Fälle beherrschen, wo der aktuelle Standort frei auf dem Platz liegt und nicht auf vordefinierten Nodes. Dem Router sollte es zumutbar sein, auf dem Start/Zielplatz selbst zu optimieren. So viele Wege sind es nicht mehr, wenn die Nodes im konkreten Fall fixiert werden. Es wird sowieso ständig eine Neuberechnung fällig, wenn man sich auf dem Platz bewegt. Eine der Nodes ist dann beweglich.
Hat eigentlich jemand praktische Erfahrungen mit dem Routing über solche Plätze?
“OsmAnd” auf Android hat einen Fußgänger-Routing Modus.
Ich hatte es allerdings nur einmal in der Stadt probiert, um eine bestimmte Kneipe zu finden.
Das hat funktioniert. Ansonsten nutze ich massiv parallele neuronale Netze für solche Aufgaben.
Ob OsmAnd auch in Fußgängerzonen funktioniert?
Im Mittelgebirge hatte ich es einmal probiert und da hatte es versagt,
kilometerweite Umwege vorgeschlagen weil bestimmte Schotterwege ignoriert wurden.
Wahrscheinlich genauso gut oder schlecht wie mit den Garmin-Karten: das Routing verwendet nur die Außenkanten der Area. Ein entsprechendes Ticket wurde mit won’t fix geschlossen. Kommentar von Victor: “This is a small glitch (we consider for small areas), but it is very hard to fix technically. Because routing engine doesn’t support routing via areas.”.
Da kann ich Victor verstehen. Das ist eher ein Feature Request als ein Bugfix. Wenn man die Sache richtig angeht, mit allen Problemen wie Flächenfusion etc. kann das schon aufwendig werden. Victor bietet an, Features gegen Spenden zu implementieren. “small glitch” stimmt auch in den meisten Fällen, da man auf den Plätzen sowieso seinen eigenen Weg sucht, abhängig vom Verkehrsaufkommen, Platzierung der Cafeterie-Bestuhlung, Marktständen etc. Wichtig ist vor allem, dass der Platz eine Route nicht verhindert - das Rand-Routing ist dann schon eine vernünftige Notlösung.
Nun, man braucht natürlich genug Motivation, so ein Projekt durchzuziehen. Haben wir Geoinformatiker unter uns? Das wäre eigentlich eine schöne Aufgabenstellung für studentische Arbeiten: Bachelor, Master etc., mit theoretischen Komponenten und einem schönen Erlebnis der praktischen Nutzbarkeit. Der Zeitrahmen könnte für eine solche Arbeit passen und eine Veröffentlichung ist sowieso notwendig.
Gibt es denn schon OpenSource-Lösungen für das Flächenrouting-Problem? Wenn nicht, müsste man das Rad tatsächlich erst erfinden. Dabei sind auch die speziellen Datenstrukturen von OSM zu berücksichtigen. Was macht man z.B. wenn sowohl Flächen als auch Wege dadurch gezeichnet wurden?
Präprocessing von OSM-Daten ist nur sinnvoll für Transit-Routing. Lokal auf dem Platz muss es der Router selbst meistern. Man kann nicht für alle potentiellen Standpunkte (unendlich viele) die Wegenetze berechnen und alles speichern. Das wäre unsinnig. Andererseits wäre es unsinnig, wenn der Router für alle Plätze im Transit jedesmal die kürzeste Platzroute neu berechnen muss (ändert sich nur nach dem Editieren der Karte). Lezteres wäre mit virtuellen Wegen in der Routingkarte eleganter zu lösen. Eigentlich könnte das sogar zentral in OSM gespeichert werden, weil alle Router vor dem gleichen Problem stehen.
Für wäre doch das “Transit-Routing” identisch zum “Routing zu einem Ziel auf dem Platz zu sehen”:
Beim Transitrouting hat der Router ermittelt, dass bspw. der kürzeste Weg von A nach B über den Platz verläuft. D.h. eine Straße ist mit dem Platz verbunden (habe ich also einen “Start-Knoten” (node) ) und wo die ermittelte Route dann auf einer anderen Straße, die ebenfalls an den Platz mit einem Knoten (node) verbunden ist, wäre dann sozusagen der “Ziel-Knoten”.
Wenn sich nun das Routingprogramm eine Route ermittelt, deren Ziel auf dem bzw. an dem Platz liegt, wäre das doch die gleiche Problemstellung, wie wenn das Routingprogramm lediglich eine “Transitroute” über den Platz berechnet.
Insofern (wenn also das Problem des Flächenroutings gelöst ist), könnte man doch eigentlich auf die “virtuell erfassten” Wege komplett verzichten (was dann auch der Übersichtlichkeit dienlich wäre).
In der Hinsicht eine ganz andere Frage: Wie wird denn eigentlich ein “Outdoor-Routing” berechnet, wo es auch keine Straßen/Wege gibt - das wäre doch dann eigentlich genauso, wie das Routing über einen Platz (nur das hier natürlich eine wesentlich größere Fläche zu berücksichtigen ist)?! Klar - beim Outdoor-Routing wird in den meisten Fällen einfach eine Luftlinie berechnet. Aber es gibt doch auch hier Programme, die eine “komfortable” Route berechnen (also z.B. Berge/Schluchten vermeiden) können, oder tatsächlich die kürzeste Strecke (Luftlinie).
Nein, das hat ganz unterschiedliche Komplexität. Für das Transit-Routing sind lediglich alle Kombinationen der Straßen-Anknüpfungspunkte zu berechnen und durch je einen einzigen virtuellen Weg mit Kostenfaktor zu speichern. Das sind nicht viele. Sehr realistisch im aktuellen OSM/Routing-Konzept.
Die Verbindungen zwischen den ganzen Zwischenknoten auf dem Platz sind wesentlich umfangreicher, u.a. die ganzen Kombinationen an Polygonecken und Hauseingängen. Für einen Transit spielt das alles keine Rolle. Das ist nur relevant, wenn man sich bereits auf dem Platz befindet oder wenn man ein Ziel darauf anwählt. Letzterer Fall könnte noch vorausberechnet werden, ersterer nicht, weil der Standort auf dem Platz beliebig sein kann. Falls also die konkrete Wegführung auf dem Platz eine Rolle spielen soll muss das Routing-Programm dort individuell routen.
Also Aufgabe für den Routing-Karten-Produzenten:
Transit-Wege vorausberechnen und speichern. Für jeden Platz auf der Karte ist also die Optimierungsaufgabe zu lösen.
Aufgabe für das Routing-Programm:
virtuelle Wege beim Transit über Platz berücksichtigen, genauso wie die realen Wege (kein Extraaufwand)
Bei Wahl eines Start/Zielpunktes auf einem Platz jeweils abhängig davon eine Optimalroute finden (Flächenrouting nur dort)
beim aktuellen Standort auf einem Platz die Route dynamisch neuberechnen
Die Rechenlast für das Routing-Programm ist beherrschbar, für die Start/Zieleingabe jeweils nur 1x eine Optimierung
und dynamisch jeweils nur für den aktuellen Platz. Müsste es auch für die ganzen Transitflächen noch Optimalrouten finden
könnte es aufwendig werden. Im Voraus weiss man ja noch gar nicht, ob ein Platz überhaupt Teil der Route ist.
Wenn man dann alle möglichen Flächen in der näheren Umgebung gleich mitoptimieren müsste …
Da sind die virtuellen Wege doch praktischer.
“Neu erfundene” virtuelle Routing Tags existieren eh bereits rudimentär, z.B. für den Sylt-Shuttle
OSM-Daten sind per se schon grottig genug, was die Interpretierbarkeit für Router betrifft.
Router benötigen gewichtetete Kanten, also Ways. Alles andere ist Unfug und nur mit massivem Preprocessing-Aufwand zu beseitigen. Für Städte mag das ja noch gehen, für Länder und Kontinente wäre das ein klares ko-Kriterium. Da kann man gleich das Rechenzentrum von Google mieten.
Zur Laufzeit einer Routenberechnung geht eine Polygon-Interpretation schon mal gar nicht - wäre viel zu lahm.
Meine Meinung:
OSM sollte seiner Linie treu bleiben und nicht ständig neue Dinge erfinden - gibt schon zu viele alternative Tagging-Optionen für ein und die selbe Geschichte. Wir Deutschen lieben sowas ja, doch ob die restliche OSM-Welt da noch Lust zu hat, …, und dem folgt, …, hab da so meine Zweifel.
OSM dient unterschiedlichen Zielgruppen. Das hübsche Malen von Karten und die Darstellung der optischen Realität ist dabei eine von vielen. Routing und GeoCoding sind da schon wieder eine völlig andere Nummer. Hier benötigt man eindeutig lokalisierbare Anker, von mir aus auch virtuelle, die man finden und verbinden kann. Auch der Vorschlag Dinge über einen “Snapping-Radius” als zugehörig/zusammenhängend zu interpretieren führt allzu oft zu komischen Ergebnissen.
Um OSM einigermaßen korrekt zu routen, kann man sich nur auf die NodeIDs als Links verlassen.
Wenn ich also zum Bäcker in der Fuzo fuß-routen möchte, dann erwarte ich, dass es einen idealisierten Weg daran gibt. Per GeoCoding krieg ich die Koordinate vom Bäcker und kann dann eine sehr schnelle Lotfuß-Berechnung lostreten. Ich denke, so funktionieren die meisten Router.
Was mich immer wieder ärgert sind übrigens Routing-Apps und -Programme, die OSM-Material aus den o.g. Gründen schlecht berechnen und dann periodisch “vernünftiges” Kartenmaterial zum Kauf anbieten.
Das hat sicher einen guten Grund ;-(
Weil die Router nur entlang Kanten routen, sind Wege über Flächen wegen des “immer an der Wand lang” Routings im Routing-Ergebnis manchmal länger als in der Realität längere Wege über Straßen, die die Fläche umgehen. Das führt zu überraschenden Routings. Und das kann man verbessern, natürlich ohne den OSM-Datenbestand aufzublasen und ohne in den eigentlichen Router einzugreifen.
Die Grundidee bestand darin, zwischen dem Auslesen der OSM-Daten und dem Preprozessing der Router-Software (möglichst wenig) [virtuelle] Wege einzufügen, die das Routing-Ergebnis verbessern, ohne die Last signifikant zu erhöhen.
Wir finden bereits die Minimalzahl von Wegen, die zu einem optimalen Routingergebnis führt. Soweit ist das Problem gelöst.
Leider sind das oft zu viele, und man müsste ausdünnen: und das kann man auch, weil zum Erreichen des Zieles überhaupt nicht nötig ist, die optimalen Routen über den Platz anzubieten. Es reichen hinreichend gute, und hinreichend bedeutet hier, dass man günstiger wird als der Weg außenherum. Leider ist die Reduktion von den (zu vielen) “optimalen” Wegen auf eine kleine Menge “notwendiger/hinreichender” Wege nicht trivial.
Das ist nicht richtig: Ich kann leicht die Ergänzugsways zu allen 150.000 highway-Flächen weltweit bereitstellen. Z.B. als “osmdiff”, so dass man die in der Verarbeitungspipe irgendwo mit einfließen lassen kann. Aber eben nur die Optimalen, und nicht einen sinnvoll ausgedünnten Satz.
[×] Zustimmung.
Ja natürlich.
Dass aber aus der Überlegung, wie man mit überschaubarem Aufwand einen Router dazu bringt, Flächen zu nutzen statt sie zu umgehen, die Forderung wird, zentimetergenaues Routing um die Tische der Außengastronomie herum zu jedem POI am Randes des Platzes bereitzustellen, ist für Diskussionen hier völlig normal und auch nicht schlimm.
Es liegt einfach daran, dass es einfacher ist, Visionen zu haben, als eine einzige Zeile Code zu schreiben. Und dass Visionen umso größer werden, je weniger Kenntnisse der Realität sie behindern.
Zur Laufzeit muss nur der aktuelle Platz optimiert werden, auf dem man sich befindet. Das sind alle Karten-Nodes und Polygonkanten plus eine Node des aktuellen Standorts. Einfaches Graphenproblem, ohne Raytracing. Im Zeitalter von GHz-CPU ist das doch kein Problem oder?
Alle Plätze im Transit können durch wenige virtuelle Wege vollkommen optimal repräsentiert werden, genau gesagt (n*(n-1))/2 beidseitig nutzbare bzw. ein paar Extras bei Einbahnstraßen. Das wären für einen typischen Marktplatz mit 5 Zugangswegen nur 10 virtuelle Wege dazwischen. Ist das ein Problem? So häufig sind die Plätze auch wieder nicht. Routing-Karten bei OsmAnd gibt es Bundesländer-weise, nicht als Planet-File. Der Rechenaufwand dürfte sich in Grenzen halten. Außerdem ist es dann nicht Aufgabe der OSM-Community, sondern des Routingkarten-Erzeugungsprogramms, vollautomatisch.
Also, für Fußgänger wäre das schon ein nettes Feature, mit relativ wenig Rechenaufwand machbar. Muss nur jemand Zeit zum Programmieren haben …
Wie gesagt, eine schöne studentische Arbeit für die betreffenden Fachbereiche. Die müssen sich sowieso immer neue Themen ausdenken. In einer Masterarbeit will man i.d.R. etwas Neuartiges entwickeln und ist zur Publikation verpflichtet. Sehr viel guter Sourcecode ist bei solchen Arbeiten entstanden.
Das kann man so pauschal nicht sagen. Ich halte es zwar auch für sehr wichtig, Datenfelder möglichst exakt zu definieren und wenig Interpretationsspielräume zu lassen (z.B. max-speed nicht einmal als km/h und einmal als miles-per-hour ins gleiche Datenfeld ohne Einheitenangabe zu schreiben), aber die Praxis zeigt, dass Routing auf OSM durchaus gut funktionieren kann.
Ich hatte mir den Spaß erlaubt, gelegentlich neben meinem kommerziellen Auto-Navigator noch “OsmAnd” mitlaufen zu lassen. Die Anweisungen kommen dann quasi in Stereo. Erstaunlicherweise sind die beiden sich in den meisten Fällen einig gewesen. Dumme Fehler haben sich beide erlaubt. Manchmal war OSM auch besser. Der Fahrspurassistent ist im kommerziellen Navi besser. In manchen Innenstädten hat mich OSM gelegentlich komplett in die Irre geführt (bzw. ich hab’s eine Zeitlang beobachtet bis ich das Ding ignoriert hatte und meinen eigenen Weg gefahren bin). Man beurteilt die Routing-Qualität auch gerne nach solchenen eher seltenen Aussetzern. Da kann 99% der Route vollkommen Ok sein. Wenn das Ding einen aber einmal kreuz- und quer durch die City irreführt merkt man sich das.
Vielleicht ist Software denkbar, die derartige seltenen Fehler automatisch erkennt. In dem Sinne ist es vielleicht auch gut, wenn das OSM-Material von kommerziellen Anbietern herangezogen wird, wenn sie mithelfen, solche Fehler zu beseitigen.
Mir fallen jetzt spontan zwei grössere Fehler ein, die ich dabei erlebt habe: 1.: OsmAnd routet teilweise über Feldwege, 2.: das “kommerzielle Navi” routet teilweise über dauerhaft gesperrte Strassen und kennt einige Dinge nicht. Ansonsten ist OsmAnd oft etwas besser (besonders innerstädtisch), allerdings (teils deutlich) langsamer, an Kreuzungen an denen Fahrspuren als eigene Strassen gemappt wurden etwas verwirrend…
…und da muss ich dir leider zustimmen. Die Abwahl von Autobahnen klappt “drüben” auch besser (ist nicht so zwanghaft).
Code schreiben ist gar nicht so schwer, nur funktionieren tut es danach nicht immer
