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

Tach auch,

hier gibt’s ein Paper “Shortest Paths in the Plane with Polygonal Obstacles”. Die Abbildungen auf Seite 987 (im Pdf Seite 6) sehen ja schonmal ganz nett aus.

http://www.cs.ubc.ca/labs/theory/thread/papers/short.pdf

Ansonsten:

Ja. :sunglasses:

Edit: Paper falsch zitiert.

Nahmd,

Ist das die Aufgabenstellung?


solve (Ring[] outers, Node[] points, Ring[] obstacles1, Line[] obstacles2, Node[] passages)
returns Line[]

outers          ← definieren die Fläche[n]
points          ← Zugangspunkte auf dem Rand der Fläche, und
                ← zu erreichende POIs im Inneren der Fläche
obstacles       ← flächenhafte und linienhafte Hindernisse
passages        ← Durchgänge durch Linienhindernisse (Gatter im Zaun)

Gruß Wolf

Edit: passages nachgetragen

Im Netz findet man dazu auch einiges unter den Begriffen:

Ob die folgende Implementierung etwas taugt, weiß ich noch nicht. Auf jeden Fall ist da schonmal von Obstacles, Start und Ende-Knoten und Visualisierung die Rede…

So, hab die Hausaufgabe4 mal installiert und laufen lassen. Das Ergebnis sieht dann so aus:

Im Vergleich zu der Liste oben fehlen wahrscheinlich die linienhaften Hindernisse und Durchgänge. Weiß nicht, ob das besonders schwierig ist nachzurüsten.

Nahmd,

Sehr schön, das braucht also nur noch in das Preprozessing für die Routing-Engines eingebaut werden.

Gruß Wolf

Natürlich hätte das geholfen. Der Renderer war mit den neuen Stimmkreisgrenzen irritiert und hat den ganzen Stadtplan damit beschriftet. Die meisten von euch haben es wohl gar nicht bemerkt, weil das nicht flächendeckend war, sondern regional auf Hotspots beschränkt. Da war es katastrophal. Straßen wurden umbenannt (mit der election boundary), Wälder in kleine Parzellen gestückelt und mit Stimmkreisnamen beschriftet. Es ist klar, dass irgendwann auch Renderer das begreifen werden. Hätte man die Ausdrückmöglichkeit einer visibility könnte man solchen Problemen von vorneherein aus dem Weg gehen, weil so etwas nie in normalen Karten erscheint. Es war nur ein Beispiel. Das visibility-Flag würde halt generell überall funktionieren. Nicht dass es zur Regel wird, aber eben für Problemzonen. Es zwingt keinen es umzusetzen, aber es erleichtert Mainstream-Renderern, die Weisheit des Mappers optisch umzusetzen. Am Ende genießt man das OSM-Werk in erster Linie optisch als Karte und nicht durch Lektüre von Datenbank-Dumps. Jemand der Spezialkarten, z.B. der Wahlkreise, oder beliebiger anderer OSM-Objekte erstellt, kann natürlich solche “üblicherweise unsichtbaren” Objekte explizit rendern.

Das Konzept der “virtuellen Wege” halte ich auch für sehr interessant. Die stellen auch unsichtbare “Objekte” dar, die aber lediglich Hilfskonstruktionen sind, um logische Verbindungen von Wegen irgendwie computerbasiert erfassen und verarbeiten zu können. Ich sehe es nicht als Konkurrenz zum Sichtbarkeits-Konzept, sondern als eigenständige Kategorie.

Beides macht Sinn. Virtuelle Wege sind da angezeigt, wo in Wirklichkeit überhaupt nichts in Richtung Weg angedeutet wird. Z.b. große Plätze ohne angedeutete Straßen. Die virtuellen Wege dienen hier lediglich der logischen Verknüpfung von Zugangswegen, damit Router damit arbeiten können. Die Datenstruktur muss eben so ausgelegt sein, dass sie automatisch verarbeitbar ist. Beispielsweise, zwei Gebäude zwischen denen ein Durchgang existiert, aber keine Informationen über Türen/Tore etc. vorhanden sind. Statt irgendwo falsch einen Durchgang hinzusetzen könne man die einfach durch einen logischen Weg verknüpfen. Ein Fußgänger-Route könnte die Information nutzen und Abkürzungen vorschlagen. Es gibt viele große öffentliche Gebäudekomplexe mit Durchgangsmöglichkeiten. Nicht immer kann oder will man da ins Gebäude echte Wege einzeichnen.

