You are not logged in.

Announcement

*** NOTICE: forum.openstreetmap.org is being retired. Please request a category for your community in the new ones as soon as possible using this process, which will allow you to propose your community moderators.
Please create new topics on the new site at community.openstreetmap.org. We expect the migration of data will take a few weeks, you can follow its progress here.***

#51 2013-11-08 11:23:02

GeorgFausB
Member
From: Probstei, Schleswig-Holstein
Registered: 2008-10-14
Posts: 1,916

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

Moin,

openzzz wrote:

Es wäre eben konsequenter als Tags zu fälschen oder immer Neue zu erfinden, die bis auf die Sichtbarkeit nichts anderes bedeuten als die Originale. Bei den Stimmbezirken gab es nur die Wahl, eine Auswertesoftware mit falschen Tags in die Irre zu führen ("x-name" oder "name-dontshow") oder die Optik der Karte zu ruinieren. Der Mapper hat sich zumindest für eine City für die Zweite Möglichkeit entschieden. Es wäre eben alles viel einfacher, wenn man die Ausdrucksmöglichkeit hätte, solche Sonderobjekte "in der Regel", also für "normale" Karten visuell zu unterdrücken.

Mal abgesehen davon, dass man hier bei deinem "Wahlkreis"-Beispiel auch mit einem"visible"-Flag nichts ausgerichtet hätte (*) - ein Namespace virtual: würde genau die Möglichkeit bieten:
- Es dient als Marker für in der Realität nicht vorhandene Objekte.
- Die bisher vorhandenen Möglichkeiten des Taggens (und Auswertens) bleiben erhalten.

Ein neuer Key oder Namespace hat die positive Eigenheit, dass alle Auswerter sich explizit mit der Problematik befassen müssen, während eine bloße zusätzliche negierende Eigenschaft beim Ignorieren zu ungewollten Ergebnissen führt.

Ein Router kann ganz bequem virtual:xyz wie xyz behandeln - ein Renderer wird sie per se erstmal ignorieren.

Gruß
Georg

(*) Der Renderer hat ja bereits die Möglichkeit genutzt, das Objekt anhand dessen Objekt-Keys zu ignorieren - aber eine einzelne Eigenschaft trotzdem gerendert.

Offline

#52 2013-11-08 22:26:29

maxbe
Member
Registered: 2010-01-19
Posts: 3,255
Website

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

fussgaengerinsalzburg.png

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.

Last edited by maxbe (2013-11-08 22:30:50)

Offline

#53 2013-11-08 22:34:18

Netzwolf
Member
Registered: 2008-04-01
Posts: 1,666
Website

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

Nahmd,

maxbe wrote:

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.

http://geo.dianacht.de/tests/fussgaengerinsalzburg.png

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


Fragen zu meinen Posts via Mastodon oder per Twitter-DM.

Offline

#54 2013-11-08 23:02:32

Basstoelpel
Member
Registered: 2008-11-02
Posts: 1,083

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

maxbe wrote:

Bei den wirklich bizarren Umrissen wurden aber oft schon hilfreiche Wege durch die Fläche eingetragen.

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

Offline

#55 2013-11-08 23:19:32

maxbe
Member
Registered: 2010-01-19
Posts: 3,255
Website

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

Netzwolf wrote:

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

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

Offline

#56 2013-11-09 00:36:02

Netzwolf
Member
Registered: 2008-04-01
Posts: 1,666
Website

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

Nahmd,

Basstoelpel wrote:

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.

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

Gruß Wolf


Fragen zu meinen Posts via Mastodon oder per Twitter-DM.

Offline

#57 2013-11-09 09:59:31

Göre
Member
Registered: 2013-09-16
Posts: 991

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

wegavision wrote:

Straßen sind ja immer als Fläche zu sehen, von der einen Grundstücksgrenze bis zur anderen. Warum also da eine Ausnahme machen?
Als einziges Argument würde mir einfallen, dass es auf Karten besser aussieht, aber wie oft hört man hier, wir arbeiten nicht für die Renderer. Oder gibt es noch andere Argumente für die Fläche. Ich würde gerne bei mir die Zone rauschmeißen und wieder eine nette Straße draus machen. Übrigens wird gerne um die Fläche der Zone herum der Straßennamen angezeigt, sieht auch nicht schön aus.


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 cool

