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

Ich hab mal eine Karte mit flächigen Fusswegen in meiner Gegend gemacht, nur um mal ein Gefühl dafür zu kriegen, wie das Problem aussieht. Geduldige Menschen finden sie hier. Noch geduldigere können auch einen Layer mit einem herkömlichen Routing-Graphen anzeigen, der kommt inzwischen sogar mit Relationen zurecht (manchmal zumindest…).

Aus den Flächen wurden bisher nur Gebäude, Wasser, Bäume (Standardbäume erzeugen 2x2m-Löcher) und Parkbänke (1x1m) ausgeschnitten (1). Und natürlich alle Flächen, die schon der Mapper rausgenommen hat.
Einige Fussgängerzonen zeigen wie wichtig eine Lösung wäre. Bei den wirklich bizarren Umrissen wurden aber oft schon hilfreiche Wege durch die Fläche eingetragen.

Grüße, Max

Edit: (1) Strichförmige Hindernisse (Hecken, Mauern…) sind noch Gegenstand intensiver Überlegungen.

Nahmd,

Sehr schön.

Lässt sich das (mit vernünftigem Aufwand) noch um die Anschlusspunkte erweitern, also die Stellen, wo Wege anschließen?

Gruß Wolf

OT: Bizarr sind an der Stelle nur die Gebäude. Wenn die und ein paar Gebäude weiter nördlich ordentlich in 3d dargestellt werden, kann das 3d mapping als weitgehend ausgereift gelten. 3dr:type=8.7, angedacht ist es also durchaus.

Baßtölpel

Erst dachte ich, “Ja”, aber nach dem ersten Versuch… “Nein, eher nicht”. Wege und Flächen schneiden sich nämlich gelegentlich mehrmals. Manchmal sogar richtig oft, falls ein Weg eine Begrenzung eines Multipolygons ist… Mal sehn…

Nahmd,

Mein Ok für 3D gibts erst, wenn der Kölner Dom ordentlich wiedergegeben wird. :stuck_out_tongue:

Gruß Wolf

alos ich trage das ein damit es besser aussieht

UND

manche die immer wieder schreiben <<<wir arbeiten nicht für die Renderer.>>> achten mehr bei anderen darauf wie bei sich selbst.
und mal ganz unter uns beiden, wen stört es denn wenn man in der Karte auch mal was angezeigt bekommt :sunglasses:

So funktioniert aber rendern nicht. Der Renderer möchte das Objekt so gut wie möglich beschrieben haben und an Hand dessen malt er es oder eben nicht. Dein allgemeines “visible=no” hilft da dem Renderer überhaupt nichts. Das sagt ihm nur, dass da draußen mindestens ein Mapper ist, der der Meinung ist, das Objekt ist unsichtbar. Es verrät aber nicht den Grund. Wenn der Grund ohnehin schon anderweitig getaggt ist, braucht der Renderer auch kein zusätzliches “visible=no”. :wink:

Automatische Lösungen des Routers sind immer (aktueller Erfassungsgrad) Ratespiele. Das kann gut gehen, kann aber auch in einer Route durch die Kirche in der Platzmitte führen. Der Mapper kann sagen: So-Fr kann man am besten direkt über den Marktplatz gehen, Sa ist Markt, da muss man einen Bogen machen.

Den Druck auf die Router gibt es ja nun auch schon seit vielen Jahren mit dem bekannten Resultat: Wer “gutes” Routing will, zeichnet einfach highways drüber und fertig.

Sehe ich auch so.

Hier meine Überlegungen zu dieser etwas theoretischen Diskussion :wink:

  1. Virtuelle (oder sonstige) Ways über Flächen helfen bei der Bildung von einfachen Relationen. Daher werden sie immer wieder gemappt werden. Siehe http://www.openstreetmap.org/browse/way/23113737

  2. Dem Router kann es egal sein, ob die Fläche auch mit einzelnen Ways zusätzlich gemappt ist. Er kann unabhängig davon einen kürzeren Weg über die Fläche suchen.

  3. Der Renderer kann sich raussuchen, ob er Wege, die auf/unter einer Fläche liegen nicht darstellt. Im einfachsten Fall malt er einfach die Fläche zuletzt. Man darf nämlich nicht vergessen, dass nicht jeder Anwender ein Computer-Vollprofi ist. Die Wege über der Fläche müssten halt nur am Flächenrand anfangen und enden.

  4. Hier: http://www.openstreetmap.org/#map=19/49.40725/11.14525 kann man eine kreativen Umgang des Renderers sehen. Die Fläche wird je nach Zoomstufe als Fläche oder als turning_circle dargestellt. Hier: http://osm.org/go/0D63P46u4 wird es für den Router schwierig zu erkennen, dass man da umdrehen kann.

  5. KISS. Die Daten sollten nicht nur von Vollprofis genutzt werden können. Wie mache ich eine “Drahtgitter-Karte” von Wegebeziehungen oder eine einfache Darstellung eines Wegenetzes? Siehe Punkt 1, dargestellt als “Radfahrerkarte”.

  6. Wie mappe ich eine Fußgängerzone, auf der es nur eine Fahrspur auf den Platz gibt, die für den Lieferverkehr/Fahrradverkehr freigegeben ist (und diese natürlich auch Fußgängerzone ist)? Doch nicht als zwei Flächen!?

Es sind doch genau genommen zwei verschiedene Denkweisen (Fläche<->Way). Einerseits mappen wir die Wegebeziehungen als Achsen der “wichtigsten” Nutzer, andererseits sind alle Straßen doch Flächen. Hier: http://osm.org/go/0D6zmqw1L– verläuft die Straße im Zickzack, weil das die Achse für die Autos ist. Fußgänger laufen gerade an den Häusern entlang. Also müsste entsprechend der Fußgängerzone hier auch die Straße im Ganzen als Verkehrsfläche gemappt werden und der Router berücksichtigen, dass es für die Fußgänger kürzer als für die Autos ist :wink:

Zusammenfassend würde ich einfach Beides unter der Bedingung von 3. (letzter Satz) gleichzeitig dulden.

Area=yes ist meiner Meinung nach doch für eine Unterscheidung ausreichend.

Moins,

Mein Oranger Assistent behauptet, dass die (Basis-)Lösung für die Erzeugung virtueller Wege über Flächen mit Hindernissen ebenso trivial ist wie Routensuche oder Erreichbarkeitsanalyse. Die Herausforderung liegt in der Bereitstellung der Daten (Platz und alle sich mit dem Platz überschneidende Hindernisse) und nicht im Erzeugen der Wege.

Soll ich den vorlauten Kerl machen lassen oder ihn lieber ins Regal setzen?

Gruß Wolf

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?