Andererseits gibt es viele Fälle in denen Wege real existieren, man sie aber nicht in der Karte sehen will. Beispiel wieder ein Marktplatz, wo schwach angedeutete Wege drübelaufen, z.B. für den Lieferverkehr, z.B. mit abgesenktem Kopfsteinpflaster. Oder der zuvor zitierte Bergpfad, der über eine Holzstapel-Fläche führt. Es ist nur logisch, diese Wege nach traditionellem Konzept zu erfassen. Als Fußweg, Lieferweg, verkehrsberuhigte Straße etc. Nicht nur um dem Router zu helfen, sondern weil es einfach so logisch ist. Trotzdem möchte man oft solche Wege nicht in der Karte sehen. Statt ein Sonderobjekt “virtueller Weg” würde ich hier den normalen Weg bevorzugen, der als “bitte dieses Segment nicht zeichnen” ausgedrückt wird. Es wäre eine saubere Lösung. Was man zuvor gehört hat, dass eine Fläche den sowieso überblenden würde, falls die ID höher ist. Gut, das mag funktionieren, ist aber weder logisch noch elegant.

Zu diesem Themenkomplex fände ich 3 Auszeichnungsmethoden interessant, die man alle unterstützen könnte (sowohl von der Mapper-Seite als auch in der Programmierung der Renderer und Router):

  • der “virtuelle Weg” für Wege die nur der logischen Verknüpfung wegen angelegt werden, um Straßen oder Gebäude/-teile zu vernetzen.
    Das dient in erster Linie Routern um es zu nutzen, Renderern die damit schönere Karten machen, vielleicht anderen …
  • display=yes/no: Sichtbarkeit generell ein/ausschalten, z.B. reale Wege über einen Marktplatz, wo der ortskundige Mapper eine Entscheidungshilfe liefert, dass diese konkreten Wegesegmente im Stadtplan nicht gut aussehen würden
  • active=yes/no: Schalter, um Objekte grundsätzlich deaktivieren zu können.

Deaktivieren mit active=no könnte man so nutzen: z.B. die Stimmkreise/Wahlkreise gelten nur für eine Wahl, sind vielleicht für die nächste Wahl nur geringfügig modifiziert. So könnte man die Objekte in der Datenbank lassen, sagt aber dazu, dass sie momentan nicht aktiv sind. Ähnlich, wenn man auf einer Großbaustelle (z.B. Berliner Stadtschloß) schon einmal die Baupläne in OSM mappt, aber ausdrücken will, dass diese derzeit noch nicht in Anwendungen genutzt werden sollen.

Im Normalfall muss der Mapper keins dieser Tags setzen. Das sind alles Sonderfälle, die aber bei falscher Umsetzung in Karten negativ auffallen würden. Auswertesoftware ist frei, diese “Empfehlungen” der Mapper umzusetzen oder nicht. Im Normalfall wäre es gut, sie zu berücksichtigen (z.B. im Default-Renderer auf der OSM-Homepage). Wenn nicht, braucht man auch nicht über die Mapper zu schimpfen, sondern um die schlechte Umsetzung der Empfehlungen (der Weisheit der Mapper). Natürlich kann i.d.R. der Rendering-Stil die meisten Entscheidungen selbst treffen. Wie eine Autobahn gerendert wird entscheidet er selbst. Es gibt aber immer Sonderfälle, in denen ein Computer keine intelligenten Entscheidungen trifft, wo der Mensch eingreifen muss. Dazu müssen Ausdrucksmöglichkeiten bzw. Entscheidungshilfen in Software vorgesehen werden.