Offline

#58 2013-11-09 10:36:15

aighes
Member
From: Shanghai
Registered: 2009-03-29
Posts: 5,383
Website

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

openzzz wrote:

Natürlich soll in erster Linie der "Style" des Renderers entscheiden wie und ob etwas sichtbar ist. Dafür braucht er aber gute "Ausdrucksmöglichkeiten" in Form von Tags. Eine davon wäre eben so ein "Not-Aus" Flag, als "Empfehlung" dieses Objekt "i.d.R." nicht darzustellen.

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

chris66 wrote:

Ich bin auch nicht begeistert. Der Anreiz für eine automatische Lösung im Router wird dadurch auch gemindert.
Gegen ein durchdachtes Proposal hätte ich aber erstmal nichts einzuwenden.

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.

Last edited by aighes (2013-11-09 10:37:29)


Viele Grüße
Henning

Offline

#59 2013-11-09 14:24:21

pyram
Member
Registered: 2012-06-16
Posts: 1,509

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

seawolff wrote:

ich würde es vorziehen, dass ein Netz virtueller Wege über einen Platz vom Mapper und nicht vom Präprozessor erstellt wird

Sehe ich auch so.

Hier meine Überlegungen zu dieser etwas theoretischen Diskussion ;-)

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

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

openzzz wrote:

Natürlich soll in erster Linie der "Style" des Renderers entscheiden wie und ob etwas sichtbar ist. Dafür braucht er aber gute "Ausdrucksmöglichkeiten" in Form von Tags.

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

Offline

#60 2013-11-09 14:25:05

Netzwolf
Member
Registered: 2008-04-01
Posts: 1,666
Website

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

Moins,

chris66 wrote:

Der Anreiz für eine automatische Lösung im Router wird dadurch auch gemindert.

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.

aighes wrote:

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.

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

Gruß Wolf


Fragen zu meinen Posts via Mastodon oder per Twitter-DM.

Offline

#61 2013-11-09 14:47:45

couchmapper
Member
Registered: 2013-02-17
Posts: 462

Re: 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 … /short.pdf

Ansonsten:

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

Ja. cool

Edit: Paper falsch zitiert.

Last edited by couchmapper (2013-11-09 14:49:29)

Offline

#62 2013-11-09 15:00:03

Netzwolf
Member
Registered: 2008-04-01
Posts: 1,666
Website

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

Nahmd,

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

couchmapper wrote:

Ja. cool

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

Last edited by Netzwolf (2013-11-09 15:20:47)


Fragen zu meinen Posts via Mastodon oder per Twitter-DM.

Offline

#63 2013-11-09 17:06:23

couchmapper
Member
Registered: 2013-02-17
Posts: 462

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

Im Netz findet man dazu auch einiges unter den Begriffen:
* Visibility Graph, eigenes Kapitel im Buch Computational Geometry: Algorithms and Applications
* Pathfinding, Link 2 im Kontext Spieleentwicklung
* Noch ein Paper von Hershberger
* Eine nette Visualisierung

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:
16420923dm.png

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

Last edited by couchmapper (2013-11-09 17:23:44)

Offline

#64 2013-11-09 18:00:27

Netzwolf
Member
Registered: 2008-04-01
Posts: 1,666
Website

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

Nahmd,

couchmapper wrote:

Im Netz findet man dazu auch einiges unter den Begriffen:
* Visibility Graph, eigenes Kapitel im Buch Computational Geometry: Algorithms and Applications
* Pathfinding, Link 2 im Kontext Spieleentwicklung
* Noch ein Paper von Hershberger
* Eine nette Visualisierung

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

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

Gruß Wolf


Fragen zu meinen Posts via Mastodon oder per Twitter-DM.

Offline

#65 2013-11-10 00:41:57

openzzz
Member
Registered: 2013-10-03
Posts: 215

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

GeorgFausB wrote:

Moin,
Mal abgesehen davon, dass man hier bei deinem "Wahlkreis"-Beispiel auch mit einem"visible"-Flag nichts ausgerichtet hätte (*) - ein Namespace virtual: würde genau die Möglichkeit bieten:
- Es dient als Marker für in der Realität nicht vorhandene Objekte.
- Die bisher vorhandenen Möglichkeiten des Taggens (und Auswertens) bleiben erhalten.
Ein neuer Key oder Namespace hat die positive Eigenheit, dass alle Auswerter sich explizit mit der Problematik befassen müssen, während eine bloße zusätzliche negierende Eigenschaft beim Ignorieren zu ungewollten Ergebnissen führt.
Ein Router kann ganz bequem virtual:xyz wie xyz behandeln - ein Renderer wird sie per se erstmal ignorieren.

(*) Der Renderer hat ja bereits die Möglichkeit genutzt, das Objekt anhand dessen Objekt-Keys zu ignorieren - aber eine einzelne Eigenschaft trotzdem gerendert.

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.

Offline

#66 2013-11-10 00:53:54

openzzz
Member
Registered: 2013-10-03
Posts: 215

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

couchmapper wrote:

So, hab die Hausaufgabe4 mal installiert und laufen lassen. Das Ergebnis sieht dann so aus:
http://up.picr.de/16420923dm.png
Im Vergleich zu der Liste oben fehlen wahrscheinlich die linienhaften Hindernisse und Durchgänge. Weiß nicht, ob das besonders schwierig ist nachzurüsten.

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.

Offline

#67 2013-11-10 02:30:52

Netzwolf
Member
Registered: 2008-04-01
Posts: 1,666
Website

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

Moins,

ich hatte dieses Déjà-vuschon einmal.

Gruß Wolf


Fragen zu meinen Posts via Mastodon oder per Twitter-DM.

Offline

#68 2013-11-10 03:11:00

maxbe
Member
Registered: 2010-01-19
Posts: 3,255
Website

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

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:
jakob_vorher_r.png

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:

jakob_brech_r.png

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.

jakob_nachher_r.png

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:

jakob_vorher_nachher.png

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.

jakob_vom_platz.png

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.

Last edited by maxbe (2013-11-10 13:04:56)

Offline

#69 2013-11-10 13:06:32

couchmapper
Member
Registered: 2013-02-17
Posts: 462

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

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

Last edited by couchmapper (2013-11-10 13:07:37)

Offline

#70 2013-11-10 13:14:36

openzzz
Member
Registered: 2013-10-03
Posts: 215

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

maxbe wrote:

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

maxbe wrote:

Ich glaube, der Aufwand ist zu hoch für das bisschen Ergebnis, aber andererseits schön routen tut der Router jetzt schon... wink
....
Um zu verdeutlichen, was brute force Algorithmen  so anrichten, hab ich das mal für München durchgerechnet, dauert nicht mal eine halbe Stunde.
...
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.

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.

Last edited by openzzz (2013-11-10 13:19:44)

Offline

#71 2013-11-10 13:17:51

openzzz
Member
Registered: 2013-10-03
Posts: 215

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

couchmapper wrote:

* 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 Edit: typos

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

Offline

#72 2013-11-10 15:32:20

maxbe
Member
Registered: 2010-01-19
Posts: 3,255
Website

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

openzzz wrote:

Ich hatte das Problem zuvor mal als "unendliche viele Möglichkeiten", "kombinatorische Explosion" und "Zickzackkurs" beschrieben. Das wurde nicht ganz ernst genommen.

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

openzzz wrote:

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

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

openzzz wrote:

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.

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

openzzz wrote:

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.

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

Offline

#73 2013-11-10 16:00:49

openzzz
Member
Registered: 2013-10-03
Posts: 215

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

maxbe wrote:

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

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.

Offline

#74 2013-11-10 20:36:44

Tordanik
Moderator
From: Germany
Registered: 2008-06-17
Posts: 2,840
Website

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

maxbe wrote:

Mehreckige Häuser werden natürlich auch jetzt durch alle Ecken dargestellt (z.B. die Kirche am Preysingplatz).

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

Last edited by Tordanik (2013-11-10 20:37:00)


OSM in 3D: OSM2World

Offline

#75 2013-11-11 10:50:02

chris66
Member
From: Germany
Registered: 2009-05-24
Posts: 10,106

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

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

16440460wp.jpg

Last edited by chris66 (2013-11-11 10:50:48)


Mapper aus dem Münsterland.

Offline

Board footer

Powered by FluxBB