Fußgängerzone als Fläche - bzw. Routing über Flächen

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.

Was sind denn die Optimalrouten?
http://www.openstreetmap.org/#map=18/51.05894/13.74231

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. :wink:

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.

Hey Leute! Mich würde nun aber wirklich mal interessieren, wer glaubt, dass derartige Berechnung für einen auch noch so modernen Computer tatsächlich in akzeptabler Zeit durchzurechnen sind. Auch Maschinen sind doch nur Menschen :confused: Nein, hat denn jemand schonmal Europa routingfähig gerechnet oder gar das Planetfile? … Ich ja. … und mir wäre an sehr vielen Stellen ein denormalisiertes Datenmodell mit virtuellen Wegen lieber gewesen.

Kommt drauf an, wie man “akzeptabel” definiert :wink:

Für meine 450x340 qkm importiere ich die Daten fürs Routing mittwochs alle 14 Tage. Da braucht der (eher träge, vor allem beim Plattenzugriff) Server einen halben Tag. Den grössten Teil davon, 6-7 Stunden, verbringt er damit, die 4.7 Mio Wege mit Höhendaten zu versehen. Das ist für mich akzeptabel.

Für ein nettes Feature mit Bastelspassfaktor hänge ich da gerne noch 2 oder 3 Stunden dran, Hauptsache er wird bis Mitternacht fertig. Zur Zeit brauche ich 3 Stunden, um die Plätze mit unsinnigen virtuellen Wegen zu vermüllen und dann 6 Stunden, um die unnötigen rauszulöschen. Und dann 10 Minuten, um das Backup wieder einzuspielen, weil ich dabei alles kaputt gemacht habe.

Das ist für mich noch nicht akzeptabel. Allerdings hab ich mich um Performance dabei noch gar nicht gekümmert und der Faktor 2 oder 3 sollte drin sein, wenn man sich ein bisschen Mühe gibt… Ich verwende zur Zeit auch nicht Wolfs Programme, ich glaube, die hätten den Faktor 3 schon eingebaut :wink:

Beim Routen sehe ich auch keine grossen Performance-Einbussen. Wenn ein Platz durch virtuelle Wege die Komplexität einer durchschnittlichen Kreuzung mit zwei Fahrbahnen und ein paar Fuss- und Radwegen erreicht (das werden ja auch schnell mal 20-30 Kanten), muss der Router damit zurechtkommen. Aber auch hier interessiert mich das nicht sonderlich. Ich hab pgrouter als Router gewählt, weil ich eben sowas einbauen können will, nicht weil der so performant routet. Ich warte gerne ne Minute auf eine schöne Route.

Grüße, Max

Nahmd,

Meinst Du mit “derartige Berechnungen” die Erzeugung von synthetischen Wegen zur Verbesserung des Routings über Plätze?

Ich glaube nicht, dass die in vernünftiger Zeit durchzurechnen sind. Sondern ich weiß es. :slight_smile:

Etwas auf Geschwindigkeit getrimmt und ohne teure Objeke wie ArrayList, TreeSet und TreeMap schätze ich den Zeitaufwand für Flächen wie z.B. die Umgebung des Kölner Doms auf ca. 10ms. Das ergibt für die 150k zur Zeit existierenden Highway-Flächen 1500s, also nicht einmal eine halbe Stunde. Die meisten der Flächen sind sehr viel einfacher bis trivial und damit noch schneller durchgerechnet. Dazu ist die Aufgabe beliebig parallelisierbar und eher CPU- als Speicher- oder IO-intensiv. Du kannst mit allen Cores eine Breitseite feuern. Was willst Du mehr?

Gruß Wolf

Ok, das ist keine wirklich große Datenmenge. Jetzt multipliziere das mal mit 10 oder 100.

Ok, das wären dann die Highway-Flächen. Das Problem ist aber generalisierbar. Es gilt doch eigentlich für alle Flächen, also z.B. Wiesen, Acker oder Wälder an denen eine Straße/Weg angrenzt … natürlich getrennt durch einen kleinen fiesen, nicht begradigten Fluss, wo die nächste Brücke irgendwo in 5 km zu finden ist. Das ist nur eins von vielen Beispielen. Wald und Brücke sind natürlich datentechnisch über die 10Gig verstreut - natürlich in diversen Relationen - vielleicht auch noch kaskadiert. Selbst wenn man ohne teure Collection-Objekte auskommt, sind die Grenzen für herkömmliche Rechner schnell erreicht. Das stellt für mich die Machbarkeit infrage und der Hilferuf nach einer objektorientierten OSM-Datenstruktur wird lauter. :wink:

Es geht hier ja um wenige kleine Flächen, die der Mapper explizit als “drüberlaufbar” gekennzeichnet hat, indem er z.B. “highway=pedestrian, area=yes” verwendet hat.

Über ebenfalls explizit als “drüberlaufbare Wiesen und Wälder” gekennzeichnete Flächen könnte man auch reden (und ja, eine so gemappte Wiese mit Bach und einem Brückchen in der Mitte wäre die Krönung…). Aber das werden – halbwegs vernünftiges Mapping vorausgesetzt – auch eher kleine Flächen sein.

Grüße, Max

Nahmd,