Die typische Situation in Fußgängerzonen und Marktplätzen ist vermutlich nicht so komplex und leichter durch echte oder virtuelle Wege darzustellen. In der Theorie schaut das ganz nett aus, aber ob das auch so direkt umsetzbar ist? Von der Performance her könnte das problematisch werden. Das sind schon deutlich mehr virtuelle Wege als man sonst real in Karten einzeichnet. Das Memory-Limit der Smartphones wird schon jetzt bis an den Rand ausgereizt. Ist auch die Frage ob man das wirklich so exakt routen muss, oder ob der Fußgänger mit einem groben Wegenetz auch den richtigen Weg vom Marktplatz aus in die Ausfallstraße findet.

Damit automatisches Routing funktioniert müssen auch alle Details stimmen. Beispielsweise, wie hängen mehrere nebeneinander gezeichnete Polygone zusammen? Wenn die einzeln begehbar sind, kann man die dann auch queren? Brauchen wir dann doch virtuelle Wege dazwischen? Und dann muss das noch alles konsequent von Mappern umgesetzt werden.

Die Kunst der Kartographie ist doch, Karten gut zu generalisieren und nicht Landschaftsmalerei zu betreiben. Die Kunst des Weglassens. Man könnte natürlich auch noch die ganzen Blumenkübel mappen. Aber irgendwann wird es doch zu unübersichtlich auf einer Karte. Ich finde es gut, dass Wege in Einheitsbreite gerendert werden, die Pfade nur 1 Pixel breit auf dem Smartphone. Nur so kann man übersichtlich zeichnen. Auf dem Smartphone ist die Vektorkarte schon jetzt relativ langsam und teilweise auch unübersichtlich.

Moins,

ich hatte dieses Déjà-vuschon einmal.

Gruß Wolf

Während ich auf Eingebung wartete (die kam inzwischen, danke, ich les die später…), hab ich mal couchmappers Verfahren eingebaut. Testweise mal am Jakobs- und am Sebastiansplatz in München. Das sind zwei benachbarte Flächen, der Sebastiansplatz (rechts) hat kein Hindernis drin und ist nur als Fläche in OSM, Der Jakobsplatz (links) hat zwei Gebäude und ein paar Parkbänke als Hindernisse. Ausserdem hat schon jemand einen Pfad über den Jakobsplatz gelegt.

Der Routinggraph sah so aus:

Zur Vorbereitung sucht man sich alle Ecken dieser Plätze und bricht den vorhandenen Graphen dort auf. Dabei entstehen ein paar Punkte an den Aussenkanten, und noch unsichtbare an den Inneren:

Und dann holt man ein Artillerieregiment, zielt genau auf den kleinen Spatzen, feuert und Dann verbindet man jeden dieser Knoten mit jedem anderen, sofern man dazu die Fläche nicht verlassen muss.

Das ganze wird dann ein bisschen unübersichtlich, die meisten der neu entstandenen Wege sind auch nicht sinnvoll, aber man kann Routen. Und wenn man den Graphen nicht sieht, überzeugt der Vorher-Nachher-Vergleich schon:

In dem Fall hat der Router sogar vorher den Sebastiansplatz gemieden, weil der Weg an der Kante länger war und ist nur einem Stück Hausmauer am Jakobsplatz gefolgt.

Was noch getan werden müsste:

  • Alle nicht sinnvollen Wege wieder rauswerfen, wobei fraglich ist, was davon sinnlos ist. Das Ziel könnte ja auch ein Haus am Platz sein, dann wäre es doof, nur die Zuwege zum Platz zu berücksichtigen.
  • Alle neuen Wege verbinden. So wie es jetzt ist, kann man zwar halbwegs perfekt über den Platz, aber man kann nur schlecht den Platz verlassen. Der Router sucht dann einfach den nächsten Weg am Startpunkt und führt mich zu irgendeiner Kante, wo der Weg halt hinführt. Und erst ab da wird optimiert (in der Hausaufgabe4 ist der Startpunkt auch ein Knoten, aber dazu muss ich schon bei der Vorverarbeitung wissen, wo der Startpunkt ist).
    Aber das ist kein Problem, Kreuzungen zwischen den 698 neuen Wegen gibts genug.

Ich glaube, der Aufwand ist zu hoch für das bisschen Ergebnis, aber andererseits schön routen tut der Router jetzt schon… :wink:

Grüße, Max

