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 
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 
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
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. 
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.
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.
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.
.oO( “highway=path; trail_visibility=no; area=yes” ) 
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 
) 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 
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?