Das ist eine Frage der Aufgabenstellung aka Pflichtenheft. Die Lösung von Max bietet maximale Flexibilität als Basis für Experimente. Und mehr als das: die von ihm erzeugten Routen sind oft identisch zu denen, die man händisch entwerfen würde. :slight_smile:

Will man einen Routing-Graph für die ganze Welt erzeugen, geht auch das. Aber auf einem anderen Weg: ich brauche ~20s, um die 2.3M Highway-Elemente inklusive ihrer Geometrien (~23M Punkte) einzulesen. Um die in eine binäre Form zu bringen, schätze ich 10µs je Geometrieelement und 100µs je Way, wobei die letzteren zum größten Teil durch die Umwandlung der Attribute in eine Bitmaske oder eine Geschwindigkeit verbraucht werden. Komplexe Features wie Abbiegebeschränkungen, Vorfahrtsregeln, Bahnübergänge, Öffnungszeiten usw. seinen mal außen vor. Das wären 8 Minuten für die oben angegebene Region.

Die ganze Welt hat ca. 73M Highway-Elemente. Damit komme ich auf 5h für die Erzeugung eines naiven binären Routing-Graphen. Wieviel Zusatzaufwand die komplexen Features machen, kann ich nicht beurteilen; von Routing verstehe ich nur rudimentär wenig. Jedenfalls halte ich die Erzeugung eines Routing-Graphen für die ganze Welt in ½Tag für eine “Berechnung in akzeptabler Zeit”.

Genau das ist der (einzige) Grund, warum mich das Thema interessiert. :slight_smile:

.oO( “highway=path; trail_visibility=no; area=yes” ) :sunglasses:

Und relevant ist hauptsächlich die Anzahl und Komplexität der Hindernisse, weniger die Größe der Fläche. Wenn in der Wildnis nur ein paar Stream und Cliff die Hindernisse bilden, kann die Fläche im Grunde beliebig groß sein, und der Graph aus den synthetischen Wegen wird überschaubar bleiben.

Gruß Wolf

Ich hab noch ein bisschen gespielt und mein gesammeltes Wissen in eine Wiki-Seite geschrieben.

Virtuelle Wege einzutragen geht eigentlich ganz gut, die Rechenzeit ist für mich akzeptabel, 1 bis 2 Sekunden pro Platz (was bei mir heisst, der Import des Routing-Graphen dauert 20% länger), und wenn man die richtig komplizierten Fälle (etwa die Hecken in Ludwigsburg oder das Forum der hundert Treppen) überspringt, kann man das ganze wesentlich beschleunigen.

Ebenfalls deutlich beschleunigen kann man das Rechnen, wenn man seine Hindernisse sorgfältig auswählt. Man muss ja für alles, was so rumsteht überlegen, ob das einen Fussgänger ernsthaft aufhält. Jedes Loch in der Fläche, das dadurch entsteht, vervielfacht den Aufwand.

Ich hab das recht grosszügig betrachtet. Mit "amenity=* bildet jede Telefonzelle, Parkbank und jeder Papierkorb ein Hindernis. Bäume mit natural=tree ebenfalls. Häuser, Denkmäler, Flüsse, Trambahngleise sind auch Hindernisse und natürlich darf der Rasen nicht betreten werden.

Dabei habe ich auch gelernt, wie vielfältig die Welt der Plätze ist, vieles davon bleibt dem Betrachter verborgen, weil die Mapnik-Karte die Dinge entweder gar nicht rendert (amenity=fountain stehen häufig auf Plätzen, aber auch amenity=bicycle_parking können grosse Flächen einnehmen) oder sie unter den priorisierten highway-Flächen versteckt (Wintersportstätten oder Bäche z.B.).

Herzlichen Dank für die Vorschläge hier, besonders an Netzwolf, der interessante Dinge über Winkel erzählt hat (ich habe Tage damit verbracht, das als Unsinn zu entlarven, bevor ichs dann doch eingebaut hab :wink: ) und couchmapper, der Dijkstra zum Löschen unnötiger Wege vorgeschlagen hat.

Der Routing-Graph über den Sebastians- und den Jakobsplatz, den ich oben als Beispiel verwendet habe, sieht übrigens jetzt so aus:

Die dicken blauen Linien sind die bereits gemappten Wege, die dünnen die zusätzlichen virtuellen.

Und wer mal selbst Routen will, kann mit diesem oder diesem Beispiel anfangen (die Geschwindigkeit liegt nicht an den paar tausend virtuellen wegen, das war schon vorher so… und wenns gar nicht geht, liegts daran, dass ich auch grad dran rumbastel…)

Grüße, Max

Nachtrag: Übrigens kann man an allen Plätzen, bei denen schon Wege drüber gemappt wurden, eher wenig Verbesserung durch automatisch eingetragene Wege erzielen. Bei vielen wurden aber einige Nebenstrassen einfach vergessen.

Wenn ich das richtig verstehe, dann kann man sagen: Glückwunsch :slight_smile: Sieht sehr gut aus, auch die Dokumentation im Wiki.

Werde mir das mal genauer anschauen und rumprobieren. Bleibt dann nur zu hoffen, dass dies auch andere Router einbauen oder?