**Nachtrag: **

Um zu verdeutlichen, was brute force Algorithmen so anrichten, hab ich das mal für München durchgerechnet, dauert nicht mal eine halbe Stunde.

München besteht derzeit aus 56288 Wegen. Das ergibt fürs Routing 132327 Wegestückchen. Dazu kommen noch 245 Fussgängerzonen, die teilweise ungünstig überquert werden.

Nach der Abkürzungssuche stehen 206674 Wege im Routinggraphen. So schlichte Gebilde wie der Giesinger Bahnhofsplatz, über den man schon vorher gut geroutet wurde, werden dank der vielen Bäume und Parkbänke in ein 7675-kantiges Routingmonster verwandelt. Kompliziertere Flächen wie der Coubertinplatz werden in 14011 Wege zerlegt.

Statt der vorher 132327 müssen jetzt bei jeder Routing-Berechnung 206674 Wege berücksichtigt werden, 56% Zuwachs für 0.5% Fussgängerzonen.

Super Sache, vielen Dank dafür!

Ein paar Gedanken dazu:

  • Parkbänke und Bäume würde ich als Hindernis gar nicht erst beachten, da die räumliche Ausdehnung zu gering ist im Vergleich zu dem zu erwartenden Routingfehler.
  • In der Hausaufgabe4, die ja für Robotersteuerung entworfen wurde, wird allen Hindernissen eine gewisse zusätzliche räumliche Ausdehnung hinzugefügt. Das soll wohl sicherstellen, dass der Roboter überall durchpasst. Nebeneffekt davon ist, dass mehrere eng zusammenliegende Objekte zu einem Objekt zusammengefasst werden und damit die Zahl der Kanten im Graph sinkt. Das kann man auch im Screenshot weiter oben erkennen - jedes Objekt hat dort eine innere Kante (reale Ausdehnung) und eine äußere Kante (für den Roboter künstlich erweiterte Ausdehnung). Im mittleren Teil kann man auch erkennen, wie verschiedene überlappende Außengrenzen behandelt werden.
  • In den Routinggraph würde ich nur das Ergebnis des Dijkstra zwischen allen Andockpunkten der Flächen mit “normalen” Wegen berechnen und den im Routinggraph aufnehmen. Für mehrere Start/Zielknoten müsste man die Kanten wohl auch konsolidieren, um die Zahl der Kanten klein zu halten. Ich denke, es ist nicht ideal, alle möglichen Kanten des Visibility Graphen 1:1 in den Routingraph zu übernehmen.
  • Hershberger (siehe Link oben) rechnet wohl auch nicht alle Kanten brute-force mäßig durch, sondern arbeitet mit Wavefronts. Wie das genau funktioniert habe ich noch nicht wirklich verstanden. Kürzeste Pfade mit mehreren Ausgangspunkten kann man entsprechend diesem Paper auch mit ‘geodesic voronoi diagrams’ lösen (siehe letzte Seite in diesem Paper). Da bin ich aber komplett überfragt.

Edit: typos

Ich hatte das Problem zuvor mal als “unendliche viele Möglichkeiten”, “kombinatorische Explosion” und “Zickzackkurs” beschrieben. Das wurde nicht ganz ernst genommen. Im Prinzip gibt es innerhalb der Fläche unendlich viele mögliche Startpunkte. An jeder Kante kann an unendlich vielen Stellen “reflektiert werden”. So etwa wie “raytracing” bzw. “rayshooting”. Das ist unmöglich brute force berechenbar.

Nun kommt die Vereinfachung ins Spiel: In deinem Beispiel werden Quadrate nur durch 4 Knoten und Kanten dargestellt, was dir nach diesem Algorithmus die Möglichkeit verbaut, optimale Routen zu finden. Und selbst wenn man diese Kanten durch ausreichend viele Knoten approximiert hätte man immer noch unendlich viele potentielle Ausgangspunkte.

Wenn man Wege vorausberechnet, müsste man dann den Platz durch eine Matrix von potentiellen Ausgangspunkten aufteilen und für JEDEN Punkt ein solches Netz virtueller Routingpfade aufstellen und speichern. Das ist unrealistisch.

