vielleicht stelle ich mir das jetzt zu einfach vor (ich möchte keineswegs behaupten, dass “code zu schreiben einfach wäre”), aber am anfang steht doch bei einem routing meist der “kürzeste” weg - das ist immer eine gerade zwischen start- und zielpunkt. dann müsste der router schauen, welche benutzbaren straßen/wege er nehmen kann, um das routing zu ermöglichen. wenn nun einer dieser ermittelten benutzbaren straßen/wege eine area ist, ist auch in diesem fall der kürzeste weg zwischen den “andockpunkten” der an bspw. den platz anschließenden straßen immer eine gerade. wenn nun auf dieser gerade hindernisse auftauchen (gebäude, bänke, bäume, … oder aber auch wenn der platz verwinkelt ist), muss die routingsoftware alternative wege auf diesem platz finden. und da es hier, wie schon diskutiert, theoretisch “unendlich” viele alternativen gibt, kann aus meiner sicht eine lösung nicht mittels in OSM erfassten “virtuellen” Wegen liegen (sonst habe ich hier irgendwann ein “spinnennetz” an virtuellen Wegen, von keiner mehr durchblickt). Die lösung muss also in der routingsoftware selbst liegen. die berechnung der wege muss doch auch immer zur laufzeit des programmes erfolgen - es kann ja durchaus sein, dass sich der benutzer entgegen dem routingvorschlag verhält und die software in abhängigkeit vom aktuellenn standort des nutzers ggf. eine neue route berechnen und vorschlagen muss.
Moin,
ich glaube, hier thoeretisierts Du das Problem zu sehr.
Im Preprocessing kann man eine doch endliche Anzahl von optimalen Wegen zwischen den Anschlusspunkten finden.
Damit gibt sich über den Platz schonmal ein gewisses Netz von “virtuellen” Wegen im Kartenmaterial.
Damit ergibt sich das Problem “beliebiger Punkt auf dem Platz” zu dem üblichen Routing-Problem “finde den nächstgelegenen (vorhandenen) Weg zu diesem Punkt”.
Und hier vertraue ich ganz ehrlich auf den Unterschied zwischen Theorie und Praxis:
In der Theorie sind das unendliche Weiten - in der Praxis aber überschaubare Entfernungen im Meterbereich. (*)
Bereits in einem “praktischen” Netz von optimalen virtuellen Wegen sehe ich da bereits das Problem, dass sich der Router für einen der viel zu eng liegenden Wege entscheiden muss und aufgrund der GPS-Schwankungen viel zu oft “neuberechnet” - wie wäre es da erst bei Deinem “floating” Routing?
Von daher würde ich immer noch von Fall zu Fall ein “generalisiertes Preprocessing der virtuellen Wege von Mapperhand” in Erwägung ziehen.
Auch wenn der automatische Router den menschlichen sicherlich im Prozentbereich schlagen wird. 
Gruß
Georg
(*) Ich gehe hierbei zugegeben von europäischen Plätzen aus - vielleicht liegt da mein Vorurteil …
Solche Späße erlaubt sich auch mein kommerzielles Navi in Belgien und Holland. Offenbar haben sie dort gelegentlich “Feldwege”, die befahren werden dürfen, inklusive Unterboden-Graspolitur. Dummerweise hat das Navi die gemütliche Hauptstraße daneben einfach ignoriert. Wäre wohl einen Tick länger gewesen (aber flotter). Mit den deutschen Straßenkategorien kommt es besser zurecht, obwohl der Kartenhersteller Navteq seine Europazentrale in Eindhoven hat …
Bei der Geschwindigkeit liegt es teils auch am GPS-Chip. Ich denke mein Smartphone hat nicht so einen guten Kalman-Filter und kann schlechter Aussetzer interpolieren als der SIRF vom Navigerät. Dann muss OsmAnd machmal hinterherhinken, wenn die Position teilweise fehlt. Natürlich ist so eine detaillierte Vektorkarte wie OSM auch aufwendig zu rendern. Man könnte den reduzierten Straßenkarten-Modus mal probieren.
Ich hatte bereits den Hybrid vorgeschlagen: Virtuelle Wege nur für den Transit, damit die Gesamtroutenberechnung schnell funktioniert. Und ein Detailrouting auf dem Platz jeweils individuell (inkl. Start/Zielweg auf Platz). Das hat eine geringe Komplexität (der Platz hat weniger Nodes als eine typische Gesamtroute). Das ist doch die einzig sinnvolle Lösung, oder? Mann kann’s auch separat angehen, z.B. die virtuellen Wege weglassen und nur die Platzroute optimieren, oder virtuelle Wege auf Transit ohne Platzrouting. Hängt wohl auch vom Modus ab, was sinnvoll ist. Mit einem Fahrrad hat man Plätze in wenigen Minuten überflogen. Da interessieren keine Details.
Also, irgendwie kann ich der ganzen Diskussion nur bedingt folgen.
Nicht existente Wege einzubauen, egal ob virtuell oder berechnet, ist für mich eine Notlösung / Workaround.
Virtuell (render=false u.a.) ist dabei beinahe noch erträglich - existiert ja schon hier und da.
Das Problem ist doch eher das OSM Datenmodell. Ich kann nicht ganz nachvollziehen, wie man behaupten kann, dass derartige Berechnungen auf modernen Rechner grundsätzlich machbar wären. Vor kurzem hat mich jemand gefragt, ob es möglich sei, eine (Routing-)Topologie für Europa auf einem 2Gig-RAM rechner zu erstellen. Witzigerweise wäre das möglich, ist es auch, jedoch nicht mit den irrwitzigen Relationen, die OSM irgendwann mal eingeführt hat. Die kann man dann getrost ignorieren … fast. Klar sind 2Gig heute nicht mehr StateOfTheArt, aber vor kurzem noch. Alles in eine PostGIS-DB reinzupusten und dann beten, dass der Nachtlauf am nächsten Morgen irgendwas vernünftiges produziert hat, ist ebenso suboptimal. Was bleibt ist die Hoffnung, dass Leute nicht irgendwann auf die Idee kommen einen Weg in zehn nacheinander kaskadierte Relationen zu taggen und ganz unten den Straßennamen zu verewigen. … Tja, dann können wir uns leider nicht beschweren, denn recht hat er … ist ja richtig so, weil technisch möglich und sogar offiziell so dokumentiert - leider - sogar in einem offiziellem Buch … ;-(
Als temporären Kompromiss könnte ich, wie auch schon erwähnt, durchaus leben. Aber so ganz kann ich den Unterschied zwischen “Transitrouting” und “Zielrouting auf einen Platz” noch nicht erkennen. Selbst bei einem Transitrouting habe ich einen (Zwischen-) Startpunkt und einen (Zwischen-) Zielpunkt, der auf dem Platz bzw. am Platz liegt - nämlich der Verbindungsknoten der jeweils angrenzenden Straße.
Ich bin aber auch nach wie vor der Meinung, dass diese virtuellen Wege eigentlich nichts in der OSM-Datenbank zu suchen haben, da diese eigentlich in der realen Welt nicht existent sind. Sollten für das Preprocessing der Routingsoftware tatsächlich solche “virtuellen” Wege benötigt werden, müssten diese aus meiner Sicht im Rahmen der Datenaufbereitung ermittelt und dann im Rahmen der Erstellung der Routingdaten gespeichert werden.
Sofern tatsächlich die “Verbindungswege” zwischen den Andockknoten der angrenzenden Straßen als “virtuelle Wege” in OSM benötigt werden, so muss in jedem Fall ein einheitliches und abgestimmtes Schema her. Es kann z.B. nicht sein (wenn ich bei meinem Lieblingsbeispiel “Zeil in Frankfurt” bleibe), dass sowohl die area-Fußgängerzone, als auch der “virtuelle Weg” mit name=Zeil erfasst werden soll (da dieses dann auch im Zeifel zweimal auf einer Karte angezeigt werden würde).
Bei einfachen (rechteckigen) Plätzen dürften diese ggf. notwendigen virtuellen Wege noch handhabbar sein. Bei komplexeren Plätzen (die z.B. “um die Ecke” gehen) ist die Übersichtlichkeit dann auch wieder schnell hinüber.
Ein weiteres Problem, womit man sich auch beschäftigen müsste wäre, wie man mit angrenzenden Plätzen umgehen soll. Ich hatte hierzu auch bereits mein Lieblingsbeispiel Zeil/Hauptwache/Konstablerwache in Frankfurt genannt. Bei Bedarf kann ich gerne noch weitere Beispiele liefern ;)) Auch sollte klar beschrieben werden, wie z.B. mit “virtuellen Verbindungswegen” zu U-/S-Bahn-Abgängen (Rolltreppe, Aufzüge, …) umgegangen werden soll.
Das Thema ist in der Tat ziemlich komplex. Sicher - bei “normalen deutschen Plätzen” handelt es sich in den meisten Fällen um ein Routing von wenigen hundert Metern. Für ortsfremde oder auch sehbehinderte Nutzer können diese wenigen hundert Meter durchaus ein überwindbares Hindernis darstellen.
Nahmd,
Die Routing-Algorithmen arbeiten auf Graphen aus Knoten und Kanten. Flächen sind nicht vorgesehen, und meine Kristallkugel sagt mir, dass das auch so bleiben wird.
Es ist eine realistische Lösung. Der Zustand zur Zeit ist das “immer-an-der-Wand lang”-Routing.
Die virtuellen Wege erweitern der Routing-Graphen. Nicht mehr, nicht weniger. In der OSM-DB haben die nichts verloren.
Ich bin auf die von Dir programmierte Area-Erweiterung für eine der zur Zeit genutzen Routing-Engines gespannt. 
Die Routing-Engine berechnet keine Wege, sondern stellt aus den in der Routing-Datenbasis enthaltetenen Kanten/Wegsegmenten eine Route zusammen.
Schau Dir den A*-Algorithmus bei Wikipedia an, da siehst Du, wie der auf einem Graphen aus Knoten und Kanten arbeitet. Es gibt auch eine elementare Implementierung aus nur wenigen Zeilen Code.
Man kann. Es sind nur noch zu viele.
Die Lösung der Aufgabe “finde zu einem Punkt in der Fläche einen Punkt im Routing-Graphen” ist bereits jetzt Bestandteil jeder Routing-Software.
Die werden natürlich nicht in die OSM-Datenbank aufgenommen, sondern nur in den Routing-Graphen / die Routing-Daten einer Routing-Engine.
Welche Berechnung? Das Routing selbst? Der Routinggraphen wird durch Routing-Hilfe-Wege auf Areas nur um wenige Prozent wachsen. Oder das Preprocessing? Du hast die Beispiele hier gesehen.
Für Abhängigkeiten zwischen verschiedene Kanten wie z.B. Abbiegebeschränkungen sind Relationen eine einfache und saubere Lösung und auch einfach auszuwerten. Bei der Erzeugung von virtuellen Wegen auf Flächen stellen Löcher (ausgedrückt durch MP) in der Fläche keinerlei Problem da. Welche anderen Relationen haben Auswirkungen auf Routing?
Gruß Wolf
Nahmd,
Wenn der Router den Radler nicht auf Straßen außen um den Platz herum führt, weil der immer-an-der-Wand-lang Weg länger ist als der Weg über die Straßen.
Verbundene Flächen und POIs innerhalb der Fläche sind kein Problem (reinzoomen in die rechte obere Ecke). Sofern sich jemand der Augabe annimmt, die Verbindungswege auszudünnen. 
Gruß Wolf
Ja, davon sind wir bisher ausgegangen. Die Wege entstehen bei der Kartenproduktion. Die routingfähigen Apps wie “OsmAnd” haben ihr eigenes Vektorkartenformat und das wird natürlich für eine hohe Performance strukturiert.
Damit nicht jedesmal die optimale Platzmetrik neu berechnet werden muss, könnten die Optimalrouten natürlich auch in einer OSM-table selbst hinterlegt werden, nicht sichtbar für den Mapper in JOSM. Eine intelligente Datenbank könnte die Neuberechnung dann fallweise antriggern, falls sich die Platz-Polygone und Zugangswege verändert haben. Nur als Idee. Eine Kooperation der OSM-Datenbank ist nicht unbedingt erforderlich.
Transit bedeutet, dass keine Punkte innerhalb des Platzes gespeichert werden. Es wird nur für jede Kombination der Zugangswege (10 virtuelle Wege für 5 Straßenanbindungen) eine Kostenmetrik berechnet (Länge etc.) und als Verbindung gespeichert. Die ganzen Zwischenknoten auf dem Platz werden während der Optimierung natürlich verglichen, aber nur die Kürzeste Route als ein einziger Kostenfaktor gespeichert. Das muss für jeden Platz gemacht werden, aber was sind schon 10 virtuelle Wege pro Platz? Der Speicheraufwand ist minimal. Die Routing-App müsste dafür noch nicht einmal verändert werden, wenn die virtuellen Wege passend in die Routingvektorkarte gespeichert werden.
Der große Vorteil damit ist, dass man die Optimierung nur einmal bei der Kartenproduktion machen muss, nicht während jeder Routen(neu)berechnung. Ansonsten müsste das Handy bei jeder Routenberechnung mehrere Plätze gleichzeitig optimieren. Die Komplexität steigt überproportional mit der Knoten- und Kantenzahl. Das wäre doch etwas viel.
Wenn sich aktueller Standort, Start oder Ziel auf einem Platz befinden, reicht nicht nur ein Kostenfaktor für die Zugangswegekombination, sondern dann muss der komplette Weg auf dem Platz berechnet werden. Jeder Punkt hat ein eigenes Verbindungsnetzwerk. Bei freier GPS-Position auf dem Platz sind das unendlich viele Möglichkeiten. Es versteht sich von selbst, dass so etwas im Handy berechnet werden muss und nicht für alle Plätze pauschal gespeichert werden kann.
Wir haben viele Beispiele für Elemente, die es nicht “gibt”, wie zum Beispiel die Mittelachse eines Flusses.
Streng genommen ist es praktisch unmöglich die Mittelachse eines Feldweges zu bestimmen. Auch Generalisierungsvorschriften, die es zu Anfang des Projektes gab, haben nicht gerade der Realität entsprochen ;).
Daher ist für mich stets der praktische nutzen ausschlaggebend.
Von dem, was ich bisher gelernt habe, wären die Optimalrouten für uns von Vorteil. Also befürworte ich sie.
Um mal kurz zur Ursprungsfrage zurück zu kommen: Braucht man bei Fussgängerzonen wie den Mannheimer Planken, wo eh alle nötigen Wege eingezeichnet sind, wirklich noch die Fläche oder kann die weg?
Bei Plätzen wie dem Berliner Platz oder Plätzen mit z.B. highway=service braucht man allerdings Flächenrouting.
OT: Bei mir am kleinen RAM und an der lahmen CPU bei der Berechnung und beim Rendering.
Gibt’s denn den Quellcode, mit dem du die SVGs erstellt hast? Wäre vielleicht ein guter Ansatzpunkt, wenn man sich daran versuchen will.
Entspricht in Etwa dem, wie ich es selbst machen würde - bis auf einen Fußweg, der in Nichts endete.
Sonst ist wahrscheinlich village green falsch angewendet, wenn ich der ursprünglichen Definition glauben soll. 
Bei der Gelegenheit:
http://map.f4-group.com/#lat=51.0527675&lon=13.7336507&zoom=19&ui.showMenuPage=true&ui.discoveryOpen=false&menuPage.type=search&menuPage.id=Dresden&camera.theta=57.368&camera.phi=151.73
Jemand hat Hochhäuser in Dresden gebaut. Sonst wirklich nette 3D Modelle, vielen Dank!
Ich finde ja. Am südöstlichen Ende ist das eine Fläche mit 20 bis 30m breite und ausgefransten Rändern. Im Umriss steckt mehr Information drin als sich durch einen einfachen Weg (oder ein ganzes Bündel davon) ausdrücken lässt. Gerendert siehts auch hübscher aus…
Aber 20 bis 30m breite Strassen mit nicht ganz regelmässigen Häusern am Rand erfassen wir ja auch nicht als Fläche (bzw nur als “area:highway”=, nicht als highway=).
Jo, weil viele Leute Strassen eher als Striche wahrnehmen (auf Karten, aber auch im echten Leben) und auch im Hinblick auf Routing damit ganz gut zurechtkommen. Andere Dinge wie Tümpel, Rasenflächen, Blumenbeete sehen die meissten eher als Fläche und wollen sie nicht zu Strichen oder Punkten abstrahieren. Fussgängerzonen liegen irgendwo dazwischen, aber der Trend geht anscheinend zu Flächen.
Nahmd,
http://www.openstreetmap.org/#map=18/50.94030/6.95692
Wallrafplatz und Roncalliplatz sind Area-Fußgängerzonen, die Hohestraße (vom Wallrafplatz nach Süden) ist Line-Fußgängerzone. So soll es sein.
Gruß Wolf
Nahmd,
Aufgabenstellung und die Optimalrouten (bei 10% Längenaufschlag für synthetische Wege). Letztere gehören natürlich ausgedünnt.
Nachtrag: auf Vorschlag von maxbe habe ich die Originalwege belassen (dargestellt in rot) und die synthetischen Wege (blau) mit 10% Längenzuschlag bestraft, so dass bei der Bestimmung der optimalen Wege die Originalwege bevorzugt werden.
Die Zahl der synthetischen Wege nimmt mit zunehmender Bestrafung ab: so schaut es bei 20% aus aus; und bei 30% wird es richtig übersichtlich. Von der Übersichtlichkeit bitte nicht täuschen lassen: die Bevorzugung der Originalwege löst nicht das Problem der übergroßen Zahl synthetischer Wege.
Gruß Wolf
Ich finde die Originalwege lassen ein Fußgängerrouting zu. Und etwas Entscheiden sollte der “Mensch” auch können/müssen (wegen der Alz…) .
Warum dort aber highway=pedestrian (statt footway) unter der Fläche highway=pedestrian (M. E. mit MP aus Einzelwegen verkompliziert - nur wegen des “Stadtgrüns”?)) liegt, würde mich interessieren. Dann hängen die Treppen auch nicht im “leeren”. Fast alle, außer Mapnik, lassen die Wege sowieso als Fußweg laufen.
Optimalrouten sind etwas für “Maschinen” - und die können schneller rechnen. Aber soweit sind wir (glücklicherweise) noch nicht.