Die Linien, die zu anschlusslosen Ecken der Flächen führen kapiere ich nicht.
Ging es nicht genau darum?
In der unteren Grafik rechts sehe ich keine Linien zu nicht angeschlossen Ecken.
In dem oberen Beispiel Jakobsplatz schon. Hm…
Mal was anderes:
Hat schon jemand drüber nachgedacht, wie die Routinganweisung in solchen Fällen wäre?
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 
Nehmen Sie den vierten virtuellen Weg von links. 
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,
Grüße, Max
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.
Ohne Berücksichtigung der Wegrichtung sollte das wohl eher (n*(n-1))/2 sein, oder? Keine Ahnung, wo da die Fakultät herkommen soll.
Ach stimmt, Fakultät war falsch, hatte wohl multipliziert statt addiert: (N-1)+(N-2)+(N-3)+…+1 ist die Zahl der Wege. N ist die Zahl der Zugangspunte.
Dann gilt die gaußsche Summenformel wie von dir beschrieben.
Die Zahl ist aber auch sehr klein.
Was ich sagen wollte: wie das Verbindungsnetz intern aussieht muss dann für das Drüberrouten gar nicht gespeichert werden. Es reicht, für jede Kombination von entry/exit node einen Metrikwert zu speichern. Die lokale Route am Platz kann ein Smartphone dann immer noch recht schnell vollständig berechnen, in Abhängigkeit vom Standort auf dem Platz (zusätzliche Node im Netz), muss es aber nicht gleichzeitig für alle Plätze auf der Route machen. N ist dann zwar viel größer, nicht die Zahl der Zugangswege, sondern aller Polygonpunkte, aber von der Smartphone-CPU sicher noch beherrschbar.
Letztendlich erfüllt der Node zwischen Fußweg (Linie) und Platz (Fläche) die Funktion einer Kreuzung. Solche Kreuzungen werden doch ohnehin mit einem entsprechenden Tag versehen (sollten sie zu mindestens, oder?)
Davon ausgehend reduziert sich doch die mögliche Wegezahl über diesen Platz auf die möglichen Anschlußpunkte mit dem highway=crossing - Tag?
von Routing keine Ahnung habend und nur so als Gedankenfetzen in den Raum werfend,
Sven
Nö, es ist ein “interessanter Punkt” fürs Routing, aber ein besonderes Tag darf man da nicht erwarten.
Weder beim Eintragen noch beim Auswerten ist so eine Verbindung ein besonderer Punkt, sondern eine ganz normale Verbindung zweier Wege, wie jede andere Einmündung auch. Der Mapper und der Renderer sind zufrieden, weil sie die Verbindung von Weg und Fläche haben. Der Router eigentlich auch, der sieht das als Kreuzungspunkt, von wo aus er den Weg erreichen kann und die Fläche. Letztere bezieht er zumindest mit der “immer an der Wand lang”-Methode in seine Wegfindung ein.
Grüße, Max
Moins,
Diese Anschlusspunkte zu finden, ist ein Schritt bei der Definition der Aufgabe “virtuelle Wege über einen Platz bestimmen”. Sie sind nicht irgendwie markiert, kann kann aber leicht Punkte herraussuchen, die sowohl zur Begrenzung einer Highway=*-Fläche gehören also auch zu einer Highhway-Linie.
Ich hab da mal ein paar SVGs vorbereitet: w31988047, w227012666 und r1633555.
(aus der OSM-Datenbank: Highway-Linien: rot, Highwayflächen: gelb mit blauem Rand, Hindernisse: schwarz; algorithmisch ergänzt: die Anschlusspunkte: blaue Kringel)
Die Aufgabe besteht jetzt darin, (virtuelle) Wege zu ergänzen, über die je zwei der blauen Kringel optimal verbunden sind.
BTW: aneinandergrenzende Flächen sind eine echte Herausforderung: Wenn die Geschwindigkeit auf Nachbarflächen gleich ist, besteht die triviale Lösung darin, die beiden Flächen zu verschmelzen; man muss aber den Fall besonders berücksichtigen, dass mehrere Flächen zusammen einen Ring bilden: nehmen wir eine “^” und eine “V”-förmige Fläche und setzen erstere auf zweitere, so bekommen wir eine “O”-förmige Fläche mit einer Insel darin, es entsteht also ein inner. Das ist nichts Weltbewegendes, man darf es nur nicht übersehen.
Wenn die Flächen unterschiedliches Tagging haben und damit möglicherweise mit unterschiedlichen Geschwingkeiten durchlaufen werden, hängt der optimale Übertrittspunkt auf einer Grenzlinie zwischen zwei Flächen vom Verhältnis der Geschwindingkeiten in den beiden Flächen ab (Schulphysik: Lichtbrechung), und virtuelle Wege müssten für jedes der in Frage kommenden Verhältnisse getrennt berechnet werden. Das ist natürlich Overkill. Wird man nicht machen wollen.
Die einfache Möglichkeit bei benachbarten Flächen ist ein synthetischer Übangspunkt in der Mitte der gemeinsamen Grenze. Das liefert nicht die optimale Routen, funktioniert dafür aber in allen Fällen.
Gruß Wolf
Nahmd,
Das passiert, wenn man alles verbindet, was nicht bei drei auf’m Baum ist.
Aufgabe ist, die rot gekringelten Anschlusspunkte über die Fläche zu verbinden. Die triviale Lösung erzeugt alle lokal sinnvollen Verbindungen, das sind weniger als in obigem Beispiel, aber immer noch zu viel. Die Routing-Engine würde hier bereits die optimale Verbindung finden, aber wegen der enthaltenen überflüssigen Wege Rechenzeit vergeuden. Etwas zeitaufwendig kann man mit einem sehr einfachen Algorithmus die überflüssigen Wege filtern und erhält ein überschaubares Ergebnis, über dass sich Routing-Engine und Nutzer freuen. 
Unbedingt nötig ist das Filtern bei stark strukturierten Gebieten mit wenig Zugängen.
Fies sind einfache Flächen mit vielen Zugängen, denn da bleiben trotz Filtern zu viele Wege über. Der Filter kann keinen Weg mehr tilgen, wenn jeder Weg Teil der optimalen Verbindung zwischen mindestens zwei Anschlusspunkten ist.
Hier ist ein Algorithmus gefragt, dem man Umwege erlaubt in Prozent oder in Metern, und der dann hinreichend geschickt möglichst viele Wege tilgt oder zusammenfasst, ohne den erlaubten Umweg zu überschreiten. Das ist mir aber zu heftig. 
Gruß Wolf
Sollte doch eigentlich reichen, erstmal alle gemeinsamen Punkta als Zugänge zu betrachten (also genau wie bei angrenzenden Wegen). Wenn man wirklich mit langen Teilstücken rechnet, kann man auf denen ja virtuelle Verbindungspunkte einsetzen, wenn sie eine bestimmte Länge überschreiten. Ich denke, so genau, dass man unterschiedliche Geschwindigkeiten betrachtet, müssen wir nicht sein, zumal sich Geschwindigkeiten selten sehr stark unterscheiden dürften für das gleiche Fortbewegungsmittel auf zwei angrenzenden Flächen, die groß genug sind, als dass das wirklich einen Unterschied machen würde.
Vielleicht könnte man auch vor dem Finden der lokalen Verbindungen versuchen, bei Flächen mit vielen Zugängen nah beieinanderliegende Zugänge zunächst mit einem virtuellen Punkt zu verbinden und dann nurnoch diesen zu betrachten. Funktioniert wahrscheinlich nicht besonders gut, wenn man die ganze Sahara als Fläche betrachtet, auf der man routen könnte, aber ich könnte mir vorstellen, dass es für die meisten Fälle tut - und dass für die anderen andere Algorithmen auch nicht unbedingt großartig funktionieren.
Nahmd,
Es sieht reichlich merkwürdig aus, wenn man zu einer Platzecke laufen muss statt über die freie Fläche, um einen Nachbarplatz betreten zu können: daher mein Vorschlag des synthetischen Übergangspunktes in der Mitte der Trennlinie.
Bei den Demo-SVGs mache ich mir’s einfach: ich ignoriere während der Wegsuche die Grenze zwischen benachbarten Plätzen und laufe gerade rüber. Dafür muss man beim Bereitstellen der Daten für den Platzwegsucher darauf achten, dass nicht auf einem Radln erlaubt ist und auf dem anderen nicht.
Oder ein beliebiges anderes Verfahren. Hier hat es beliebig viele Möglichkeiten, dafür aber kein klares Kriterium, wann die Aufgabe gelöst ist. Erinnert an das Plazieren von Labels oder allgemein an kartographisches Generalisieren: schlecht charakterisierte undankbare Probleme. Nicht meine Welt.
Gruß Wolf
Hallo zusammen,
erstmal ein großes Kompliment für das bisher geleistete!
Soviel, wie ich verstanden habe, wurden beim automatischen Routing die “Kontaktpunkte” der an einen Platz anstoßenden Straßen miteinander “virtuell” verbunden (also nicht über tatsächlich vorhandene ways in OSM), um so ein optimales Routing über als area getaggte “Straßen” zu ermöglichen. Wenn ich jetzt keinen Denkfehler mache, funktioniert das auch, wenn bei dem Routing von A nach B diese “area-Straße” (bspw. ein Platz) nur überquert werden muss (also sozusagen eine Zwischenstation ist).
Würde aber dieses Schema auch dann funktionieren, wenn das Ziel selbst auf dem Platz liegt, oder aber das Ziel eine an dem Platz liegende Adresse (ein Haus oder ein Geschäft) ist? Es müssten doch dann nicht nur die Punkt der angrenzenden Straßen miteinander verbunden werden, sondern zusätzlich auch noch die Punkte der jeweiligen Häuser, Geschäfte, Hauseingänge, … ?!
Vom Prinzip her dürfte dieses Problem aber auch die vorgeschlagenen virtuellen Wege (virtual:) betreffen?!
VG,
Thorsten
Nahmd,
Nein, genau das passiert zur Zeit nicht. Es würde aber besseres Routing ermöglichen.
Routing-Engines arbeiten nicht auf Geometrien, sondern auf einem Graphen aus Punkten und abstrakten Abständen zwischen diesen Punkten. Insbesonders kennen Routing-Engines keine Flächen. Bei der Aufbereitung der Daten werden zur Zeit Flächen ebenso wie geschlossene Ringwege behandelt, was dazu führt, dass die Routing-Engine sich einen Weg an der Außengrenze eines Platzes entlang sucht. Der natürlich (viel) länger ist als der wirkliche Weg. Und das führt dazu, dass die Routingengine möglicherweise einen Weg außen herum über Straßen als besser (kürzer/schneller) ansieht und ihn einer Route über den Platz hinweg bevorzugt.
Die virtuellen Wege erlaubten den Routing-Engines besseres Routing über Plätze, ohne dass die Algorithmen der Engines verändert werden müssten.
Auch die Häuser an Straßen sind (meist) nicht an die Straßen angeschlossen. Die Engines selber routen prinzipiell nur von Punkt auf Weg nach Punkt auf Weg. Es ist Aufgabe der Adresseingabe, zu einer Adresse / zu einem Poi diesen Punkt zu finden.
Die virtuellen Wege würden – so von der Adresseingabe berücksichtigt – bessere Start- und Endpunkte für Routen abgeben.
Gruß Wolf
Morsche,
erst mal vielen Dank für die Erläuterung.
Wenn man sich mal das Beispiel “Zeil / Konstablerwacher / Carl-Theodor-Reiffenstein-Platz / Stiftstraße / Hasengasse” in Frankfurt (http://www.openstreetmap.org/#map=18/50.11451/8.68520) anschaut, dürfte das Routingproblem vielleicht noch offensichtlicher werden:
Was haben wir hier? Die Fußgängerzone “Zeil / Konstablerwacher / Carl-Theodor-Reiffenstein-Platz / Stiftstraße / Hasengasse” sind zunächst mal als area=yes getagged. Darüber hinaus gibt es noch div. Verbindungswege, die mit name der jeweiligen Straße erfasst wurden (Stiftstraße, Hasengasse, Zeil, Konstablerwache, Fahrgasse,… Auf der Zeil selbst (also auf der leeren Fläche zwischen den Häuserzeilen) sind div. Gaststätten als einfacher node erfasst, bei denen es tatsächlich um kleine Pavillons handelt, die (noch) nicht als building=yes gezeichnet wurden. Dann haben wir die U- und S-Bahn-Gleise, die unter der Zeil verlaufen, sowie die zugehörigen Bahnhöfe unter der Konstablerwache. Weiter hätten wir noch eine “B-Ebene” (ebenfalls eine Art Fußgängerzone) mit entsprechenden Geschäften, die ebenfalls unter der Konstablerwache ist, die allerdings (noch) nicht erfasst wurden. Sowie die (Roll-)Treppen und Aufzüge, die zur B-Ebene und/oder zu den darunter liegenden U-/S-Bahnhöfen mit den entsprechenden Bahnsteigen (insgesamt 3 bzw. 4 Tiefebenen incl. B-Ebene) führen.
Wenn man dann noch ein evtl. Indoor-Routing bspw. in Einkaufszentren (im Beispiel Zeil wären das in Erster Linie “My-Zeil” und “Zeilgalerie”) hinzuzieht, kommen wir auf etliche Wege, die möglicherweise dann als virtual: ergänzt werden müssten (also z.B. virtuelle Wege zu den Auf-/Abgängen der U-/S-Bahnhöfen, evtl. virtuelle Wege zu den sich auf der Zeil befindlichen Pavillons, ggf. virtuelle Wege in der “Fußgängerzone” der B-Ebene sowie den dazugehörigen Geschäften, …). Und dieses Thema dürfte es in Frankfurt nicht nur einmal geben (ich denke da z.B. auch an die Ecke Zeile/Hauptwache/Fressgass/Alte Oper; Hauptbahnhof; Willi-Brandt-Platz; …); auch in anderen Städten mit Fußgängerzonen und/oder unterirdischen Bahnhöfen, Straßenbahn- und Bushaltestellen, …
Insofern kann aus meiner Sicht die “virtual:-Wege”-Lösung nur eine Übergangslösung darstellen. Für das Routing selbst müssen in der Routing-Engine selbst Lösungen gefunden werden. Hierbei ist aber auch klar, dass diese Lösung nur mit einem “Miteinander” (also OSM und Routing-Hersteller gemeinsam) gefunden werden kann und entsprechende Kompromisse auf beiden Seiten notwendig sind.
VG,
Thorsten
Ich habe mal die Überschrift ergänzt, hat ja zum großen Teil nichts mit meiner Frage mehr zu tun