Du hattest das Problem durch die grobe Quantisierung schon stark vereinfacht (Gebäude 4 Knoten & Kanten). Das ist dann gröberes Zickzack-Routing, kein Vorteil mehr gegenüber wenigen vom Mapper manuell gezeichneten virtuellen Querwegen über den Platz.

Der Rechen- und Speicheraufwand dafür ist riesig. Auf einem Smartphone ist das so nicht machbar.

Der einzige Vorteil der automatischen Lösung: was man da als Möglicheit virtueller Wege für den Mapper andiskutiert hatte, könnte man automatisch vorberechnen lassen. Also nicht im Sinne eines kürzesten Pfades, sondern um überhaupt den Platz automatisch queren zu können. Vielleicht setzt man dann noch einen Knoten pauschal in die Mitte des Platzes, damit Fußgänger auch diesen als Startpunkt des Routers nutzen können.

Das Netz müsste man schon stark ausdünnen, damit Performance in Smartphones möglich ist. Im Prinzip wäre das dann ähnlich, als ob ein Mapper manuell die Querverbindungen anlegen würde.

Manuelle Routen würden auch besser aussehen, weil man die nicht zickzack an Häuserwänden reflektieren würde, sondern straßenmittig verlegt und auf dem Platz kurven legt statt zackig über die Häuserwände routet. Auch wenn das etwas vom kürzesten Pfad abweicht, so würde das aber eher den tatsächlichen Fußwegen entsprechen.

Ist das “wavefront”-Konzept nicht im Prinzip das “raytracing” bzw. “raytracing”, dass ich anfangs mal angesprochen hatte?

Dochdoch, nur her mit dem Code zum Ausdünnen…

Kannst Du ein Beispiel malen, wo es günstiger wäre, ein quadratisches Hindernis durch mehr als seine vier Ecken abzubilden? “Günstiger” im Sinne von “kürzerer Weg”, nicht im Sinne von “da kratzt man sich nicht die Schulter an der Mauer auf” oder “man hat weniger Kurven”. Mehr Knoten zu bauen ist kein Problem, aber ich glaube das bringt nichts. Mehreckige Häuser werden natürlich auch jetzt durch alle Ecken dargestellt (z.B. die Kirche am Preysingplatz).

Auch ne Idee: Einfach ein paar Punkte zufällig verteilen und damit rechnen. Oft nicht optimal, aber immer besser als Randrouting.

Jup, dort wo Wege sind, sind die immer besser als die automatischen. Insbesondere berücksichtigen die auch Dinge, die der Mapper zwar weiss, aber nicht eingetragen hat (z.B. Tische vor Restaurants und Obstläden, oder kreuzende Bus- und Taxispuren auf dem Bahnhofsplatz).

Grüße, Max

Ach stimmt, war nicht zu Ende gedacht. Das bringt ja gar nichts. Wenn man an konvexen Hindernissen herum will ist der Weg an der Wand entlang immer der Kürzeste. Und dazwischen gibt es immer eine kürzeste Gerade von den Ecken aus. Gedanklich war ich immer zu sehr in der Straßen- oder Platzmitte, was natürlich nicht die kürzeste Route ist.

Also ist die Menge der Knoten von Hindernissen und Entry/Exit-Knoten beherrschbar. Falls man nur den besten Querungsweg berechnen will. Fall man von beliebigem Punkt aus auf dem Platz starten will, müsste man für jeden dieser potentiellen Punkte das Netz neu berechnen. Die Komplexität kann man nur eingrenzen, indem diese Freiheit radikal beschnitten wird.

Ich denke der Optimalpfad auf dem Platz ist auch nicht so wichtig. Das wird der Fußgänger schon selbst herausbekommen. Wichtig ist vor allem, dass die Zugangswege vernetzt werden und längere Routen an Plätzen keine Probleme bekommen.

Ich denke, da könnte man durch Beschränkung auf die Eckpunkte der konvexen Hülle des Gebäudes noch Knoten einsparen.

Übrigens vielen Dank für die Bereicherung dieser Diskussion mit deinen Beispielen. :slight_smile:

