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

DoDoMR · 2013-11-18 20:22:07

openzzz wrote:

DoDoMR wrote:
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
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.

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.

Netzwolf · 2013-11-18 21:24:10

Nahmd,

DoDoMR wrote:

[…] 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.

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.

kann aus meiner sicht eine lösung nicht mittels in OSM erfassten "virtuellen" Wegen liegen

Es ist eine realistische Lösung. Der Zustand zur Zeit ist das “immer-an-der-Wand lang”-Routing.

(sonst habe ich hier irgendwann ein "spinnennetz" an virtuellen Wegen, von keiner mehr durchblickt).

Die virtuellen Wege erweitern der Routing-Graphen. Nicht mehr, nicht weniger. In der OSM-DB haben die nichts verloren.

Die lösung muss also in der routingsoftware selbst liegen.

Ich bin auf die von Dir programmierte Area-Erweiterung für eine der zur Zeit genutzen Routing-Engines gespannt.

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.

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.

GeorgFausB wrote:

Im Preprocessing kann man eine doch endliche Anzahl von optimalen Wegen zwischen den Anschlusspunkten finden.

Man kann. Es sind nur noch zu viele.

Damit ergibt sich das Problem "beliebiger Punkt auf dem Platz" zu dem üblichen Routing-Problem "finde den nächstgelegenen (vorhandenen) Weg zu diesem Punkt".

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.

pimapper wrote:

Nicht existente Wege einzubauen, egal ob virtuell oder berechnet, ist für mich eine Notlösung / Workaround.

Die werden natürlich nicht in die OSM-Datenbank aufgenommen, sondern nur in den Routing-Graphen / die Routing-Daten einer Routing-Engine.

Ich kann nicht ganz nachvollziehen, wie man behaupten kann, dass derartige Berechnungen auf modernen Rechner grundsätzlich machbar wären.

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.

jedoch nicht mit den irrwitzigen Relationen, die OSM irgendwann mal eingeführt hat.

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

Netzwolf · 2013-11-18 21:39:25

Nahmd,

DoDoMR wrote:

Mit einem Fahrrad hat man Plätze in wenigen Minuten überflogen. Da interessieren keine Details.

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.

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.

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

openzzz · 2013-11-19 00:57:06

DoDoMR wrote:

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.

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.

DoDoMR wrote:

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.

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.

marek kleciak · 2013-11-19 01:15:24

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.

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.

rayquaza · 2013-11-19 02:23:34

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.

openzzz wrote:

Bei der Geschwindigkeit liegt es teils auch am GPS-Chip.

OT: Bei mir am kleinen RAM und an der lahmen CPU bei der Berechnung und beim Rendering.

errt · 2013-11-19 08:14:00

Netzwolf wrote:

Sofern sich jemand der Augabe annimmt, die Verbindungswege auszudünnen.

Gibt's denn den Quellcode, mit dem du die SVGs erstellt hast? Wäre vielleicht ein guter Ansatzpunkt, wenn man sich daran versuchen will.

viw · 2013-11-19 09:26:48

marek kleciak wrote:

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.

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

marek kleciak · 2013-11-19 09:47:36

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 … phi=151.73
Jemand hat Hochhäuser in Dresden gebaut. Sonst wirklich nette 3D Modelle, vielen Dank!

Last edited by marek kleciak (2013-11-19 09:53:41)

maxbe · 2013-11-19 09:59:48

rayquaza wrote:

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?

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

rayquaza · 2013-11-19 10:14:03

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=*).

maxbe · 2013-11-19 10:50:00

rayquaza wrote:

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.

Netzwolf · 2013-11-19 12:20:17

Nahmd,

rayquaza wrote:

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?

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

Netzwolf · 2013-11-19 12:46:39

Nahmd,

viw wrote:

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

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

Last edited by Netzwolf (2013-11-19 15:47:33)

geri-oc · 2013-11-19 15:19:25

Netzwolf wrote:

...
Aufgabenstellung und die Optimalrouten. 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.
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.

pimapper · 2013-11-19 20:47:06

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.

maxbe · 2013-11-19 21:41:42

pimapper wrote:

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.

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

Netzwolf · 2013-11-19 21:43:38

Nahmd,

pimapper wrote:

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.

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

pimapper · 2013-11-20 09:32:29

maxbe wrote:

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.

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

Netzwolf wrote:

Das ergibt für die 150k zur Zeit existierenden Highway-Flächen 1500s, also nicht einmal eine halbe Stunde

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. ;-)

Last edited by pimapper (2013-11-20 09:46:50)

maxbe · 2013-11-20 10:44:22

pimapper wrote:

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.

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

Last edited by maxbe (2013-11-20 10:48:40)

Netzwolf · 2013-11-20 11:40:49

Nahmd,

pimapper wrote:

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

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”.

pimapper wrote:

[…] 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.

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

maxbe wrote:

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...).

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

Aber das werden -- halbwegs vernünftiges Mapping vorausgesetzt -- auch eher kleine Flächen sein.

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

maxbe · 2013-12-14 01:34:37

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.

Last edited by maxbe (2013-12-14 12:09:58)

Schina02 · 2013-12-14 18:41:04

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?

Announcement

#126 2013-11-18 20:22:07

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

#127 2013-11-18 21:24:10

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

#128 2013-11-18 21:39:25

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

#129 2013-11-19 00:57:06

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

#130 2013-11-19 01:15:24

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

#131 2013-11-19 02:23:34

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

#132 2013-11-19 08:14:00

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

#133 2013-11-19 09:26:48

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

#134 2013-11-19 09:47:36

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

#135 2013-11-19 09:59:48

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

#136 2013-11-19 10:14:03

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

#137 2013-11-19 10:50:00

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

#138 2013-11-19 12:20:17

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

#139 2013-11-19 12:46:39

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

#140 2013-11-19 15:19:25

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

#141 2013-11-19 20:47:06

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

#142 2013-11-19 21:41:42

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

#143 2013-11-19 21:43:38

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

#144 2013-11-20 09:32:29

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

#145 2013-11-20 10:44:22

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

#146 2013-11-20 11:40:49

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

#147 2013-12-14 01:34:37

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

#148 2013-12-14 18:41:04

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

Board footer