Parkbänke und Bäume würde ich als Hindernis gar nicht erst beachten, da die räumliche Ausdehnung zu gering ist im Vergleich zu dem zu erwartenden Routingfehler.
In der Hausaufgabe4, die ja für Robotersteuerung entworfen wurde, wird allen Hindernissen eine gewisse zusätzliche räumliche Ausdehnung hinzugefügt. Das soll wohl sicherstellen, dass der Roboter überall durchpasst. Nebeneffekt davon ist, dass mehrere eng zusammenliegende Objekte zu einem Objekt zusammengefasst werden und damit die Zahl der Kanten im Graph sinkt. Das kann man auch im Screenshot weiter oben erkennen - jedes Objekt hat dort eine innere Kante (reale Ausdehnung) und eine äußere Kante (für den Roboter künstlich erweiterte Ausdehnung). Im mittleren Teil kann man auch erkennen, wie verschiedene überlappende Außengrenzen behandelt werden.
In den Routinggraph würde ich nur das Ergebnis des Dijkstra zwischen allen Andockpunkten der Flächen mit “normalen” Wegen berechnen und den im Routinggraph aufnehmen. Für mehrere Start/Zielknoten müsste man die Kanten wohl auch konsolidieren, um die Zahl der Kanten klein zu halten. Ich denke, es ist nicht ideal, alle möglichen Kanten des Visibility Graphen 1:1 in den Routingraph zu übernehmen.
Hershberger (siehe Link oben) rechnet wohl auch nicht alle Kanten brute-force mäßig durch, sondern arbeitet mit Wavefronts. Wie das genau funktioniert habe ich noch nicht wirklich verstanden. Kürzeste Pfade mit mehreren Ausgangspunkten kann man entsprechend diesem Paper auch mit ‘geodesic voronoi diagrams’ lösen (siehe letzte Seite in diesem Paper). Da bin ich aber komplett überfragt.
Ich hatte das Problem zuvor mal als “unendliche viele Möglichkeiten”, “kombinatorische Explosion” und “Zickzackkurs” beschrieben. Das wurde nicht ganz ernst genommen. Im Prinzip gibt es innerhalb der Fläche unendlich viele mögliche Startpunkte. An jeder Kante kann an unendlich vielen Stellen “reflektiert werden”. So etwa wie “raytracing” bzw. “rayshooting”. Das ist unmöglich brute force berechenbar.
Nun kommt die Vereinfachung ins Spiel: In deinem Beispiel werden Quadrate nur durch 4 Knoten und Kanten dargestellt, was dir nach diesem Algorithmus die Möglichkeit verbaut, optimale Routen zu finden. Und selbst wenn man diese Kanten durch ausreichend viele Knoten approximiert hätte man immer noch unendlich viele potentielle Ausgangspunkte.
Wenn man Wege vorausberechnet, müsste man dann den Platz durch eine Matrix von potentiellen Ausgangspunkten aufteilen und für JEDEN Punkt ein solches Netz virtueller Routingpfade aufstellen und speichern. Das ist unrealistisch.
Du hattest das Problem durch die grobe Quantisierung schon stark vereinfacht (Gebäude 4 Knoten & Kanten). Das ist dann gröberes Zickzack-Routing, kein Vorteil mehr gegenüber wenigen vom Mapper manuell gezeichneten virtuellen Querwegen über den Platz.
Der Rechen- und Speicheraufwand dafür ist riesig. Auf einem Smartphone ist das so nicht machbar.
Der einzige Vorteil der automatischen Lösung: was man da als Möglicheit virtueller Wege für den Mapper andiskutiert hatte, könnte man automatisch vorberechnen lassen. Also nicht im Sinne eines kürzesten Pfades, sondern um überhaupt den Platz automatisch queren zu können. Vielleicht setzt man dann noch einen Knoten pauschal in die Mitte des Platzes, damit Fußgänger auch diesen als Startpunkt des Routers nutzen können.
Das Netz müsste man schon stark ausdünnen, damit Performance in Smartphones möglich ist. Im Prinzip wäre das dann ähnlich, als ob ein Mapper manuell die Querverbindungen anlegen würde.
Manuelle Routen würden auch besser aussehen, weil man die nicht zickzack an Häuserwänden reflektieren würde, sondern straßenmittig verlegt und auf dem Platz kurven legt statt zackig über die Häuserwände routet. Auch wenn das etwas vom kürzesten Pfad abweicht, so würde das aber eher den tatsächlichen Fußwegen entsprechen.
Kannst Du ein Beispiel malen, wo es günstiger wäre, ein quadratisches Hindernis durch mehr als seine vier Ecken abzubilden? “Günstiger” im Sinne von “kürzerer Weg”, nicht im Sinne von “da kratzt man sich nicht die Schulter an der Mauer auf” oder “man hat weniger Kurven”. Mehr Knoten zu bauen ist kein Problem, aber ich glaube das bringt nichts. Mehreckige Häuser werden natürlich auch jetzt durch alle Ecken dargestellt (z.B. die Kirche am Preysingplatz).
Auch ne Idee: Einfach ein paar Punkte zufällig verteilen und damit rechnen. Oft nicht optimal, aber immer besser als Randrouting.
Jup, dort wo Wege sind, sind die immer besser als die automatischen. Insbesondere berücksichtigen die auch Dinge, die der Mapper zwar weiss, aber nicht eingetragen hat (z.B. Tische vor Restaurants und Obstläden, oder kreuzende Bus- und Taxispuren auf dem Bahnhofsplatz).
Ach stimmt, war nicht zu Ende gedacht. Das bringt ja gar nichts. Wenn man an konvexen Hindernissen herum will ist der Weg an der Wand entlang immer der Kürzeste. Und dazwischen gibt es immer eine kürzeste Gerade von den Ecken aus. Gedanklich war ich immer zu sehr in der Straßen- oder Platzmitte, was natürlich nicht die kürzeste Route ist.
Also ist die Menge der Knoten von Hindernissen und Entry/Exit-Knoten beherrschbar. Falls man nur den besten Querungsweg berechnen will. Fall man von beliebigem Punkt aus auf dem Platz starten will, müsste man für jeden dieser potentiellen Punkte das Netz neu berechnen. Die Komplexität kann man nur eingrenzen, indem diese Freiheit radikal beschnitten wird.
Ich denke der Optimalpfad auf dem Platz ist auch nicht so wichtig. Das wird der Fußgänger schon selbst herausbekommen. Wichtig ist vor allem, dass die Zugangswege vernetzt werden und längere Routen an Plätzen keine Probleme bekommen.
Moin,
Tordaniks Vorschlag virtual:highway=xyz gefällt mir momentan am besten, den Marktplatz
habe ich jetzt mal dementsprechend getaggt und auch die Bus-Route auf den virtual-way
gelegt (Etwas was bei der automatisch Lösung wohl nicht geht).
So schön es auch is, wenn die Router selbst ihren Weg über Fußgängerzohnen, bzw. allgemein areas, finden, so sehr habe ich Bedenken, dass das resultierende Routing für Menschen wie z.B. Blinde ausreichend wäre. Gerade in Fußgängerzonen mit Straßencafés wäre es sinnvoll, ein Schema wie virtual: zu haben, um eine „gefahrenfreie“ Route durch die Fußgängerzone zu markieren. Das sollte natürlich die Router nicht davon abhalten, über areas routen zu können, ich denke aber, dass wir um ergänzende Hinweise wie z.B. ein virtual: nicht herumkommen werden. Je länger ich hier mitlese und darüber nachdenke, desto besser finde ich virtual:
Das würde ich als allgemeines Lebensrisiko einstufen. Kann ja auch passieren dass auf der vom Mapper eingetragenen Route plötzlich eine Baugrube, ein Umzugslaster oder sonst was steht. Außerdem muss der Nutzer immer noch mit den Ungenauigkeiten des GPS-Systems leben. Interessant an der ganzen Sache ist, das wie in #68 demonstriert das Routing den tatsächlich kürzeren Weg findet.
Da sieht man natürlich auch, dass im Gegensatz zur Umsetzung durch den Router unnötige Umwege herauskommen, weil sich der Mapper Arbeit sparen und die Daten übersichtlich halten möchte. Oder gibt es wirklich einen Grund, von dem Weg im Westen nicht geradeaus nach Nordosten zu gehen, sondern erst in die Platzmitte zu laufen? Selbst auf den annähernd diagonalen Routen wären bei dir unnötige Knicke drin.
Das bestätigt in dieser Form eher meine Vermutung, dass ein Automatismus mit der Vielzahl der Kombinationsmöglichkeiten deutlich besser zurecht kommt als ein Mapper.
Leider wird virtual:* für Router sehr wohl ein Problem, wenn wir dasselbe Tag aus ganz unterschiedlichen Gründen nutzen:
Mapper A trägt damit die optimale Route für Blinde ein
Mapper B baut eine Hilfslinie für eine Route, weil er keine Flächen in eine Routenrelation aufnehmen möchte
Mapper C will mit seiner Ortskenntnis eine bessere als die von einem eigentlich gut funktionierenden Flächenrouter produzierte Route angeben
Mapper D will ein minimales Wegeskelett angeben - nur für einfache Router, die noch kein Flächenrouting haben
Ein Routing mit Flächenfunktionalität für sehende Fußgänger würde ja die virtuellen Wege von Mapper C nutzen wollen, alle anderen jedoch nicht. Dazu muss es sie aber vom Rest unterscheiden können. Wenn wir alle anfangen, unsere eigenen Ideen auf virtual:* zu projizieren, dann ergibt das ein Chaos.
Weil ich es übersichtlich halten wollte.
Den Umweg von vielleicht 3 m wird man verkraften können, außerdem wird wohl keiner hier exakt nach der Linie
auf seinem Navi laufen.
Hab ich auch mal getestet… Erst alles berechnen wie gehabt und dann das Zeug wieder löschen, was keine kurzen Strecken zwischen “interessanten” Punkte bildet. “Interessant” sind alle Punkte wo andere Wege den Platz berührten (im Falle des Jakobsplatzes allerdings alle Aussenpunkte, das hat mit der Besonderheit eines Weges mit Tags als outer einer Relation zu tun…)
Bim Jakobsplatz ist der Unterschied nicht so gross, aber immerhin fallen ein paar der Parkbänke im Nordwesten aus dem Graphen, weil sie niemandem im Weg stehen:
Bei trivialen Flächen ist die Einsparung deutlicher (Marstallplatz):
Grüße, Max (der jetzt ein paar Tage nix mehr damit macht)
Zum Jakobsplatz hat maxbe ja schon geschrieben, dass das “mit der Besonderheit eines Weges mit Tags als outer einer Relation zu tun” hat und bei dem Marstallplatz-Beispiel ist die westliche der beiden Flächen teilweise von einem Gebäude umgeben, was dann als “interessanter Punkt”, “wo andere Wege den Platz berührten” zählt. Oh, und das Marstallplatz-Bild zeigt zweimal die selbe Stelle als vorher/nachher-Vergleich
Kurz zur Erklärung: Ich hatte mal einen schönen Graphen, bevor ich hiermit angefangen hatte. Der wird von osm2po aufgebaut. Das hat mir den Weg 31988047 (highway=pedestrian) eingebaut.
Relationen kann osm2po leider nicht. Die werden nachträglich aus einer osm2pgsql-Datenbank nachgetragen weil osm2pgsql kann das. Allerdings kann das so gut mit Relationen umgehen, dass es die Tags von outer ways auf die Relation überträgt, falls das sinnvoll ist. Die darf man dann kein zweites Mal importieren, weil die outer ja schon abgearbeitet wurden.
Für die Bastelei hier muss ich auf die osm2pgsql-Datenbank zurückgreifen, die kennt Häuser, Bäume und Flächen (kennt ein Router alles nicht, der kennt nur Striche und Knoten). Und wenn ich dann die Kreuzungen des Umringes der Relation 152653 (die dank osm2pgsql inzwischen auch ein highway=pedestrian geworden ist) mit anderen Wegen suche, stolper ich an jedem Eck über den Weg 31988047 im Routinggraphen und markiere den als “Kreuzung zwischen R152653 und W31988047”.
Im echten Betrieb würde man das aus einer Datenbank holen, oder wenigstens aus einer OSM-Datei, die zeitlich zum Import des Graphen passt, oder wenigstens die gleiche Projektion für Flächensuche und Routing verwenden Aber zum Mal-Schnell-Rumprobieren baue ich mir kein solches System auf. Inzwischen ist der Graph auch schon ganz schön buggy durch meine wüst drauflos programmierten Versuche. Ich hab z.B. keine Erklärung dafür, warum in der westlichen Fläche noch ein paar Punkte in der Mitte übrigbleiben (das ist ein Brunnen, der als Hindernis gilt). Ist aber egal, in zwei Wochen gibts wieder einen neuen Routinggraphen,
Wenn ich z.B. eine 10km Route über diese Fläche von meinetwegen 50m Weg berechnen lasse, wie hoch hoch ist denn dann etwa der Rechenaufwand vom Platz im Verhältnis zum Rest der Strecke?
Kann mir das nicht so richtig vorstellen.
Abschätzen kann ich die Rechenzeit nicht, nur die Datenmenge mit bereits gemappten Dingen vergleichen: Die beiden Flächen Jakobs/Sebastiansplatz da oben haben nach dem Ausdünnen zusammen 134 Wege. Das ist so etwa die Größenordnung eines detaillierten Parks (102 Wege) oder 1/3 eines grösseren Friedhofs (449 Wege), oder 1/5 eines Dorfes (697 Wege).
Du übrigens musst nicht mal über den Platz geroutet werden, um davon ausgebremst zu werden. es reicht wenn du in der Nähe bist, der Router muss ja mindestens nachsehen, ob der Weg eine kürzere Strecke bietet.
Im Moment seh ich allerdings nicht mal eine Chance, diese Wege performant genug zu erzeugen…
OsmAnd kann Straßennamen ansagen. Also falls der aktuelle Standort auf einer straßenlosen Fläche liegt, wäre so etwas denkbar: “verlassen Sie den Markusplatz nach Norden in die Calle de la Rizza”. Platzname und Name der Anschlußstraße sind gespeichert.
Das dürfte für den Normalfall reichen. Üblicherweise sind Plätze (Marktplätze) nicht so komplex strukturiert. Das Wichtigste ist die Vernetzung der entry/exit-nodes der Fläche. Mit einer Metrik entsprechend der Linienlänge würde man in den meisten Fällen vernünftige Routen erhalten.
Ein exaktes Routing mit kürzestem Pfad ist mit den hier diskutierten vorausberechneten virtuellen Wegen sowieso nicht möglich. Denn dann müsste man für jeden beliebigen Standort auf dem Platz ein eigenes Netz berechnen und speichern. Das wäre unsinnig und ein Performancekiller. Mann könnte es auch kombinieren: für den lokalen Platz verzichtet der Router auf die Nutzung virtueller Wege und berechnet geometrisch die kürzeste Route vom momentanen Standort zur nächsten Anschlußstraße. Über entfernte Flächen wird vereinfacht mit virtuellen Wegen geroutet, was lokal noch unbedeutsam ist. Die Zahl der Wegekombinationen beim Drüberrouten ist klein, nur (N-1)! bei N Zu-/Abgängen mit jeweils nur einem Kostenfaktor entsprechend der Weglänge.
Für Radfahrer könnte man solche Areas auch komplett auf eine einzige Node schrumpfen, weil die Querungszeit praktisch unbedeutsam ist im Vergleich zu einer längeren Gesamtroute.