Moin,
Tordaniks Vorschlag virtual:highway=xyz gefällt mir momentan am besten, den Marktplatz
habe ich jetzt mal dementsprechend getaggt und auch die Bus-Route auf den virtual-way
gelegt (Etwas was bei der automatisch Lösung wohl nicht geht).

So schön es auch is, wenn die Router selbst ihren Weg über Fußgängerzohnen, bzw. allgemein areas, finden, so sehr habe ich Bedenken, dass das resultierende Routing für Menschen wie z.B. Blinde ausreichend wäre. Gerade in Fußgängerzonen mit Straßencafés wäre es sinnvoll, ein Schema wie virtual: zu haben, um eine „gefahrenfreie“ Route durch die Fußgängerzone zu markieren. Das sollte natürlich die Router nicht davon abhalten, über areas routen zu können, ich denke aber, dass wir um ergänzende Hinweise wie z.B. ein virtual: nicht herumkommen werden. Je länger ich hier mitlese und darüber nachdenke, desto besser finde ich virtual: :slight_smile:

Das würde ich als allgemeines Lebensrisiko einstufen. Kann ja auch passieren dass auf der vom Mapper eingetragenen Route plötzlich eine Baugrube, ein Umzugslaster oder sonst was steht. Außerdem muss der Nutzer immer noch mit den Ungenauigkeiten des GPS-Systems leben. Interessant an der ganzen Sache ist, das wie in #68 demonstriert das Routing den tatsächlich kürzeren Weg findet.

Da sieht man natürlich auch, dass im Gegensatz zur Umsetzung durch den Router unnötige Umwege herauskommen, weil sich der Mapper Arbeit sparen und die Daten übersichtlich halten möchte. Oder gibt es wirklich einen Grund, von dem Weg im Westen nicht geradeaus nach Nordosten zu gehen, sondern erst in die Platzmitte zu laufen? Selbst auf den annähernd diagonalen Routen wären bei dir unnötige Knicke drin.

Das bestätigt in dieser Form eher meine Vermutung, dass ein Automatismus mit der Vielzahl der Kombinationsmöglichkeiten deutlich besser zurecht kommt als ein Mapper.

Leider wird virtual:* für Router sehr wohl ein Problem, wenn wir dasselbe Tag aus ganz unterschiedlichen Gründen nutzen:

  • Mapper A trägt damit die optimale Route für Blinde ein

  • Mapper B baut eine Hilfslinie für eine Route, weil er keine Flächen in eine Routenrelation aufnehmen möchte

  • Mapper C will mit seiner Ortskenntnis eine bessere als die von einem eigentlich gut funktionierenden Flächenrouter produzierte Route angeben

  • Mapper D will ein minimales Wegeskelett angeben - nur für einfache Router, die noch kein Flächenrouting haben

Ein Routing mit Flächenfunktionalität für sehende Fußgänger würde ja die virtuellen Wege von Mapper C nutzen wollen, alle anderen jedoch nicht. Dazu muss es sie aber vom Rest unterscheiden können. Wenn wir alle anfangen, unsere eigenen Ideen auf virtual:* zu projizieren, dann ergibt das ein Chaos.

Weil ich es übersichtlich halten wollte. :wink:
Den Umweg von vielleicht 3 m wird man verkraften können, außerdem wird wohl keiner hier exakt nach der Linie
auf seinem Navi laufen.

Ja, die Gefahr besteht durchaus.

Hab ich auch mal getestet… Erst alles berechnen wie gehabt und dann das Zeug wieder löschen, was keine kurzen Strecken zwischen “interessanten” Punkte bildet. “Interessant” sind alle Punkte wo andere Wege den Platz berührten (im Falle des Jakobsplatzes allerdings alle Aussenpunkte, das hat mit der Besonderheit eines Weges mit Tags als outer einer Relation zu tun…)

Bim Jakobsplatz ist der Unterschied nicht so gross, aber immerhin fallen ein paar der Parkbänke im Nordwesten aus dem Graphen, weil sie niemandem im Weg stehen:

Bei trivialen Flächen ist die Einsparung deutlicher (Marstallplatz):

Grüße, Max (der jetzt ein paar Tage nix mehr damit macht)