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

wegavision wrote:

Ich würde gerne bei mir die Zone rauschmeißen und wieder eine nette Straße draus machen.

Lass sie bitte drin. "Falsch" ist das ja nicht. Und spätestens wenn das Area-Objekt mit Api 0.7 kommt (*), wirst du das bedauern.

Übrigens wird gerne um die Fläche der Zone herum der Straßennamen angezeigt, sieht auch nicht schön aus.

Altbekanntes Mapnik-Problem, der immer noch alle Flächen am Rande beschriftet. Hänge "deine" Fußgängerzone in die Beschwerdeliste zu Mapnik rein und nimm uns nicht durch "gefälliges Umtaggen" die Argumente weg.

oder häng ein area=yes dran, wie die Kollegen bereits bemerkten.

Gruss
walter

• ) Bin schon über 30 - ob ich das noch erleben werde? 😉
  

wegavision wrote:

...Übrigens wird gerne um die Fläche der Zone herum der Straßennamen angezeigt, sieht auch nicht schön aus.

Hast du auf deine FuZo ein area=yes Tag hängen? Wenn nein - nimm das mal mit auf. Dann sollte es passen... (in "meiner" Stadt werden alle "FuZos" normal beschriftet....)

Nahmd,

wambacher wrote:

Altbekanntes Mapnik-Problem, der immer noch alle Flächen am Rande beschriftet. Hänge "deine" Fußgängerzone in die Beschwerdeliste zu Mapnik rein und nimm uns nicht durch "gefälliges Umtaggen" die Argumente weg.

Pack ein area=yes an die Fläche, und die Hauptkarte zeigt eine beschriftete Fläche.

Gruß Wolf

wegavision wrote:

Oder gibt es noch andere Argumente für die Fläche

Im Gegensatz zu üblichen Straßen haben Fussgängerzonen häufig Formen, die sich durch "längliches highway=pedestrian mit width=n Meter breite" nicht beschreiben lassen.

Grüße, Max

maxbe wrote:

wegavision wrote:

Oder gibt es noch andere Argumente für die Fläche

Im Gegensatz zu üblichen Straßen haben Fussgängerzonen häufig Formen, die sich durch "längliches highway=pedestrian mit width=n Meter breite" nicht beschreiben lassen.
Grüße, Max

Das gibt's häufig (z.B. an Plätzen), aber zum großen Teil sind sie doch eher straßenförmig (nur rotes Pflaster statt Asphalt). Es waren ja auch früher meist gewöhnliche Straßen.

Einen großen Unterschied Fläche / Straße gibt es vielleicht beim Routing. Die meisten Fußgängerzonen in meiner Umgebung sind für Radfahrer freigegeben. Ich lasse mich da zwar i.d.R. nicht von OSM routen, aber es ist für Radfahrer praktisch, quer durch die Innenstadt zu fahren statt am Autoring rundherum. Vermutlich hätten Routingprogramme ein Problem, wenn kein richtiges Straßennetz die Pfade ermöglicht. Gedanklich aus der Router-Logik (minimierte Pfadkostenfunktion), nicht was wir visuell an der Karte sehen. Als Fußgänger kann man sich von OsmAnd auch routen lassen. Ob Flächen die üblichen Routing-Konzepte über den Haufen werfen?

Manchmal wundert man sich, warum OsmAnd Wegeverbindungen nicht nutzt, obwohl scheinbar alles richtig getaggt wurde. Ein paar Fälle hatte ich in JOSM untersucht, aber keinen Grund für die Router-Verweigerungshaltung gefunden. Gibt es ein paar gute Tipps für Router-freundliches Tagging?

openzzz wrote:

Ob Flächen die üblichen Routing-Konzepte über den Haufen werfen?

Ja:

(Routing über den Marstallplatz)

Die meisten Router (eigentlich alle, die ich kenne...) ignorieren "area=yes", freuen sich über den Umring als "highway=pedestrian" und routen agoraphobisch an Rand entlang. Das ist aber kein grundsätzliches Problem, man könnte ja virtuelle Abkürzungen vorher oder zur Laufzeit berechnen, die alle Abzweigungen miteinander verbinden. Macht nur kaum einer in der Praxis. Die nächste Stufe wären dann Plätze mit Hindernis in der Mitte.

openzzz wrote:

Gibt es ein paar gute Tipps für Router-freundliches Tagging?

Mitten durch den "highway=pedestrian, area=yes" ein paar "highway=pedestrian" ohne area legen, die alle Nebenstraßen verbinden. Und hoffen, dass es kein Renderer bemerkt. Aber wir taggen ja nicht für Router...

Grüße, Max

Edit: Link ergänzt

Nahmd,

Die meisten Router (eigentlich alle, die ich kenne...) ignorieren "area=yes", freuen sich über den Umring als "highway=pedestrian" und routen agoraphobisch an Rand entlang.

Gibts auch als Lied: “Und dann schleich ich – still und heimlich – immer an der Wand lang, immer an der Wand lang …”

maxbe wrote:

Mitten durch den "highway=pedestrian, area=yes" ein paar "highway=pedestrian" ohne area legen, die alle Nebenstraßen verbinden. Und hoffen, dass es kein Renderer bemerkt. Aber wir taggen ja nicht für Router...

Für den Router taggen ist böse.

Gruß Wolf

Edit: Kommentar zum Router ergänzt.

maxbe wrote:

Mitten durch den "highway=pedestrian, area=yes" ein paar "highway=pedestrian" ohne area legen, die alle Nebenstraßen verbinden. Und hoffen, dass es kein Renderer bemerkt. Aber wir taggen ja nicht für Router...

Man müsste die Welt irgendwie logisch und konsequent in die Datenstruktur umsetzen, so dass
es auch automatisch arbeitende Programme wie Routingapps verstehen.
Man taggt nicht für bestimmte Apps, aber doch so dass ein Computer die Beziehungen
automatisch verarbeiten kann (setzt ein gewisses Maß an Standardisierung voraus).

Mit Straßen ist es am einfachsten, sicher sinnvoll für normale straßenförmige Fußgängerzonen.
Dein Beispiel war ein Platz. Da wäre es wohl nicht elegant, nichtexistente Straßen durchzuziehen.
Wenn der als begehbar und Rad-befahrbar markiert wird, müsste eine App das eigentlich
berücksichtigen und die Zugangsknoten in einer Route verbinden. Die Metrik ist über die
Distanz eigentlich klar.

Schwieriger für Routingsoftware wäre der Fall, wenn ganze Innenstädte als Fußgängerflächen
markiert werden, also dann das Wegenetz komplett entfällt.
Kein Graphenoptimierungsproblem mehr, sondern so etwas wie Raytracing für Routen.

p.s.
"wir taggen nicht für Router", aber man könnte vielleicht mit unsichtbaren Straßenverbindern
(gibt es eine display=no - Option?) die logischen Verknüpfungen der Wege klarmachen.
Für den Fall dass die Router grundsätzliche Probleme mit dem Typ "begehbare" Fläche haben.
Ich meine, dafür ist die Anwendung Routing wichtig genug, dass man sie gut versorgt.
In den Bergen hat mir OsmAnd schon 2km Umwege vorgeschlagen, nur weil irgendwo
logische Verbindungen im Wegenetz nicht korrekt waren (in JOSM konnte ich keine Fehler finden).
Zum Glück hatte ich noch eine Papierkarte dabei: gibt einen besseren Überblick als die
Peepshow im Smartphone-Display.

Nahmd,

openzzz wrote:

Wenn der als begehbar und Rad-befahrbar markiert wird, müsste eine App das eigentlich
berücksichtigen und die Zugangsknoten in einer Route verbinden. Die Metrik ist über die
Distanz eigentlich klar.

Schwieriger für Routingsoftware wäre der Fall, wenn ganze Innenstädte als Fußgängerflächen
markiert werden, also dann das Wegenetz komplett entfällt.
Kein Graphenoptimierungsproblem mehr, sondern so etwas wie Raytracing für Routen.

Die Aufgabenstellung ist gut charakterisiert: gegeben ein allgemeines Polygon (auch mit Löchern). Im Polygon und am Rand des Polygons eine Anzahl von Punkten. Gesucht ist der minimale Graph, dessen Kanten nur innerhalb des Polygons (und auf dessen Rand) verlaufen, auf dem je zwei der gegeben Punkte mit geringster Weglänge verbunden sind. Technisch schwierig ist das nicht, es ist nur viel Arbeit.

Das Problem ist eher sozial: für die Lösung dieser Aufgabe gibt es keinerlei Belohnung. Sie wird (unsichtbar) in Routing-Applikationen integriert und verhilft diesen zu (geringfügig) besseren Ergebnissen. Der Autor bleibt unsichtbar. Eine ähnlich undankbare Aufgabe ist die optimierte Platzierung von Texten und Symbolen in Karten. Und für soziale Probleme gibt es keine technische Lösungen.

Naja, vielleicht gehst Du die Aufgabe an?

"wir taggen nicht für Router", aber man könnte vielleicht mit unsichtbaren Straßenverbindern
(gibt es eine display=no - Option?) die logischen Verknüpfungen der Wege klarmachen.

Ich sehe zwei getrennte Aufgaben: zum einen das Routing durch erfasse Flächen (siehe oben); zum anderen ein Taggingschema zum Erfassen von Flächen ausschließlich zum Routen. Letzteres hätte auch ich gerne für meine Arbeit in den Alpen: da widerstrebt es mir, durch gangbare Flächen willkürlich Wege “highway=path; visibility=no” einzutragen, nur damit algorithmisch ein Weg durch die Fläche gefunden werden kann.

Als Schlüssel würde ich “highway” verwenden, weil es thematisch um einen (abstrakten) Weg geht. Als Wert vielleicht “pathless”, und dann hoffen, dass die Renderregeln der Standardkarten unbekannte Werte von “highway” einach ignorieren. Also: “highway=pathless; area=yes”.

Gruß Wolf

Netzwolf wrote:

Die Aufgabenstellung ist gut charakterisiert: gegeben ein allgemeines Polygon (auch mit Löchern). Im Polygon und am Rand des Polygons eine Anzahl von Punkten. Gesucht ist der minimale Graph, dessen Kanten nur innerhalb des Polygons (und auf dessen Rand) verlaufen, auf dem je zwei der gegeben Punkte mit geringster Weglänge verbunden sind. Technisch schwierig ist das nicht, es ist nur viel Arbeit.
....
Das Problem ist eher sozial: für die Lösung dieser Aufgabe gibt es keinerlei Belohnung. Sie wird (unsichtbar) in Routing-Applikationen integriert und
....
Als Schlüssel würde ich “highway” verwenden, weil es thematisch um einen (abstrakten) Weg geht. Als Wert vielleicht “pathless”, und dann hoffen, dass die Renderregeln der Standardkarten unbekannte Werte von “highway” einach ignorieren. Also: “highway=pathless; area=yes”.
Gruß Wolf

"schwierig" ist relativ. Je verwinkelter ein Innenstadtfußgängerbereich ist, desto schwieriger wird das. Ich denke so in Richtung kombinatorischer Explosion. Bei einem Wegenetz gibt es nur ein paar Knoten und Connections. Hier gibt es ja im Prinzip unendlich viele Wege. Eine direkte Gerade ziehen geht ja nur bei einfach gelagerten Fällen wie das Beispiel eines Platzes.

Kein Routing-Programm das ich kenne macht so etwas. Ich habe da nur die Raytracer im Kopf. Das ist massiver Rechenaufwand. Vielleicht zu viel verlangt für die preiswerten Routing-Apps. Doch, Victor, der Autor von OsmAnd produziert zwar OpenSource, verkauft aber auch eine Plus-Version im Market. Die App ist beliebt. Vielleicht lohnt sich das doch.

Einfacher wäre natürlich so ein unsichtbarer Weg. Gibt's kein invisible-Tag? "display=yes/no"? Das fände ich hilfreich. Es gibt durchaus versteckte Daten, die sematisch wichtig sind, aber nicht auf einer Karte dargestellt werden sollen. So wie hier.

Nahmd,

openzzz wrote:

"schwierig" ist relativ. Je verwinkelter ein Innenstadtfußgängerbereich ist, desto schwieriger wird das.

Nein. Wenn der Algorithmus korrekt ist, wird die Implementierung alle Aufgaben lösen. Da gibt es keine “Schwierigkeit” mehr, sondern nur die Frage nach Rechenzeit und Speicherplatz.

Ich denke so in Richtung kombinatorischer Explosion. Bei einem Wegenetz gibt es nur ein paar Knoten und Connections. Hier gibt es ja im Prinzip unendlich viele Wege. Eine direkte Gerade ziehen geht ja nur bei einfach gelagerten Fällen wie das Beispiel eines Platzes.

Eine kurze Überlegung zeigt, dass man sich auf die “Anschlusspunkte”, an denen weitere Wege ansetzen, und die konkaven Eckpunkte des Polygons beschränken kann, und nur Kanten zwischen diesen Punkten betrachten muss. Erster Entwurf eines Algorithmus: 1. die konkaven Ecken des Polygons finden (trivial) und zu den Anschlusspunkten werfen. 2. Von jedem Punkt der enthaltenen Menge eine Kante zu allen gradlinig erreichbaren (“sichtbaren”) Punkten erzeugen. 3. Auf diesem Graph von jedem der Anschlusspunkte zu jedem anderen Anschlusspunkt die kürzeste Verbindung suchen (Implementierung per Mini-Router). 4. Aus dem Graph alle Kanten streichen, die von keiner der optimalen Verbindungen benutzt werden. 5. Heuraka.

Kein Routing-Programm das ich kenne macht so etwas. Ich habe da nur die Raytracer im Kopf. Das ist massiver Rechenaufwand. Vielleicht zu viel verlangt für die preiswerten Routing-Apps.

Das ist auch nicht Aufgabe einer Applikation, sondern wird bei der Vorverarbeitung der Daten erledigt. Als Ergebnis fliegt die Fläche raus und wird durch die erzeugten Kanten ersetzt. Nur für das Routing natürlich und nicht für die Anzeige, bei letzterer bleibt die Fläche. Die Applikation weiß nichts von dieser Konversion.

Zu den weglosen Wegen…

Einfacher wäre natürlich so ein unsichtbarer Weg. Gibt's kein invisible-Tag? "display=yes/no"? Das fände ich hilfreich. Es gibt durchaus versteckte Daten, die sematisch wichtig sind, aber nicht auf einer Karte dargestellt werden sollen. So wie hier.

Ich möchte den Auswertern nichts vorschreiben, sondern ihnen so viele Informationen geben, dass sie vernünftige Entscheidungen treffen können. In meinem Fall mit den gangbaren, aber weglosen Flächen kann ich mir durchaus vorstellen, dass sie in einer Spezialkarte, z.B. der Topo von maxbe oder der Garmin-Alpenkarte von unixasket dezent dargestellt werden.

Gruß Wolf

Netzwolf wrote:

...
Eine kurze Überlegung zeigt, dass man sich auf die “Anschlusspunkte”, an denen weitere Wege ansetzen, und die konkaven Eckpunkte des Polygons beschränken kann, und nur Kanten zwischen diesen Punkten betrachten muss. Erster Entwurf eines Algorithmus: 1. die konkaven Ecken des Polygons finden (trivial) und zu den Anschlusspunkten werfen. 2. Von jedem Punkt der enthaltenen Menge eine Kante zu allen gradlinig erreichbaren (“sichtbaren”) Punkten erzeugen. 3. Auf diesem Graph von jedem der Anschlusspunkte zu jedem anderen Anschlusspunkt die kürzeste Verbindung suchen (Implementierung per Mini-Router). 4. Aus dem Graph alle Kanten streichen, die von keiner der optimalen Verbindungen benutzt werden. 5. Heuraka.
...
Zu den weglosen Wegen…

Einfacher wäre natürlich so ein unsichtbarer Weg. Gibt's kein invisible-Tag? "display=yes/no"? Das fände ich hilfreich. Es gibt durchaus versteckte Daten, die sematisch wichtig sind, aber nicht auf einer Karte dargestellt werden sollen. So wie hier.

Ich möchte den Auswertern nichts vorschreiben, sondern ihnen so viele Informationen geben, dass sie vernünftige Entscheidungen treffen können. In meinem Fall mit den gangbaren, aber weglosen Flächen kann ich mir durchaus vorstellen, dass sie in einer Spezialkarte, z.B. der Topo von maxbe oder der Garmin-Alpenkarte von unixasket dezent dargestellt werden.
Gruß Wolf

Ich hatte gestern mal etwas ähnliches aufgekritzelt. Problem Route über Fläche mit Löchern, hatte "Kreisverkehre" um jedes Loch gezogen. Die Route hangelt sich dann von Kreisverkehr zu Kreisverkehr bis zum Ziel, mit jeweils 2 möglichen Umgehungsrichtungen. Die Entry/Exit-Nodes waren ja sowieso diskretisiert am Straßennetz. Das reduziert die Komplexität auf etwas Berechenbares. Deine Lösung ist noch effizienter, weil es auf die begrenzenden Polygone fixiert. Es ist noch nicht ganz der kürzeste Pfad, weil nur an den Rändern der Fläche angedockt wird statt in Straßen/Platzmitte (real läuft man kein Zickzack), kommt dem aber schon näher. Es wird aber weitere Probleme geben, wenn Flächen nebeneinander gezeichnet sind, die erstmal zu einer Gesamtfläche fusioniert werden müssen.

Naja, ich fände es eleganter für eine sematische Datenstruktur, Fußgängerstraßen einfach nur als Straßen zu erfassen und nur die Plätze wirklich als Flächen.

Was spricht gegen ein Sichtbarkeits-Flag? Ein Renderer könnte natürlich solche Regeln bzw. Empfehlungen ignorieren, aber wenn sich das durchsetzt hätte man ein paar mehr Ausdrucksmöglichkeiten, ohne eine Kartenansicht zu stören. Es gibt eben Dinge wo man schon vorher weiß, dass eine Darstellung in Karten keinen Sinn macht. Hier ein Beispiel für ein unsichtbares Verbindungsnetz von Straßen, nur um die Verbindungslogik zu erhalten. Oder wenn man defekte Daten zeitweise unsichtbar stellt bis sie repariert wurden, dann müsste man dafür nicht unbedingt alle Querbeziehungen lösen. JSOM würde natürlich alles zum Editieren zeigen.

openzzz wrote:

Es gibt eben Dinge wo man schon vorher weiß, dass eine Darstellung in Karten keinen Sinn macht. Hier ein Beispiel für ein unsichtbares Verbindungsnetz von Straßen, nur um die Verbindungslogik zu erhalten.

Das widerspricht aber eklatant dem bisherigen Ansatz von OSM, das nur Dinge gemappt werden, die in der Realität vorhanden sind, und keine Krücken für Routingalgorithmen (aka "Wir mappen nicht für den Router").

Netzwolf wrote:

Eine kurze erlegung zeigt, dass man sich auf die Anschlusspunkte, an denen weitere Wege ansetzen, und die konkaven Eckpunkte des Polygons beschrken kann, und nur Kanten zwischen diesen Punkten betrachten muss. Erster Entwurf eines Algorithmus: 1. die konkaven Ecken des Polygons finden (trivial) und zu den Anschlusspunkten werfen. 2. Von jedem Punkt der enthaltenen Menge eine Kante zu allen gradlinig erreichbaren (sichtbaren) Punkten erzeugen. 3. Auf diesem Graph von jedem der Anschlusspunkte zu jedem anderen Anschlusspunkt die kzeste Verbindung suchen (Implementierung per Mini-Router). 4. Aus dem Graph alle Kanten streichen, die von keiner der optimalen Verbindungen benutzt werden. 5. Heuraka.

openzzz wrote:

Ich hatte gestern mal etwas ähnliches aufgekritzelt. Problem Route über Fläche mit Löchern, hatte "Kreisverkehre" um jedes Loch gezogen. Die Route hangelt sich dann von Kreisverkehr zu Kreisverkehr bis zum Ziel, mit jeweils 2 möglichen Umgehungsrichtungen. Die Entry/Exit-Nodes waren ja sowieso diskretisiert am Straßennetz. Das reduziert die Komplexität auf etwas Berechenbares.

Falls mir das jemand auch auf postgis ausdrücken kann, kann ich das gerne mal versuchsweise einbauen. Falls ich das mache, hat das aber den Nachteil, dass das nur für ein sehr exotisches System gebaut wird. pgrouting ist zwar schon ein bisschen verbreitet, aber im OSM-Umfeld eigentlich eher nicht so...

Vielviel schöner wäre natürlich ein generelles Werkzeug, das .osm-Dateien frisst und .osm-Dateien ausspuckt, die alles aus der Eingabedatei enthalten und zusätzlich die virtuellen Wege.

Bei pgrouting sieht ein Routing-Graph so aus:

(Die Zahl vor dem + bei Kanten ist die Länge, der Rest ist Gewichtungszeug.
Die Punkte sind die Verbindungsknoten)

Oder ein bisschen weniger anschaulich:

osm=>␣select␣gid,source,target,length,the_geom␣from␣routing_ways␣where␣osm_id=10071036;
gid␣␣|␣source␣|␣target␣|␣␣length␣␣␣␣|␣␣␣␣␣␣␣␣␣the_geom
-------+--------+--------+-----------+------------------------------------------------
40107␣|␣␣15371␣|␣␣51862␣|␣23.566894␣|␣0102000020E6100000040000006....
40108␣|␣␣51862␣|␣␣37460␣|␣␣98.79034␣|␣0102000020E6100000040000000....
40109␣|␣␣37460␣|␣␣51864␣|␣118.51488␣|␣0102000020E61000000400000␣....
40110␣|␣␣51864␣|␣␣37497␣|␣␣53.28253␣|␣0102000020E6100000030000007.......
40106␣|␣␣37497␣|␣␣15371␣|␣105.84595␣|␣0102000020E6100000030000008...

Dass die Verbindung (51864, 37460, 51862, 15371, 37497, 51864) ursprünglich mal eine Fläche war, weiss der Router nicht mehr. Das kann er aber rausbekommen, die ursprüngliche OSM-ID steht bei den Wegen dabei und die Nachbartabelle kennt die Tags dazu. Der umgekehrte Weg (ich kenne eine Fläche und suche die dazu passenden Kanten) ist auch einfach. Die Geometrie der Wege steht ebenfalls im Graphen.

Über Plätze mit Löchern muss ich mir gar keine Gedanken machen. Die Importer für pgrouting (früher wars mal osm2pgrouting, jetzt nehme ich osm2po), können nicht mit Relationen umgehen (*seufz*). Das ist kein grosses Problem, die meisten Hindernisse auf Plätzen bestehen aus Gebäuden, die einfach über den highway=* gesetzt wurden und sind damit sowieso für Router unsichtbar. Schön ausgeschnittene Löcher sind aber leider in meinem Router ebenfalls einfach nicht vorhanden...

Grüße, Max

In der Mailingliste ist das Thema übrigens gestern auch aufgetaucht. Nur wandern die dort über Strände statt über Fussgängerzonen...

Moins,

openzzz wrote:

Netzwolf wrote:

... Eine kurze Überlegung zeigt, dass man sich auf die “Anschlusspunkte”, an denen weitere Wege ansetzen, und die konkaven Eckpunkte des Polygons beschränken kann, und nur Kanten zwischen diesen Punkten betrachten muss. Erster Entwurf eines Algorithmus: 1. die konkaven Ecken des Polygons finden (trivial) und zu den Anschlusspunkten werfen. 2. Von jedem Punkt der enthaltenen Menge eine Kante zu allen gradlinig erreichbaren (“sichtbaren”) Punkten erzeugen. 3. Auf diesem Graph von jedem der Anschlusspunkte zu jedem anderen Anschlusspunkt die kürzeste Verbindung suchen (Implementierung per Mini-Router). 4. Aus dem Graph alle Kanten streichen, die von keiner der optimalen Verbindungen benutzt werden. 5. Heuraka.

[…] Deine Lösung ist noch effizienter, weil es auf die begrenzenden Polygone fixiert. Es ist noch nicht ganz der kürzeste Pfad, weil nur an den Rändern der Fläche angedockt wird statt in Straßen/Platzmitte (real läuft man kein Zickzack), kommt dem aber schon näher.

Der Algorithmus produziert genau die Ways, die es erlauben, zwischen Beliebigen der Anschlusspunkte auf kürzestem Wege den Platz zu überqueren. Und ja, man läuft (außer auf konvexen Plätzen ohne Hindernisse) durchaus im Zickzack: stell Dir einen Platz vor in Form eines Z (natürlich mit fettem Pinsel gepinselt, damit es flächig wird), Anschlusspunkte oben links und unten rechts. Und jetzt lauf von einem Anschlusspunkt zum anderen über den Platz… 🙂

Es wird aber weitere Probleme geben, wenn Flächen nebeneinander gezeichnet sind, die erstmal zu einer Gesamtfläche fusioniert werden müssen.

Das ist korrekt. Um die Menge virtueller Wege zu erzeugen, muss man die Flächen zuerst verbinden. Spannend wird es bei unterschiedlichen Access-Regeln: die flächengrenzenüberschreitenden Wege müssen dann mit der Vereinigung der access der beiden Teilflächen versehen werden. Das ist dann nach der Pflicht die Kür 🙂

Naja, ich fände es eleganter für eine sematische Datenstruktur, Fußgängerstraßen einfach nur als Straßen zu erfassen und nur die Plätze wirklich als Flächen.

Lineare Fußgängerzonen/Einkaufsstraßen wie die Hohestraße in Köln würde ich auch als Linien erfassen, etwas wie die Domplatte oder den Bahnhofsvorplatz aber flächig.

Was spricht gegen ein Sichtbarkeits-Flag? Ein Renderer könnte natürlich solche Regeln bzw. Empfehlungen ignorieren, aber wenn sich das durchsetzt hätte man ein paar mehr Ausdrucksmöglichkeiten, ohne eine Kartenansicht zu stören. Es gibt eben Dinge wo man schon vorher weiß, dass eine Darstellung in Karten keinen Sinn macht.

Hier ein Beispiel für ein unsichtbares Verbindungsnetz von Straßen, nur um die Verbindungslogik zu erhalten.

Wenn es eine Verbindung gibt, darf die auch in der Karte dargestellt werden.

Virtuelle Ways für besseres Routing über Flächen kann und sollte man während der Vorverarbeitung der Routing-Daten erzeugen. Die haben in der DB nichts verloren.

Oder wenn man defekte Daten zeitweise unsichtbar stellt bis sie repariert wurden, dann müsste man dafür nicht unbedingt alle Querbeziehungen lösen. JSOM würde natürlich alles zum Editieren zeigen.

Das ist eine Überlegung wert. Da man beim "Disablen" ohnehin eine neue Version der Objekte erzeugt, kann man ein beliebiges Tag ändern. Ich schreibe in solchen Fällen ein "x-" vor das Haupttag. Ein Beispiel: es hatte mal jemand offensichtlich einen Track in einen OSM-Way umgewandelt und in die DB gespeichert. Und das verwendete Tool hat jeder node einen Namen gegeben. Sah in der Karte nicht wirklich gut aus. Deshalb hab ich aus den "name=" jeweils "x-name" gemacht. Vorteil: alle existierenden 598712659278365872 Renderer kommen ohne Anpassung damit zurecht.

Gruß Wolf

OpenTripPlanner kann wohl über Plätze routen, siehe Blog "b-roll: David solves the plaza problem, with help from de Berg and Matt Conway". Dort ist auch der Ansatz etwas beschrieben. OpenTripPlanner ist Open Source (LGPL) und in Java. Da ÖPNV-Routing integriert ist, gibt es aber leider wohl nur regionale Installationen.

Gruß,
Norbert

Nahmd,

ikonor wrote:

OpenTripPlanner kann wohl über Plätze routen, siehe Blog "b-roll: David solves the plaza problem, with help from de Berg and Matt Conway". Dort ist auch der Ansatz etwas beschrieben.

Genau das haben wir oben diskutiert. Laut Beschreibung nutzen die alle Ecken aller Löcher, da kann man sich aber auf die konvexen Ecken beschränken. Dazu kann man alle Ways streichen, bei denen am Zielpunkt die beiden Segmente der Beschränkungslinie auf unterschiedlichen Seiten des Ways liegen, dann löst sich auch das Problem mit dem hochaufgelösten Kreis in Wohlgefallen auf.

OpenTripPlanner ist Open Source (LGPL) und in Java.

Jetzt muss nur noch jemand den Area-Routing-Code herausoperieren, und schon kann er den von maxbe gewünschten Preprozessor bauen.

Gruß Wolf

gormo wrote:

Das widerspricht aber eklatant dem bisherigen Ansatz von OSM, das nur Dinge gemappt werden, die in der Realität vorhanden sind, und keine Krücken für Routingalgorithmen (aka "Wir mappen nicht für den Router").

Im Gegenteil. OSM verwendet ein für das Routing optimiertes Datenmodell. Straßen werden trotz endlicher Breite als Liniennetz gemappt, Fährlinien als way einer typischen Fahrstrecke.
Selbst 500m breite Flüsse werden als Linie erfasst, einmündende Gewässer bis zur Mittellinie des Hauptstroms ergänzt (obwohl das Wasser in der Realität nicht zur Strommitte fließt).

Die Ergänzungen durch "area:highway" oder "riverbank" kamen später.

Netzwolf wrote:

Das ist eine Überlegung wert. Da man beim "Disablen" ohnehin eine neue Version der Objekte erzeugt, kann man ein beliebiges Tag ändern. Ich schreibe in solchen Fällen ein "x-" vor das Haupttag. Ein Beispiel: es hatte mal jemand offensichtlich einen Track in einen OSM-Way umgewandelt und in die DB gespeichert. Und das verwendete Tool hat jeder node einen Namen gegeben. Sah in der Karte nicht wirklich gut aus. Deshalb hab ich aus den "name=" jeweils "x-name" gemacht. Vorteil: alle existierenden 598712659278365872 Renderer kommen ohne Anpassung damit zurecht.

Es gibt funktionierende "dirty hacks" und elegante Lösungen. Letztere würde ich bevorzugen.
Falls die Funktion gewünscht wird, fallweise bestimmte Elemente nicht anzeigen zu lassen,
kann man das sauber über ein visibility-Tag definieren. Es darf ruhig die Ausnahme für Sonderfälle
bleiben. Man ist nicht gewungen, jedesmal die Sichtbarkeit zu setzen.
Ich fände es eleganter als die Tag-Namen umzufrisieren, in falsche oder nichtexistente Namen,
nur um den Renderer auszutricksen. Das wäre "Mappen für den Renderer".

Ich sehe es auch so, dass man Fussgängerzonen (wie alle anderen Strassen auch) normalerweise als Way und nur da wo es eher ein Platz ist als Fläche erfassen sollte. Und wenn man die Fläche dazu haben möchte die eben zusätzlich als "area:highway"=*.

gormo wrote:

Das widerspricht aber eklatant dem bisherigen Ansatz von OSM, das nur Dinge gemappt werden, die in der Realität vorhanden sind, und keine Krücken für Routingalgorithmen (aka "Wir mappen nicht für den Router").

Das ist mal leicht dahergesagt. Aber für wen willst du denn Mappen? Nicht für gerenderte Karten? Nicht für Router?
Für wen denn? Als reine Beschäftigungstherapie?

OpenStreet"Map" ist von der Grundidee her eine Karte, die natürlich weitaus mehr bietet, also Themenkarten (Geschichte, Denkmäler etc), Routing auf Karten, Einkaufsführer, Restaurantführer, internationales Straßenlampenverzeichnis etc.

Es gibt dabei häufig genutzte Anwendungen, z.B. als topografische Karte, Stadtplan oder Routing-Karte,
und eher seltene Anwendungen (Wahlkreise, politische Karten? ).

Die OSM-Datenbasis muss eben all den Anwendungen eine gute Grundlage bieten,
vor allem natürlich den häufig genutzten. Man mappt also dass der Renderer alles schön
darstellt, dass der Router gute Routen findet etc.
Das heisst nicht, dass man "dirty hacks" zur Politik erklärt, aber wenn der
Router eine bestimmte Logik im Verbindungsnetz benötigt, warum sollte man
nicht "routerfreundlich" taggen? Es ist schon ein großer Fortschritt, dass man routingfähige
OSM-Karten erzeugen kann. Das war früher nur mit kommerziellen Karten möglich.

Wenn Router heutzutage Probleme mit den Flächen haben, kann man ruhig punktuell
an Problemstellen etwas nachhelfen. Was ist so böse daran? Wichtig ist doch, dass
OSM-Routing in der Praxis funktioniert (also mit Gerät vor Ort und nicht nur theoretisch).

Nahmd,

openzzz wrote:

Netzwolf wrote:

Deshalb hab ich aus den "name=" jeweils "x-name" gemacht. Vorteil: alle existierenden 598712659278365872 Renderer kommen ohne Anpassung damit zurecht.

Es gibt funktionierende "dirty hacks" und elegante Lösungen. Letztere würde ich bevorzugen.
Falls die Funktion gewünscht wird, fallweise bestimmte Elemente nicht anzeigen zu lassen,
kann man das sauber über ein visibility-Tag definieren. Es darf ruhig die Ausnahme für Sonderfälle
bleiben. Man ist nicht gewungen, jedesmal die Sichtbarkeit zu setzen.
Ich fände es eleganter als die Tag-Namen umzufrisieren, in falsche oder nichtexistente Namen,
nur um den Renderer auszutricksen. Das wäre "Mappen für den Renderer".

Nun ja.

Ich verwende das System der “x-”-Prefixe, das im Internet seit Jahrzehnten bewährt ist, das System ist selbsterklärend, ich kann jedes Feature einzeln ein- und ausschalten, und das Beste: das System ist mit allen existierenden Auswertern und Renderern kompatibel. 🙂

Das “display=no” ist nicht selbsterklärend – es könnte auch bedeuten, das der Laden eine Auslage hat –, ich kann damit nur gleich das ganze Feature ausschalten, und keiner der existierenden Auswerter oder Renderer versteht es. 🙁

Wer gewinnt die Ausschreibung? 😛

Gruß Wolf

Netzwolf wrote:

Nahmd,
Ich verwende das System der “x-”-Prefixe, das im Internet seit Jahrzehnten bewährt ist, das System ist selbsterklärend, ich kann jedes Feature einzeln ein- und ausschalten, und das Beste: das System ist mit allen existierenden Auswertern und Renderern kompatibel. 🙂
Gruß Wolf

Aber bei den unsichtbaren Wegen über Flächen würde das nicht gehen, oder?
Der Tagname wird umdefiniert und ist dann auch für den Router nicht mehr zu nutzen.

Ein ähnlicher Fall bei den Stimmkreisen: dem Mapper war es selbst peinlich, eine ganze Stadt auf dem Plan zugekleistert zu haben. Er wollte aber auch nicht das name-Tag umbenennen, weil dann die Funktion beinträchtigt wird. Die Renderer haben das Darstellungsproblem nicht gelöst (bzw. ihre Policy geändert), also hat er dann aus Verzweiflung die ganzen Objekte wieder gelöscht. Es wäre einfacher gewesen, diese temporären election boundaries gleich als unsichtbar zu deklarieren. Also als Kennzeichnung "wird regulär nicht dargestellt", mit der verbleibenden Möglichkeit von Spezialprogrammen, diese geografischen Objekte doch auszuwerten. Man kann so also Semantik verbauen, ohne die Optik einer Karte zu beschädigen.

Kennst du MathML? Bei Formeln gibt es eine duale Beschreibung. Es gibt die semantische Beschreibung, die die Beziehungen der Terme ausdrückt. Formeln können so in Software automatisch verarbeitet und berechnet werden. Daneben gibt es noch eine "presentation" Auszeichnung, wie eine Formel auf Papier aussehen soll. Erinnert mich irgendwie auch an OSM beim Problem sematische Auszeichnung vs. Präsentation auf Karte.

Nahmd,

openzzz wrote:

Aber bei den unsichtbaren Wegen über Flächen würde das nicht gehen, oder?

Die "unsichtbaren Wege" sind eine Krücke fürs Routing, die wird man bei der Aufbereitung der OSM-Daten fürs Routing erzeugen und dann integrieren, aber keinesfalls in die DB schreiben. Da haben die nichts zu suchen.

Ein ähnlicher Fall bei den Stimmkreisen: dem Mapper war es selbst peinlich, eine ganze Stadt auf dem Plan zugekleistert zu haben. Er wollte aber auch nicht das name-Tag umbenennen, weil dann die Funktion beinträchtigt wird. Die Renderer haben das Darstellungsproblem nicht gelöst (bzw. ihre Policy geändert), also hat er dann aus Verzweiflung die ganzen Objekte wieder gelöscht.

Du hast fleißig durch Relevanzdiskussion dazu beigetragen.

Es wäre einfacher gewesen, diese temporären election boundaries gleich als unsichtbar zu deklarieren.

Ich hätte die Relationen erhalten und das “type=boundary” gegen ein “type=x-boundary” ausgetauscht; das beruhigt die Kartennutzer und man hat die Zeit, das Problem in Ruhe anzugehen.

Aaaaaaaber: ich arbeite so, andere arbeiten anders. Ich will niemanden von irgendwas überzeugen. Gerade bei OSM gibt es zumeist mehrere Wege zum Ziel.

Also als Kennzeichnung "wird regulär nicht dargestellt", mit der verbleibenden Möglichkeit von Spezialprogrammen, diese geografischen Objekte doch auszuwerten. Man kann so also Semantik verbauen, ohne die Optik einer Karte zu beschädigen.

Das funktioniert jetzt schon, indem Du Schlüssel benutzt, die von Renderer und/oder Routern nicht ausgewertet werden.

Ich sehe keinen Gewinn bei einem neuen Tag. Ich sehe aber die Probleme, die Du haben wirst, alle Verwalter von Karten davon zu überzeugen, das Handling Deines neuen Tags zu integrieren. Weil es Aufwand macht und keinen Vorteil bringt. Meine Kristallkugel sagt mir, dass Dein Versuch in großer Frustration enden wird. 🤔

Aber wie immer: ich will Dich natürlich nicht davon abhalten. Arbeite ein Konzept aus, stell es vor, mail alle Verwalter von Karten an, und versuche, jeden einzelnen davon zu überzeugen. Viel Glück!

Gruß Wolf

Als Beispiel wie es aussieht wenn über den Platz auch noch (beschriftete) Straßen laufen: http://www.openstreetmap.org/#map=19/48.90506/9.08086

Nicht von mir, hab es aber auch nicht rausgemacht, da mir die Problematik doch irgendwie einleuchtete. Und das mit der Beschriftung der Straßen wäre halt eben auch noch ein Problem. Vielleicht sieht man die Straße nicht, aber irgendwo her sollte ja auch noch der Name kommen. Ob der Router weiß, dass er diesen von der einschließenden area holen soll? 🙂

Schina02 wrote:

Als Beispiel wie es aussieht wenn über den Platz auch noch (beschriftete) Straßen laufen: http://www.openstreetmap.org/#map=19/48.90506/9.08086

Komisch, wenn ich nichts übersehen habe ist das genauso getaggt wie hier: http://www.openstreetmap.org/#map=19/50.97938/11.32984
Wird aber unterschiedlich gerendert. Kann ma jemand mein Brett abnehmen?

Nahmd,

MKnight wrote:

Schina02 wrote:

Als Beispiel wie es aussieht wenn über den Platz auch noch (beschriftete) Straßen laufen: http://www.openstreetmap.org/#map=19/48.90506/9.08086

Komisch, wenn ich nichts übersehen habe ist das genauso getaggt wie hier: http://www.openstreetmap.org/#map=19/50.97938/11.32984
Wird aber unterschiedlich gerendert. Kann ma jemand mein Brett abnehmen?

Im ersten Fall haben die Straßen eine größere Id als die Fläche, im zweiten hat die Fläche die größere Id.
Liegt es möglicherweise an der Zeichenreihenfolge?

Gruß Wolf

MKnight wrote:

Schina02 wrote:

Als Beispiel wie es aussieht wenn über den Platz auch noch (beschriftete) Straßen laufen: http://www.openstreetmap.org/#map=19/48.90506/9.08086

Komisch, wenn ich nichts übersehen habe ist das genauso getaggt wie hier: http://www.openstreetmap.org/#map=19/50.97938/11.32984
Wird aber unterschiedlich gerendert. Kann ma jemand mein Brett abnehmen?

Beim einen haben die Wege Namen, beim anderen nicht.
Unbenannte Wege werden auch von Mapnik noch nicht beschriftet (muß ein Bug sein).

oh, danke, ganz übersehen.

Moin,

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

- ob ein Präprozessor alle Fälle abdecken kann, ist unklar (aneinandergrenzende Flächen, Hindernisse in der Platzfläche, Treppen, die im Inneren des Platzes beginnen).
Für überbreite Freitreppen haben wir noch nicht einmal ein etabliertes Datenmodell.

- viele innerstädtische Plätze haben so viele Beete, Stadtmöbel, Brunnen, Felder von Fahrradbügeln, etc., dass praktisch nur wenige Wege benutzt werden

- ein zusätzliches Tag ist einfach in die Router zu integrieren. Ein vorgeschalteter Präprozessor erfordert viel größere Anpassungen in der Datenverarbeitung.

- das Konzept der virtuellen Wege ist auf andere Probleme anwendbar (Wanderwege über den Strand, Almwiese, u.ä., Querungen von Grünstreifen zwischen Straße und Fußweg, Treppen in der Mitte eines Bahnsteigs). Auch für Wasserwanderwege braucht man manchmal eine Verbindung zwischen Einsetzpunkt am Ufer und der Flussmitte.

Der Taggingvorschlag "highway=virtual" mit passenden access-Tags [1] gefällt mir am besten.
Für Router genügt es, diesen Wert analog zu "highway=path" zu behandeln, alle anderen Anwendungen wären nicht betroffen.
Für nachfolgende Mapper ist es vermutlich selbsterklärend.

[1] 4.11.13 Wolfgang Hinsch in talk:de - "path am Strand fuer den Router ..."

Nahmd,

seawolff wrote:

Der Taggingvorschlag "highway=virtual" mit passenden access-Tags [1] gefällt mir am besten.

[×] dafür

Ich hatte an “highway=pathless” gedacht, aber “highway=virtual” ist besser.

Es braucht allerdings ein bisschen™ Zeit, bis die rund 150.000 highway-Flächen in der OSM-DB mit virtuellen Wegen ausgestattet sind. Deshalb spricht auch nichts gegen Preprocessing für Routing-Anwendungen. Das verträgt sich sogar sehr gut, wenn sobald in einer Verkehrsfläche Wege gefunden werden, keine weiteren Wege ergänzt werden.

Gruß Wolf

Netzwolf wrote:

... aber “highway=virtual” ist besser.

Es braucht allerdings ein bisschen™ Zeit, bis die rund 150.000 highway-Flächen in der OSM-DB mit virtuellen Wegen ausgestattet sind. Deshalb spricht auch nichts gegen Preprocessing für Routing-Anwendungen. Das verträgt sich sogar sehr gut, wenn sobald in einer Verkehrsfläche Wege gefunden werden, keine weiteren Wege ergänzt werden.

Gruß Wolf

Ich finde highway=virtual auch konkret einsetzbar für Fahrspuren (besser als die unsichtbaren, maschinenlesbare lanes) Dann könnten NAVIS diese ignorieren - Router und Karten würden es "Menschen lesbar" anzeigen. Und auch bei der Ergänzung von highway:area dürften keine Probleme auftreten.

geri-oc wrote:

Netzwolf wrote:

... aber “highway=virtual” ist besser.

Ich finde highway=virtual auch konkret einsetzbar für Fahrspuren (besser als die unsichtbaren, maschinenlesbare lanes) ...

Wenn man das highway-Tag dafür nutzt, verliert man aber die Möglichkeit, den Typ des Weges nochmal zu unterscheiden. Wenn ich mit Routing z.B. auf "highway=path" wandern möchte, auf "highway=footway" aber nicht (oder service, track... oder was sonst so als Fläche eingetragen ist), stehe ich bei "highway=virtual" ziemlich ratlos da. Da Router sonst relativ wenige Möglichkeiten haben, Wege zu unterscheiden sind sie auf highway schon sehr angewiesen.

Alternative hab ich aber auch keine anzubieten, weil ich eigentlich auch keine Tags mag, die andere für ungültig erklären (also sowas wie "existiert_aber_gar_nicht=yes")

Grüße, Max

maxbe wrote:

Wenn man das highway-Tag dafür nutzt, verliert man aber die Möglichkeit, den Typ des Weges nochmal zu unterscheiden. Wenn ich mit Routing z.B. auf "highway=path" wandern möchte, auf "highway=footway" aber nicht (oder service, track... oder was sonst so als Fläche eingetragen ist), stehe ich bei "highway=virtual" ziemlich ratlos da.

Gleiches Schema wie bei construction: highway=virtual, virtual=footway.

geri-oc wrote:

Ich finde highway=virtual auch konkret einsetzbar für Fahrspuren.

Das heißt bei Fußgänger-Areas sollen Navis diese nutzen, bei Abbiegespuren aber nicht?

Da wird mir zuviel in einen Topf geworfen.

Abbiegespuren sind reale Objekte, aber ebenkeine Fahrbahnen. 😎

seawolff wrote:

Der Taggingvorschlag "highway=virtual" mit passenden access-Tags [1] gefällt mir am besten.
Für Router genügt es, diesen Wert analog zu "highway=path" zu behandeln, alle anderen Anwendungen wären nicht betroffen.
Für nachfolgende Mapper ist es vermutlich selbsterklärend.

Das finde ich einen vertretbaren Kompromiss - zumindest wäre ein eigenes Tag deutlich erträglicher als die Zweckentfremdung bestehender Tags. (Allerdings würde ich virtual:highway=* vorziehen, vergleichbar mit der neuen disused-Syntax, aber das ist eher eine Detailfrage.)

Idealfall ist meiner Meinung nach dennoch der Einbau in die Router. In dieser Diskussion wurde einmal die "kombinatorische Explosion" als Argument gegen eine Automatisierung angesprochen. Ich sehe das im Gegenteil als Argument gegen manuelle Einträge - es werden ziemlich viele virtuelle Ways nötig, die eine Software deutlich effizienter produzieren kann als ein Mapper.

Ich würde diese Hilfswege daher eher als temporäre "Stützräder" sehen, bis gängige Router es von selber können.

Netzwolf wrote:

Für den Router taggen ist böse.

Gibt's eigentlich kein passendes Tag für einen Holzplatz?
Die können Teilweise schon richtig groß sein und sind nur weiße Flecken hier

Tordanik wrote:

seawolff wrote:

Der Taggingvorschlag "highway=virtual" mit passenden access-Tags [1] gefällt mir am besten.
Für Router genügt es, diesen Wert analog zu "highway=path" zu behandeln, alle anderen Anwendungen wären nicht betroffen. ...

Das finde ich einen vertretbaren Kompromiss - zumindest wäre ein eigenes Tag deutlich erträglicher als die Zweckentfremdung bestehender Tags. (...)

Idealfall ist meiner Meinung nach dennoch der Einbau in die Router. In dieser Diskussion wurde einmal die "kombinatorische Explosion" als Argument gegen eine Automatisierung angesprochen. Ich sehe das im Gegenteil als Argument gegen manuelle Einträge - es werden ziemlich viele virtuelle Ways nötig, die eine Software deutlich effizienter produzieren kann als ein Mapper.

Ich würde diese Hilfswege daher eher als temporäre "Stützräder" sehen, bis gängige Router es von selber können.

Nun ja, nicht jedes Blumenbeet oder anderes Hinderniss auf einer Fläche ist zur Zeit bei OSM eingetragen. Von daher kann ein Mensch mit seiner Kenntnis + einem guten Luftbild, da oft einen besseren Job machen.

Es gibt übrigens durchaus auch den Fall, wo Vorzugswege auf einer Fläche explizit hervorgehoben oder markiert sind. In so einem Fall würde ich die Wege explizit mit ihrem üblichen / normalen Wert eintragen.

Eine 'kombinatorische Explosion' braucht es nur, wenn man die kürzesten Wege ermitteln will. Ein Mensch wird eher dazu neigen, einfache statt kürzeste Wegführungen zu erfassen. Dabei wird er zum Beispiel auch die Marktstände berücksichtigen, die dort mehrmals in der Woche stehen. Ein Automatismus, kann das nur, wenn die alle als erkennbares Hindernis eingetragen sind.

highway=virtual + virtual=path/footway/service/... scheint mir eine gute Lösung zu sein.
Gegen virtual:highway=path/footway/service/... hätte ich aber auch keine Einwände.

Edbert (EvanE)

chris66 wrote:

...
Das heißt bei Fußgänger-Areas sollen Navis diese nutzen, bei Abbiegespuren aber nicht?

Da wird mir zuviel in einen Topf geworfen.

Abbiegespuren sind reale Objekte, aber ebenkeine Fahrbahnen. 😎

Navis können diese Abspiegespuren nutzen - eben weil es reale Objekte sind. Und sie sind wie Fahrbahnen gebaut.

- ist m.E. auf alle Fälle besser als
turn:lanes=slight_left|slight_left;slight_right|slight_right
destination:lanes=A|A;B|B

Aber wollen sie es?

Da Router sonst relativ wenige Möglichkeiten haben, Wege zu unterscheiden sind sie auf highway schon sehr angewiesen.

Eben - aber warum verwenden sie lanes (und siehe oben) - weil kein (passender) highway vorhanden ist?
Oder wir verwenden für alle "Verbindungsspuren" highway=*_link -> highway=footway_link in den Flächen?

(Ich habe nichts gegen lanes - solange sie die Anzahl der Spuren auf der (gleichen) Fahrbahn angeben.)

geri-oc wrote:

Navis können diese Abspiegespuren nutzen - eben weil es reale Objekte sind. Und sie sind wie Fahrbahnen gebaut.
- ist m.E. auf alle Fälle besser als
turn:lanes=slight_left|slight_left;slight_right|slight_right
destination:lanes=A|A;B|B

Und das Navi weiß woher, dass du von einer Spur auf die andere wechseln darfst? Einer der Gründe, warum nur baulich getrennte Fahrspuren als separate Highways erfasst werden, ist doch, dass man ansonsten zwischen den Spuren wechseln kann.

Nadjita wrote:

geri-oc wrote:

Navis können diese Abspiegespuren nutzen - eben weil es reale Objekte sind. Und sie sind wie Fahrbahnen gebaut.
- ist m.E. auf alle Fälle besser als
turn:lanes=slight_left|slight_left;slight_right|slight_right
destination:lanes=A|A;B|B

Und das Navi weiß woher, dass du von einer Spur auf die andere wechseln darfst? Einer der Gründe, warum nur baulich getrennte Fahrspuren als separate Highways erfasst werden, ist doch, dass man ansonsten zwischen den Spuren wechseln kann.

In dem es wie ein Routingprogramm die nächsten Routenpunkte einbezieht - aus der Linksabbiegerspur darfst du nur verkehrswidrig in eine andere Spur wechseln - es sei denn, du meinst es gibt zwei Linksabbieger und ich kann wählen in welche ich möchte - hier wäre lanes=2 richtig an einem highway=*_link -(falls es nicht vorgegeben ist, die ganz linke zum Wenden oder in eine andere Fahrtrichtung wie die andere Linksabiegespur).

Ich kenne nur Karte und Router - was und wie Navis rechnen, weiß ich nicht.

Ich frage, weil Du oben schriebst, Du wollest die Dinger auch für Fahrspuren einsetzen und da sehe ich - genau wie bei Abbiegespuren - keinen Sinn, eben weil man, so lange man munter wechseln kann, die einzelnen Lanes nicht trennen darf.

EvanE wrote:

highway=virtual + virtual=path/footway/service/... scheint mir eine gute Lösung zu sein.
Gegen virtual:highway=path/footway/service/... hätte ich aber auch keine Einwände.

Hm. Hm. Widerstrebt mir immer noch irgendwie (weil es das Zeug in der Realität nicht gibt). Aber ich trag weiter meine Bedenken mit mir rum, und ihr baut einfach tolle Router :-)

Man muss ja nicht immer einer Meinung sein. Ein Veto leg ich garantiert nicht ein (selbst wenn ich eins hätte, nicht).

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.

gormo wrote:

EvanE wrote:

highway=virtual + virtual=path/footway/service/... scheint mir eine gute Lösung zu sein.
Gegen virtual:highway=path/footway/service/... hätte ich aber auch keine Einwände.

Hm. Hm. Widerstrebt mir immer noch irgendwie (weil es das Zeug in der Realität nicht gibt). Aber ich trag weiter meine Bedenken mit mir rum, und ihr baut einfach tolle Router :-)

Wir haben hier zwei Problemklassen:
- Ein highway=* als Fläche, damit kommen Router insoweit klar,
als dass sie den Rand als Route verwenden.
Das kann man mit viruellen Wegen verbessern.
- Flächen wie Strand, Wiese, Geröll, Gletscher, die ein Router normaler
weise nicht mal als Umriss zum Routen verwendet. Hier braucht es einen
virtuellen Weg, damit der Router überhaupt etwas zum Routen hat.

Für den ersten Fall kann man auf eine algorithmische Lösung hoffen. Für den zweiten Fall ist das in noch weiterer Ferne als es beim ersten Fall bereits ist.

Beide Fälle kann man mit virtuellen Wegen als Provisorium für die Zwischenzeit überbrücken.

Edbert (EvanE)

Netzwolf wrote:

Nahmd,
Für den Router taggen ist böse.
Edit: Kommentar zum Router ergänzt.

Dann schau dir die Situation mal genau an, zoome heraus auf den Berg.
Richtig böse ist, wenn genau diese logische Wegverbindung fehlen würde
und einen Bergwanderer 1 km Umweg laufen lässt (wenn er so dumm ist, sich alleine auf OSM-Routing zu verlassen).
Ein Holzplatz ist noch nicht automatisch begehbar. Der könnte ja auch voller Holz gestapelt sein.

Wenn du mal genau hinschaust,
https://maps.google.de/maps?q=47.6934+1 … 5&t=h&z=19
dann ist es einfach nur ein logischer Weg, der so einen Platz durchkreuzt.

Man mappt so, dass die Welt möglichst logisch beschrieben wird.

Das einzige Manko ist hier die Optik, dass man den logischen Weg nicht über den
Platz gezeichnet haben will. Also eine "visible=no" Eigenschaft ist gewünscht.

Es gibt viele Fälle, in denen Plätze von Wegen durchkreuzt werden.
Auf Marktplätzen werden die manchmal nur im Pflaster durch eine Vertiefung angedeutet.
Es macht also Sinn, sowohl diese angedeuteten Wege zu mappen
als auch den ganzen Platz, der rechtlich genauso befahrbar ist.
Ein Router könnte sich dann daraus die beste Routing-Strategie herauspicken.

Man könnte nun eine neue logische Klasse der virtuellen Wege einführen,
oder einfach das bewährte Schema (mit allen Features) belassen und nur
die Sichtbarkeit für bestimmte Segmente deaktivieren.

Ein Sichtbarkeit-Flag hätte den Vorteil, dass es generell für jeden Objekt-Typ anwendbar wäre
(Fußpfad, Fahrradweg, Gebäude) und die normale Logik erhalten bleibt.
Man muss dann nicht für jeden Fall eine eigene virtuelle Klasse einführen
(virtuelle Fußwege, virtuelle Straßen, virtuelle Gebäude, virtuelle Flüsse, virtuelle ...).
Das muss ja auch alles wieder irgendwie verwaltet und differenziert werden.
Ein einfacher Sichtbarkeits-Ein/Aus-Schalter wäre praktischer und weniger aufwendig
(nur ein Flag im Renderer). Der Renderer muss sowieso bei jedem Objekt Entscheidungen treffen,
ob es in bestimmten Situationen, Konfigurationen oder Zoom-Leveln erscheint oder nicht.

openzzz wrote:

[Dann schau dir die Situation mal genau an, zoome heraus auf den Berg.

Schau doch mal, wer das gemapt hat...

openzzz wrote:

Ein Holzplatz ist noch nicht automatisch begehbar. Der könnte ja auch voller Holz gestapelt sein.

Wenn da ein highway=* steht, muss man davon ausgehen, dass irgendwer da rumlaufen oder fahren kann. Genauere Details dazu stehen in access, surface ...

openzzz wrote:

Das einzige Manko ist hier die Optik, dass man den logischen Weg nicht über den Platz gezeichnet haben will. Also eine "visible=no" Eigenschaft ist gewünscht.

Ich glaube, Du solltest Dich von der Vorstellung trennen, dass Renderer das machen, was der Mapper ihnen vorschreibt. Für manche ist eine Gemeindegrenze unsichtbar, oder unterirdische Pipelines, oder Postleitzahlen, andere wollen das darstellen. Die kriegt man nicht mit einem visible-Flag für alle Objekte unter einen Hut. Da muss man schon für jedes einzelne Tag dem Renderer die Chance geben das unerwünschte auszublenden ("Grenzen bis maximal Bundesland", "Pipelines nur wenn sie oberirdisch liegen", "Wege nur wenn sie als Spur vorhanden sind"...) und für Wege über Flächen bietet sich eben highway=virtual an...

Grüße, Max

maxbe wrote:

Ich glaube, Du solltest Dich von der Vorstellung trennen, dass Renderer das machen, was der Mapper ihnen vorschreibt. Für manche ist eine Gemeindegrenze unsichtbar, oder unterirdische Pipelines, oder Postleitzahlen, andere wollen das darstellen. Die kriegt man nicht mit einem visible-Flag für alle Objekte unter einen Hut. Da muss man schon für jedes einzelne Tag dem Renderer die Chance geben das unerwünschte auszublenden ("Grenzen bis maximal Bundesland", "Pipelines nur wenn sie oberirdisch liegen", "Wege nur wenn sie als Spur vorhanden sind"...) und für Wege über Flächen bietet sich eben highway=virtual an...
Grüße, Max

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. Wenn ein Renderer sich nicht darum schert und eine schlechtere Optik riskiert ist das sein Problem. Man hat ihn gewarnt .. 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.

Kennst du das nicht von Word: "weiche" zu "harte" Formatierung? Generell wird empfohlen, Formatvorlagen zu nehmen, damit ein Dokument später leichter wieder in eine andere Vorlage gepresst werden kann. (z.B. Überschrift 1 solle dann für ein anderes Doc kursiv statt fett dargestellt werden, geht ruckzuck mit einer Vorlagenformatierung). Trotzdem macht es immer noch Sinn, harte Formatierungen zuzulassen, wenn der Autor eben bestimmte Worte ganz diktatorisch anders formatieren will, als die Vorlage es sonst macht. Manche Dinge können Maschinen eben nicht gut entscheiden. Man kann harte Formatierung natürlich missbrauchen, in meinen Augen aber kein Grund, diese Ausdrucksmöglichkeiten nicht zuzulassen.

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.

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,

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

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

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

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

Gruß Wolf

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 😎

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

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.

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.

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

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

Edit: Paper falsch zitiert.

Nahmd,

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

couchmapper wrote:

Ja. 😎

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:

• 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:

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

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

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.

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.

Moins,

ich hatte dieses Déjà-vu – schon 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... 😉

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

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

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?

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

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.

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

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: 🙂

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.

chris66 wrote:

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

http://thumbs.picr.de/16440460wp.jpg

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.

Nadjita wrote:

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.

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.

Tordanik wrote:

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?

Weil ich es übersichtlich halten wollte. 😉
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.

Wenn wir alle anfangen, unsere eigenen Ideen auf virtual:* zu projizieren, dann ergibt das ein Chaos.

Ja, die Gefahr besteht durchaus.

couchmapper wrote:

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

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)

Die Linien, die zu anschlusslosen Ecken der Flächen führen kapiere ich nicht.

chris66 wrote:

Die Linien, die zu anschlusslosen Ecken der Flächen führen kapiere ich nicht.

Ging es nicht genau darum?

In der unteren Grafik rechts sehe ich keine Linien zu nicht angeschlossen Ecken.
In dem oberen Beispiel Jakobsplatz schon. Hm...

Mal was anderes:

Hat schon jemand drüber nachgedacht, wie die Routinganweisung in solchen Fällen wäre?

things-change wrote:

chris66 wrote:

Die Linien, die zu anschlusslosen Ecken der Flächen führen kapiere ich nicht.

Ging es nicht genau darum?

In der unteren Grafik rechts sehe ich keine Linien zu nicht angeschlossen Ecken.
In dem oberen Beispiel Jakobsplatz schon. Hm...

Zum Jakobsplatz hat maxbe ja schon geschrieben, dass das "mit der Besonderheit eines Weges mit Tags als outer einer Relation zu tun" hat und bei dem Marstallplatz-Beispiel ist die westliche der beiden Flächen teilweise von einem Gebäude umgeben, was dann als "interessanter Punkt", "wo andere Wege den Platz berührten" zählt. Oh, und das Marstallplatz-Bild zeigt zweimal die selbe Stelle als vorher/nachher-Vergleich 😉

things-change wrote:

Hat schon jemand drüber nachgedacht, wie die Routinganweisung in solchen Fällen wäre?

Nehmen Sie den vierten virtuellen Weg von links. 😎

rayquaza wrote:

Zum Jakobsplatz hat maxbe ja schon geschrieben, dass das "mit der Besonderheit eines Weges mit Tags als outer einer Relation zu tun" hat

Kurz zur Erklärung: Ich hatte mal einen schönen Graphen, bevor ich hiermit angefangen hatte. Der wird von osm2po aufgebaut. Das hat mir den Weg 31988047 (highway=pedestrian) eingebaut.

Relationen kann osm2po leider nicht. Die werden nachträglich aus einer osm2pgsql-Datenbank nachgetragen weil osm2pgsql kann das. Allerdings kann das so gut mit Relationen umgehen, dass es die Tags von outer ways auf die Relation überträgt, falls das sinnvoll ist. Die darf man dann kein zweites Mal importieren, weil die outer ja schon abgearbeitet wurden.

Für die Bastelei hier muss ich auf die osm2pgsql-Datenbank zurückgreifen, die kennt Häuser, Bäume und Flächen (kennt ein Router alles nicht, der kennt nur Striche und Knoten). Und wenn ich dann die Kreuzungen des Umringes der Relation 152653 (die dank osm2pgsql inzwischen auch ein highway=pedestrian geworden ist) mit anderen Wegen suche, stolper ich an jedem Eck über den Weg 31988047 im Routinggraphen und markiere den als "Kreuzung zwischen R152653 und W31988047".

Im echten Betrieb würde man das aus einer Datenbank holen, oder wenigstens aus einer OSM-Datei, die zeitlich zum Import des Graphen passt, oder wenigstens die gleiche Projektion für Flächensuche und Routing verwenden 😉 Aber zum Mal-Schnell-Rumprobieren baue ich mir kein solches System auf. Inzwischen ist der Graph auch schon ganz schön buggy durch meine wüst drauflos programmierten Versuche. Ich hab z.B. keine Erklärung dafür, warum in der westlichen Fläche noch ein paar Punkte in der Mitte übrigbleiben (das ist ein Brunnen, der als Hindernis gilt). Ist aber egal, in zwei Wochen gibts wieder einen neuen Routinggraphen,

Grüße, Max

Wenn ich z.B. eine 10km Route über diese Fläche von meinetwegen 50m Weg berechnen lasse, wie hoch hoch ist denn dann etwa der Rechenaufwand vom Platz im Verhältnis zum Rest der Strecke?
Kann mir das nicht so richtig vorstellen.

things-change wrote:

Wenn ich z.B. eine 10km Route über diese Fläche von meinetwegen 50m Weg berechnen lasse, wie hoch hoch ist denn dann etwa der Rechenaufwand vom Platz im Verhältnis zum Rest der Strecke?

Abschätzen kann ich die Rechenzeit nicht, nur die Datenmenge mit bereits gemappten Dingen vergleichen: Die beiden Flächen Jakobs/Sebastiansplatz da oben haben nach dem Ausdünnen zusammen 134 Wege. Das ist so etwa die Größenordnung eines detaillierten Parks (102 Wege) oder 1/3 eines grösseren Friedhofs (449 Wege), oder 1/5 eines Dorfes (697 Wege).

Du übrigens musst nicht mal über den Platz geroutet werden, um davon ausgebremst zu werden. es reicht wenn du in der Nähe bist, der Router muss ja mindestens nachsehen, ob der Weg eine kürzere Strecke bietet.

Im Moment seh ich allerdings nicht mal eine Chance, diese Wege performant genug zu erzeugen... 😉

things-change wrote:

Hat schon jemand drüber nachgedacht, wie die Routinganweisung in solchen Fällen wäre?

OsmAnd kann Straßennamen ansagen. Also falls der aktuelle Standort auf einer straßenlosen Fläche liegt, wäre so etwas denkbar: "verlassen Sie den Markusplatz nach Norden in die Calle de la Rizza". Platzname und Name der Anschlußstraße sind gespeichert.

Das dürfte für den Normalfall reichen. Üblicherweise sind Plätze (Marktplätze) nicht so komplex strukturiert. Das Wichtigste ist die Vernetzung der entry/exit-nodes der Fläche. Mit einer Metrik entsprechend der Linienlänge würde man in den meisten Fällen vernünftige Routen erhalten.

Ein exaktes Routing mit kürzestem Pfad ist mit den hier diskutierten vorausberechneten virtuellen Wegen sowieso nicht möglich. Denn dann müsste man für jeden beliebigen Standort auf dem Platz ein eigenes Netz berechnen und speichern. Das wäre unsinnig und ein Performancekiller. Mann könnte es auch kombinieren: für den lokalen Platz verzichtet der Router auf die Nutzung virtueller Wege und berechnet geometrisch die kürzeste Route vom momentanen Standort zur nächsten Anschlußstraße. Über entfernte Flächen wird vereinfacht mit virtuellen Wegen geroutet, was lokal noch unbedeutsam ist. Die Zahl der Wegekombinationen beim Drüberrouten ist klein, nur (N-1)! bei N Zu-/Abgängen mit jeweils nur einem Kostenfaktor entsprechend der Weglänge.

Für Radfahrer könnte man solche Areas auch komplett auf eine einzige Node schrumpfen, weil die Querungszeit praktisch unbedeutsam ist im Vergleich zu einer längeren Gesamtroute.

openzzz wrote:

Die Zahl der Wegekombinationen beim Drüberrouten ist klein, nur (N-1)! bei N Zu-/Abgängen mit jeweils nur einem Kostenfaktor entsprechend der Weglänge.

Ohne Berücksichtigung der Wegrichtung sollte das wohl eher (n*(n-1))/2 sein, oder? Keine Ahnung, wo da die Fakultät herkommen soll.

couchmapper wrote:

openzzz wrote:

Die Zahl der Wegekombinationen beim Drüberrouten ist klein, nur (N-1)! bei N Zu-/Abgängen mit jeweils nur einem Kostenfaktor entsprechend der Weglänge.

Ohne Berücksichtigung der Wegrichtung sollte das wohl eher (n*(n-1))/2 sein, oder? Keine Ahnung, wo da die Fakultät herkommen soll.

Ach stimmt, Fakultät war falsch, hatte wohl multipliziert statt addiert: (N-1)+(N-2)+(N-3)+...+1 ist die Zahl der Wege. N ist die Zahl der Zugangspunte.
Dann gilt die gaußsche Summenformel wie von dir beschrieben.

Die Zahl ist aber auch sehr klein.
Was ich sagen wollte: wie das Verbindungsnetz intern aussieht muss dann für das Drüberrouten gar nicht gespeichert werden. Es reicht, für jede Kombination von entry/exit node einen Metrikwert zu speichern. Die lokale Route am Platz kann ein Smartphone dann immer noch recht schnell vollständig berechnen, in Abhängigkeit vom Standort auf dem Platz (zusätzliche Node im Netz), muss es aber nicht gleichzeitig für alle Plätze auf der Route machen. N ist dann zwar viel größer, nicht die Zahl der Zugangswege, sondern aller Polygonpunkte, aber von der Smartphone-CPU sicher noch beherrschbar.

maxbe wrote:

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

Letztendlich erfüllt der Node zwischen Fußweg (Linie) und Platz (Fläche) die Funktion einer Kreuzung. Solche Kreuzungen werden doch ohnehin mit einem entsprechenden Tag versehen (sollten sie zu mindestens, oder?)

Davon ausgehend reduziert sich doch die mögliche Wegezahl über diesen Platz auf die möglichen Anschlußpunkte mit dem highway=crossing - Tag?

von Routing keine Ahnung habend und nur so als Gedankenfetzen in den Raum werfend,

Sven

streckenkundler wrote:

Letztendlich erfüllt der Node zwischen Fußweg (Linie) und Platz (Fläche) die Funktion einer Kreuzung. Solche Kreuzungen werden doch ohnehin mit einem entsprechenden Tag versehen (sollten sie zu mindestens, oder?)

Nö, es ist ein "interessanter Punkt" fürs Routing, aber ein besonderes Tag darf man da nicht erwarten.

Weder beim Eintragen noch beim Auswerten ist so eine Verbindung ein besonderer Punkt, sondern eine ganz normale Verbindung zweier Wege, wie jede andere Einmündung auch. Der Mapper und der Renderer sind zufrieden, weil sie die Verbindung von Weg und Fläche haben. Der Router eigentlich auch, der sieht das als Kreuzungspunkt, von wo aus er den Weg erreichen kann und die Fläche. Letztere bezieht er zumindest mit der "immer an der Wand lang"-Methode in seine Wegfindung ein.

Grüße, Max

Moins,

streckenkundler wrote:

Davon ausgehend reduziert sich doch die mögliche Wegezahl über diesen Platz auf die möglichen Anschlußpunkte mit dem highway=crossing - Tag?

Diese Anschlusspunkte zu finden, ist ein Schritt bei der Definition der Aufgabe "virtuelle Wege über einen Platz bestimmen". Sie sind nicht irgendwie markiert, kann kann aber leicht Punkte herraussuchen, die sowohl zur Begrenzung einer Highway=*-Fläche gehören also auch zu einer Highhway-Linie.

Ich hab da mal ein paar SVGs vorbereitet: w31988047, w227012666 und r1633555.

(aus der OSM-Datenbank: Highway-Linien: rot, Highwayflächen: gelb mit blauem Rand, Hindernisse: schwarz; algorithmisch ergänzt: die Anschlusspunkte: blaue Kringel)

Die Aufgabe besteht jetzt darin, (virtuelle) Wege zu ergänzen, über die je zwei der blauen Kringel optimal verbunden sind.

BTW: aneinandergrenzende Flächen sind eine echte Herausforderung: Wenn die Geschwindigkeit auf Nachbarflächen gleich ist, besteht die triviale Lösung darin, die beiden Flächen zu verschmelzen; man muss aber den Fall besonders berücksichtigen, dass mehrere Flächen zusammen einen Ring bilden: nehmen wir eine “^” und eine “V”-förmige Fläche und setzen erstere auf zweitere, so bekommen wir eine “O”-förmige Fläche mit einer Insel darin, es entsteht also ein inner. Das ist nichts Weltbewegendes, man darf es nur nicht übersehen.

Wenn die Flächen unterschiedliches Tagging haben und damit möglicherweise mit unterschiedlichen Geschwingkeiten durchlaufen werden, hängt der optimale Übertrittspunkt auf einer Grenzlinie zwischen zwei Flächen vom Verhältnis der Geschwindingkeiten in den beiden Flächen ab (Schulphysik: Lichtbrechung), und virtuelle Wege müssten für jedes der in Frage kommenden Verhältnisse getrennt berechnet werden. Das ist natürlich Overkill. Wird man nicht machen wollen.

Die einfache Möglichkeit bei benachbarten Flächen ist ein synthetischer Übangspunkt in der Mitte der gemeinsamen Grenze. Das liefert nicht die optimale Routen, funktioniert dafür aber in allen Fällen.

Gruß Wolf

Nahmd,

chris66 wrote:

Die Linien, die zu anschlusslosen Ecken der Flächen führen kapiere ich nicht.

Das passiert, wenn man alles verbindet, was nicht bei drei auf'm Baum ist.

Aufgabe ist, die rot gekringelten Anschlusspunkte über die Fläche zu verbinden. Die triviale Lösung erzeugt alle lokal sinnvollen Verbindungen, das sind weniger als in obigem Beispiel, aber immer noch zu viel. Die Routing-Engine würde hier bereits die optimale Verbindung finden, aber wegen der enthaltenen überflüssigen Wege Rechenzeit vergeuden. Etwas zeitaufwendig kann man mit einem sehr einfachen Algorithmus die überflüssigen Wege filtern und erhält ein überschaubares Ergebnis, über dass sich Routing-Engine und Nutzer freuen. 🙂

Unbedingt nötig ist das Filtern bei stark strukturierten Gebieten mit wenig Zugängen. 😎

Fies sind einfache Flächen mit vielen Zugängen, denn da bleiben trotz Filtern zu viele Wege über. Der Filter kann keinen Weg mehr tilgen, wenn jeder Weg Teil der optimalen Verbindung zwischen mindestens zwei Anschlusspunkten ist.

Hier ist ein Algorithmus gefragt, dem man Umwege erlaubt in Prozent oder in Metern, und der dann hinreichend geschickt möglichst viele Wege tilgt oder zusammenfasst, ohne den erlaubten Umweg zu überschreiten. Das ist mir aber zu heftig. 🙄

Gruß Wolf

Netzwolf wrote:

Die einfache Möglichkeit bei benachbarten Flächen ist ein synthetischer Übangspunkt in der Mitte der gemeinsamen Grenze. Das liefert nicht die optimale Routen, funktioniert dafür aber in allen Fällen.

Sollte doch eigentlich reichen, erstmal alle gemeinsamen Punkta als Zugänge zu betrachten (also genau wie bei angrenzenden Wegen). Wenn man wirklich mit langen Teilstücken rechnet, kann man auf denen ja virtuelle Verbindungspunkte einsetzen, wenn sie eine bestimmte Länge überschreiten. Ich denke, so genau, dass man unterschiedliche Geschwindigkeiten betrachtet, müssen wir nicht sein, zumal sich Geschwindigkeiten selten sehr stark unterscheiden dürften für das gleiche Fortbewegungsmittel auf zwei angrenzenden Flächen, die groß genug sind, als dass das wirklich einen Unterschied machen würde.

Netzwolf wrote:

Fies sind einfache Flächen mit vielen Zugängen, [...]
Hier ist ein Algorithmus gefragt, dem man Umwege erlaubt in Prozent oder in Metern, und der dann hinreichend geschickt möglichst viele Wege tilgt oder zusammenfasst, ohne den erlaubten Umweg zu überschreiten. Das ist mir aber zu heftig. 🙄

Vielleicht könnte man auch vor dem Finden der lokalen Verbindungen versuchen, bei Flächen mit vielen Zugängen nah beieinanderliegende Zugänge zunächst mit einem virtuellen Punkt zu verbinden und dann nurnoch diesen zu betrachten. Funktioniert wahrscheinlich nicht besonders gut, wenn man die ganze Sahara als Fläche betrachtet, auf der man routen könnte, aber ich könnte mir vorstellen, dass es für die meisten Fälle tut - und dass für die anderen andere Algorithmen auch nicht unbedingt großartig funktionieren.

Nahmd,

errt wrote:

Netzwolf wrote:

Die einfache Möglichkeit bei benachbarten Flächen ist ein synthetischer Übangspunkt in der Mitte der gemeinsamen Grenze. Das liefert nicht die optimale Routen, funktioniert dafür aber in allen Fällen.

Sollte doch eigentlich reichen, erstmal alle gemeinsamen Punkta als Zugänge zu betrachten (also genau wie bei angrenzenden Wegen).

Es sieht reichlich merkwürdig aus, wenn man zu einer Platzecke laufen muss statt über die freie Fläche, um einen Nachbarplatz betreten zu können: daher mein Vorschlag des synthetischen Übergangspunktes in der Mitte der Trennlinie.

Bei den Demo-SVGs mache ich mir's einfach: ich ignoriere während der Wegsuche die Grenze zwischen benachbarten Plätzen und laufe gerade rüber. Dafür muss man beim Bereitstellen der Daten für den Platzwegsucher darauf achten, dass nicht auf einem Radln erlaubt ist und auf dem anderen nicht.

Vielleicht könnte man auch vor dem Finden der lokalen Verbindungen versuchen, bei Flächen mit vielen Zugängen nah beieinanderliegende Zugänge zunächst mit einem virtuellen Punkt zu verbinden und dann nurnoch diesen zu betrachten.

Oder ein beliebiges anderes Verfahren. Hier hat es beliebig viele Möglichkeiten, dafür aber kein klares Kriterium, wann die Aufgabe gelöst ist. Erinnert an das Plazieren von Labels oder allgemein an kartographisches Generalisieren: schlecht charakterisierte undankbare Probleme. Nicht meine Welt.

Gruß Wolf

Hallo zusammen,
erstmal ein großes Kompliment für das bisher geleistete!
Soviel, wie ich verstanden habe, wurden beim automatischen Routing die "Kontaktpunkte" der an einen Platz anstoßenden Straßen miteinander "virtuell" verbunden (also nicht über tatsächlich vorhandene ways in OSM), um so ein optimales Routing über als area getaggte "Straßen" zu ermöglichen. Wenn ich jetzt keinen Denkfehler mache, funktioniert das auch, wenn bei dem Routing von A nach B diese "area-Straße" (bspw. ein Platz) nur überquert werden muss (also sozusagen eine Zwischenstation ist).
Würde aber dieses Schema auch dann funktionieren, wenn das Ziel selbst auf dem Platz liegt, oder aber das Ziel eine an dem Platz liegende Adresse (ein Haus oder ein Geschäft) ist? Es müssten doch dann nicht nur die Punkt der angrenzenden Straßen miteinander verbunden werden, sondern zusätzlich auch noch die Punkte der jeweiligen Häuser, Geschäfte, Hauseingänge, ... ?!
Vom Prinzip her dürfte dieses Problem aber auch die vorgeschlagenen virtuellen Wege (virtual:) betreffen?!
VG,
Thorsten

Nahmd,

DoDoMR wrote:

Soviel, wie ich verstanden habe, wurden beim automatischen Routing die "Kontaktpunkte" der an einen Platz anstoßenden Straßen miteinander "virtuell" verbunden (also nicht über tatsächlich vorhandene ways in OSM), um so ein optimales Routing über als area getaggte "Straßen" zu ermöglichen.

Nein, genau das passiert zur Zeit nicht. Es würde aber besseres Routing ermöglichen.

Routing-Engines arbeiten nicht auf Geometrien, sondern auf einem Graphen aus Punkten und abstrakten Abständen zwischen diesen Punkten. Insbesonders kennen Routing-Engines keine Flächen. Bei der Aufbereitung der Daten werden zur Zeit Flächen ebenso wie geschlossene Ringwege behandelt, was dazu führt, dass die Routing-Engine sich einen Weg an der Außengrenze eines Platzes entlang sucht. Der natürlich (viel) länger ist als der wirkliche Weg. Und das führt dazu, dass die Routingengine möglicherweise einen Weg außen herum über Straßen als besser (kürzer/schneller) ansieht und ihn einer Route über den Platz hinweg bevorzugt.

Die virtuellen Wege erlaubten den Routing-Engines besseres Routing über Plätze, ohne dass die Algorithmen der Engines verändert werden müssten.

Würde aber dieses Schema auch dann funktionieren, wenn das Ziel selbst auf dem Platz liegt, oder aber das Ziel eine an dem Platz liegende Adresse (ein Haus oder ein Geschäft) ist? Es müssten doch dann nicht nur die Punkt der angrenzenden Straßen miteinander verbunden werden, sondern zusätzlich auch noch die Punkte der jeweiligen Häuser, Geschäfte, Hauseingänge, ... ?!

Auch die Häuser an Straßen sind (meist) nicht an die Straßen angeschlossen. Die Engines selber routen prinzipiell nur von Punkt auf Weg nach Punkt auf Weg. Es ist Aufgabe der Adresseingabe, zu einer Adresse / zu einem Poi diesen Punkt zu finden.

Vom Prinzip her dürfte dieses Problem aber auch die vorgeschlagenen virtuellen Wege (virtual:) betreffen?!

Die virtuellen Wege würden – so von der Adresseingabe berücksichtigt – bessere Start- und Endpunkte für Routen abgeben.

Gruß Wolf

Morsche,

erst mal vielen Dank für die Erläuterung.

Wenn man sich mal das Beispiel "Zeil / Konstablerwacher / Carl-Theodor-Reiffenstein-Platz / Stiftstraße / Hasengasse" in Frankfurt (http://www.openstreetmap.org/#map=18/50.11451/8.68520) anschaut, dürfte das Routingproblem vielleicht noch offensichtlicher werden:

Was haben wir hier? Die Fußgängerzone "Zeil / Konstablerwacher / Carl-Theodor-Reiffenstein-Platz / Stiftstraße / Hasengasse" sind zunächst mal als area=yes getagged. Darüber hinaus gibt es noch div. Verbindungswege, die mit name der jeweiligen Straße erfasst wurden (Stiftstraße, Hasengasse, Zeil, Konstablerwache, Fahrgasse,... Auf der Zeil selbst (also auf der leeren Fläche zwischen den Häuserzeilen) sind div. Gaststätten als einfacher node erfasst, bei denen es tatsächlich um kleine Pavillons handelt, die (noch) nicht als building=yes gezeichnet wurden. Dann haben wir die U- und S-Bahn-Gleise, die unter der Zeil verlaufen, sowie die zugehörigen Bahnhöfe unter der Konstablerwache. Weiter hätten wir noch eine "B-Ebene" (ebenfalls eine Art Fußgängerzone) mit entsprechenden Geschäften, die ebenfalls unter der Konstablerwache ist, die allerdings (noch) nicht erfasst wurden. Sowie die (Roll-)Treppen und Aufzüge, die zur B-Ebene und/oder zu den darunter liegenden U-/S-Bahnhöfen mit den entsprechenden Bahnsteigen (insgesamt 3 bzw. 4 Tiefebenen incl. B-Ebene) führen.

Wenn man dann noch ein evtl. Indoor-Routing bspw. in Einkaufszentren (im Beispiel Zeil wären das in Erster Linie "My-Zeil" und "Zeilgalerie") hinzuzieht, kommen wir auf etliche Wege, die möglicherweise dann als virtual: ergänzt werden müssten (also z.B. virtuelle Wege zu den Auf-/Abgängen der U-/S-Bahnhöfen, evtl. virtuelle Wege zu den sich auf der Zeil befindlichen Pavillons, ggf. virtuelle Wege in der "Fußgängerzone" der B-Ebene sowie den dazugehörigen Geschäften, ...). Und dieses Thema dürfte es in Frankfurt nicht nur einmal geben (ich denke da z.B. auch an die Ecke Zeile/Hauptwache/Fressgass/Alte Oper; Hauptbahnhof; Willi-Brandt-Platz; ...); auch in anderen Städten mit Fußgängerzonen und/oder unterirdischen Bahnhöfen, Straßenbahn- und Bushaltestellen, ...

Insofern kann aus meiner Sicht die "virtual:-Wege"-Lösung nur eine Übergangslösung darstellen. Für das Routing selbst müssen in der Routing-Engine selbst Lösungen gefunden werden. Hierbei ist aber auch klar, dass diese Lösung nur mit einem "Miteinander" (also OSM und Routing-Hersteller gemeinsam) gefunden werden kann und entsprechende Kompromisse auf beiden Seiten notwendig sind.

VG,
Thorsten

Ich habe mal die Überschrift ergänzt, hat ja zum großen Teil nichts mit meiner Frage mehr zu tun

DoDoMR wrote:

Wenn man sich mal das Beispiel "Zeil / Konstablerwacher / Carl-Theodor-Reiffenstein-Platz / Stiftstraße / Hasengasse" in Frankfurt (http://www.openstreetmap.org/#map=18/50.11451/8.68520) anschaut, dürfte das Routingproblem vielleicht noch offensichtlicher werden:

Was haben wir hier? Die Fußgängerzone "Zeil / Konstablerwacher / Carl-Theodor-Reiffenstein-Platz / Stiftstraße / Hasengasse" sind zunächst mal als area=yes getagged. Darüber hinaus gibt es noch div. Verbindungswege, die mit name der jeweiligen Straße erfasst wurden (Stiftstraße, Hasengasse, Zeil, Konstablerwache, Fahrgasse,... Auf der Zeil selbst (also auf der leeren Fläche zwischen den Häuserzeilen) sind div. Gaststätten als einfacher node erfasst, bei denen es tatsächlich um kleine Pavillons handelt, die (noch) nicht als building=yes gezeichnet wurden. Dann haben wir die U- und S-Bahn-Gleise, die unter der Zeil verlaufen, sowie die zugehörigen Bahnhöfe unter der Konstablerwache. Weiter hätten wir noch eine "B-Ebene" (ebenfalls eine Art Fußgängerzone) mit entsprechenden Geschäften, die ebenfalls unter der Konstablerwache ist, die allerdings (noch) nicht erfasst wurden. Sowie die (Roll-)Treppen und Aufzüge, die zur B-Ebene und/oder zu den darunter liegenden U-/S-Bahnhöfen mit den entsprechenden Bahnsteigen (insgesamt 3 bzw. 4 Tiefebenen incl. B-Ebene) führen.

Die Aufgabenstellung ist, den Routing-Engines Wege über Plätze anzubieten, damit sie sich nicht “immer an der Wand lang” hangeln müssen.

Bereits existierende Wege sind schwer zu berücksichtigen, die habe ich ausgeblendet. Die Ebenen behandelt man jede für sich; U-Bahneingänge, Rolltreppen usw., alles was Ebenen verbindet übernimmt man als POI (schwarz) in die Aufgabenstellung; Indoor-Routing ist kein Thema, solange die Wände in den Gebäuden nicht erfasst sind; ich gehe auch davon aus, dass man inenrhalb von Gebäuden die Flure und Gänge als Wege einzeichnen wird, denn das ist einfacher, als Wände einzuzeichnen.

Die Aufgabenstellung hier gehört zu den weiter oben beschriebenen fiesen, weil es sehr viel Punkte gibt und fast keine Hindernisse: die Lösung enthält deshalb auch nach dem Filtern zu viele Wege. Ohne eine Generalisierung ist die Lösung praktisch nicht einsetzbar. Und die Generalisierung ist eine wirklich unangenehme (und auch undankbare) Aufgabe.

@wegavision: sorry für die Entführung des Threads. Ich höre jetzt auch auf, da ich die benötigte Generalisierung nicht leisten kann.

Gruß Wolf

Vielleicht könnte man recht eng zusammen liegende Punkte (<20m?) zu einem Punkt zusammenfassen und nur damit rechnen (Clustering). Im Frankfurt Beispiel scheint diese Situation ja an einigen Stellen aufzutreten, was die Zahl der Kanten unnötig nach oben treibt.

Auch könnte man als Optimierungsziel die Gesamtlänge aller Wege minimieren, indem man z.B. zusätzliche Punkte einfügt. Jeder der schon einmal einen Interkonti-Flug mit Zubringerflug absolviert hat, kennt bestimmt dieses Hub-and-Spoke Prinzip. Gleiches kenn man auch vom Paketdienstleister, wo das Päckchen von Verteilzentrum zu Verteilzentrum wandert bis es irgendwann einmal beim Empfänger ankommt. Das ist aber leider alles andere als trivial... Haben wir eigentlich schon Winter??

couchmapper wrote:

... Haben wir eigentlich schon Winter??

[OT] Heute Nacht (-2°) und morgen tagsüber (+3°) ja. (Gilt für Bonn) [/OT]

Edbert (EvanE)

Nahmd,

couchmapper wrote:

Vielleicht könnte man recht eng zusammen liegende Punkte (<20m?) zu einem Punkt zusammenfassen und nur damit rechnen (Clustering). Im Frankfurt Beispiel scheint diese Situation ja an einigen Stellen aufzutreten, was die Zahl der Kanten unnötig nach oben treibt.

Auch könnte man als Optimierungsziel die Gesamtlänge aller Wege minimieren, indem man z.B. zusätzliche Punkte einfügt.

Wie ich schon schrieb: “oder ein beliebiges anderes Verfahren”. 😉

Gruß Wolf

Ich bin mir nicht sicher, ob clustern nicht nur der Optik dient. Ich habe einen Platz, an dem drei Punkte links sind und drei rechts. An der Wand sind die schon vom Polygon verbunden (4 Wege). Dann kommen 9 virtuelle Linien dazu, die die beiden Seiten verbinden:

Bei ungünstigem Clustern spart man sich keine einzige Verbindung, es sieht nur hübscher aus. Der Router hat die gleiche Arbeit mit dem nun aufgeteilten "Interkonti-Flug" quer über den Platz.

Selbst bei optimaler Clusterung hat man noch 11 Verbindungen zu bearbeiten. Erst wenn man es schafft, die zusätzlichen Punkte in die vorhandenen zu legen, oder sich von der Verbindung an der Wand verabschiedet (was vermutlich dumm ist, das ist die einzige, die von einem vernunftbegabten Wesen eingetragen wurde), kann man mehr erreichen.

Grüße, Max

Bringt ihr hier nicht ein paar Aufgaben durcheinander? Man muss doch 2 Fälle unterscheiden:

1. Der Platz ist Transit für eine längere Route ("Drüberrouten"). Das könnte durch "virtuelle Wege" zwischen den äußeren Verbindungsknoten in der Routing-Karte gespeichert werden. Dabei reicht ein einziger virtueller Weg für ein Zugangsknoten-Verbindungspaar, der die entsprechende Längen-Metrik und Typ trägt. Nur die müssen gespeichert werden, nicht der Wegverlauf dazwischen. Damit ist die Berechnung einer Optimalroute im Gesamtnetz der Karte möglich.

2. Start/Ziel oder der aktuelle Standort befindet sich auf dem Platz. Dazu gibt es unendlich viele Möglichkeiten, entsprechend unbegrenzt viele mögliche Routen. Das kann nicht im Vorfeld schon in Routingkarten gespeichert werden. Die Möglichkeiten werden erst handhabbar, passend eingeschränkt, wenn Start/Ziel oder Standort als zusätzlicher Knoten dem Graphen hinzugefügt wird. Das muss der Router vor Ort bzw. anhand einer konkreten Route entscheiden.

openzzz wrote:

Bringt ihr hier nicht ein paar Aufgaben durcheinander? Man muss doch 2 Fälle unterscheiden

Ja.

Vielleicht finden wir eine Lösung für (1), und für (1a). Letzteres ist der Fall, dass ich zu einem gemappten Punkt auf dem Platz möchte, beispielsweise eine Imbissbude, die frei auf dem Platz steht. Oder ein Treppenabgang zur U-Bahn.

(2) Lässt sich weder durch virtuelle gemappte Wege noch durch automatisiert zusätzlich eingetragene Lösen, da muss jemand einen Router schreiben.

maxbe wrote:

Vielleicht finden wir eine Lösung für (1), und für (1a). Letzteres ist der Fall, dass ich zu einem gemappten Punkt auf dem Platz möchte, beispielsweise eine Imbissbude, die frei auf dem Platz steht. Oder ein Treppenabgang zur U-Bahn.

Das ist aber wieder Fall 2, kein Transit, sondern Ziel auf Platz. Ich weiss nicht, ob es sich lohnt für diese Fälle den Platz mit virtuellen Wegen zu versehen. Der Router muss ja auch andere Fälle beherrschen, wo der aktuelle Standort frei auf dem Platz liegt und nicht auf vordefinierten Nodes. Dem Router sollte es zumutbar sein, auf dem Start/Zielplatz selbst zu optimieren. So viele Wege sind es nicht mehr, wenn die Nodes im konkreten Fall fixiert werden. Es wird sowieso ständig eine Neuberechnung fällig, wenn man sich auf dem Platz bewegt. Eine der Nodes ist dann beweglich.

Hat eigentlich jemand praktische Erfahrungen mit dem Routing über solche Plätze?

"OsmAnd" auf Android hat einen Fußgänger-Routing Modus.
Ich hatte es allerdings nur einmal in der Stadt probiert, um eine bestimmte Kneipe zu finden.
Das hat funktioniert. Ansonsten nutze ich massiv parallele neuronale Netze für solche Aufgaben.

Ob OsmAnd auch in Fußgängerzonen funktioniert?

Im Mittelgebirge hatte ich es einmal probiert und da hatte es versagt,
kilometerweite Umwege vorgeschlagen weil bestimmte Schotterwege ignoriert wurden.

openzzz wrote:

Ob OsmAnd auch in Fußgängerzonen funktioniert?

Wahrscheinlich genauso gut oder schlecht wie mit den Garmin-Karten: das Routing verwendet nur die Außenkanten der Area. Ein entsprechendes Ticket wurde mit won't fix geschlossen. Kommentar von Victor: "This is a small glitch (we consider for small areas), but it is very hard to fix technically. Because routing engine doesn't support routing via areas.".

Da kann ich Victor verstehen. Das ist eher ein Feature Request als ein Bugfix. Wenn man die Sache richtig angeht, mit allen Problemen wie Flächenfusion etc. kann das schon aufwendig werden. Victor bietet an, Features gegen Spenden zu implementieren. "small glitch" stimmt auch in den meisten Fällen, da man auf den Plätzen sowieso seinen eigenen Weg sucht, abhängig vom Verkehrsaufkommen, Platzierung der Cafeterie-Bestuhlung, Marktständen etc. Wichtig ist vor allem, dass der Platz eine Route nicht verhindert - das Rand-Routing ist dann schon eine vernünftige Notlösung.

Nun, man braucht natürlich genug Motivation, so ein Projekt durchzuziehen. Haben wir Geoinformatiker unter uns? Das wäre eigentlich eine schöne Aufgabenstellung für studentische Arbeiten: Bachelor, Master etc., mit theoretischen Komponenten und einem schönen Erlebnis der praktischen Nutzbarkeit. Der Zeitrahmen könnte für eine solche Arbeit passen und eine Veröffentlichung ist sowieso notwendig.

Wieso soll jeder Routerprogrammierer das Rad neu erfinden? Lösung wäre, den Anwendungen preprocessierte OSM Daten zur Verfügung zu stellen.

Gibt es denn schon OpenSource-Lösungen für das Flächenrouting-Problem? Wenn nicht, müsste man das Rad tatsächlich erst erfinden. Dabei sind auch die speziellen Datenstrukturen von OSM zu berücksichtigen. Was macht man z.B. wenn sowohl Flächen als auch Wege dadurch gezeichnet wurden?

Präprocessing von OSM-Daten ist nur sinnvoll für Transit-Routing. Lokal auf dem Platz muss es der Router selbst meistern. Man kann nicht für alle potentiellen Standpunkte (unendlich viele) die Wegenetze berechnen und alles speichern. Das wäre unsinnig. Andererseits wäre es unsinnig, wenn der Router für alle Plätze im Transit jedesmal die kürzeste Platzroute neu berechnen muss (ändert sich nur nach dem Editieren der Karte). Lezteres wäre mit virtuellen Wegen in der Routingkarte eleganter zu lösen. Eigentlich könnte das sogar zentral in OSM gespeichert werden, weil alle Router vor dem gleichen Problem stehen.

Für wäre doch das "Transit-Routing" identisch zum "Routing zu einem Ziel auf dem Platz zu sehen":

Beim Transitrouting hat der Router ermittelt, dass bspw. der kürzeste Weg von A nach B über den Platz verläuft. D.h. eine Straße ist mit dem Platz verbunden (habe ich also einen "Start-Knoten" (node) ) und wo die ermittelte Route dann auf einer anderen Straße, die ebenfalls an den Platz mit einem Knoten (node) verbunden ist, wäre dann sozusagen der "Ziel-Knoten".

Wenn sich nun das Routingprogramm eine Route ermittelt, deren Ziel auf dem bzw. an dem Platz liegt, wäre das doch die gleiche Problemstellung, wie wenn das Routingprogramm lediglich eine "Transitroute" über den Platz berechnet.

Insofern (wenn also das Problem des Flächenroutings gelöst ist), könnte man doch eigentlich auf die "virtuell erfassten" Wege komplett verzichten (was dann auch der Übersichtlichkeit dienlich wäre).

In der Hinsicht eine ganz andere Frage: Wie wird denn eigentlich ein "Outdoor-Routing" berechnet, wo es auch keine Straßen/Wege gibt - das wäre doch dann eigentlich genauso, wie das Routing über einen Platz (nur das hier natürlich eine wesentlich größere Fläche zu berücksichtigen ist)?! Klar - beim Outdoor-Routing wird in den meisten Fällen einfach eine Luftlinie berechnet. Aber es gibt doch auch hier Programme, die eine "komfortable" Route berechnen (also z.B. Berge/Schluchten vermeiden) können, oder tatsächlich die kürzeste Strecke (Luftlinie).

DoDoMR wrote:

Für wäre doch das "Transit-Routing" identisch zum "Routing zu einem Ziel auf dem Platz zu sehen":

Nein, das hat ganz unterschiedliche Komplexität. Für das Transit-Routing sind lediglich alle Kombinationen der Straßen-Anknüpfungspunkte zu berechnen und durch je einen einzigen virtuellen Weg mit Kostenfaktor zu speichern. Das sind nicht viele. Sehr realistisch im aktuellen OSM/Routing-Konzept.

Die Verbindungen zwischen den ganzen Zwischenknoten auf dem Platz sind wesentlich umfangreicher, u.a. die ganzen Kombinationen an Polygonecken und Hauseingängen. Für einen Transit spielt das alles keine Rolle. Das ist nur relevant, wenn man sich bereits auf dem Platz befindet oder wenn man ein Ziel darauf anwählt. Letzterer Fall könnte noch vorausberechnet werden, ersterer nicht, weil der Standort auf dem Platz beliebig sein kann. Falls also die konkrete Wegführung auf dem Platz eine Rolle spielen soll muss das Routing-Programm dort individuell routen.

Also Aufgabe für den Routing-Karten-Produzenten:
- Transit-Wege vorausberechnen und speichern. Für jeden Platz auf der Karte ist also die Optimierungsaufgabe zu lösen.

Aufgabe für das Routing-Programm:
- virtuelle Wege beim Transit über Platz berücksichtigen, genauso wie die realen Wege (kein Extraaufwand)
- Bei Wahl eines Start/Zielpunktes auf einem Platz jeweils abhängig davon eine Optimalroute finden (Flächenrouting nur dort)
- beim aktuellen Standort auf einem Platz die Route dynamisch neuberechnen

Die Rechenlast für das Routing-Programm ist beherrschbar, für die Start/Zieleingabe jeweils nur 1x eine Optimierung
und dynamisch jeweils nur für den aktuellen Platz. Müsste es auch für die ganzen Transitflächen noch Optimalrouten finden
könnte es aufwendig werden. Im Voraus weiss man ja noch gar nicht, ob ein Platz überhaupt Teil der Route ist.
Wenn man dann alle möglichen Flächen in der näheren Umgebung gleich mitoptimieren müsste ...
Da sind die virtuellen Wege doch praktischer.

Puuuhhh! Was für ein langer Thread hier... Also:

1) "Neu erfundene" virtuelle Routing Tags existieren eh bereits rudimentär, z.B. für den Sylt-Shuttle
2) OSM-Daten sind per se schon grottig genug, was die Interpretierbarkeit für Router betrifft.
3) Router benötigen gewichtetete Kanten, also Ways. Alles andere ist Unfug und nur mit massivem Preprocessing-Aufwand zu beseitigen. Für Städte mag das ja noch gehen, für Länder und Kontinente wäre das ein klares ko-Kriterium. Da kann man gleich das Rechenzentrum von Google mieten.
4) Zur Laufzeit einer Routenberechnung geht eine Polygon-Interpretation schon mal gar nicht - wäre viel zu lahm.

Meine Meinung:

OSM sollte seiner Linie treu bleiben und nicht ständig neue Dinge erfinden - gibt schon zu viele alternative Tagging-Optionen für ein und die selbe Geschichte. Wir Deutschen lieben sowas ja, doch ob die restliche OSM-Welt da noch Lust zu hat, ..., und dem folgt, ..., hab da so meine Zweifel.
OSM dient unterschiedlichen Zielgruppen. Das hübsche Malen von Karten und die Darstellung der optischen Realität ist dabei eine von vielen. Routing und GeoCoding sind da schon wieder eine völlig andere Nummer. Hier benötigt man eindeutig lokalisierbare Anker, von mir aus auch virtuelle, die man finden und verbinden kann. Auch der Vorschlag Dinge über einen "Snapping-Radius" als zugehörig/zusammenhängend zu interpretieren führt allzu oft zu komischen Ergebnissen.
Um OSM einigermaßen korrekt zu routen, kann man sich nur auf die NodeIDs als Links verlassen.

Wenn ich also zum Bäcker in der Fuzo fuß-routen möchte, dann erwarte ich, dass es einen idealisierten Weg daran gibt. Per GeoCoding krieg ich die Koordinate vom Bäcker und kann dann eine sehr schnelle Lotfuß-Berechnung lostreten. Ich denke, so funktionieren die meisten Router.

Was mich immer wieder ärgert sind übrigens Routing-Apps und -Programme, die OSM-Material aus den o.g. Gründen schlecht berechnen und dann periodisch "vernünftiges" Kartenmaterial zum Kauf anbieten.
Das hat sicher einen guten Grund ;-(

Nahmd,

pimapper wrote:

3) Router benötigen gewichtetete Kanten, also Ways. Alles andere ist Unfug und nur mit massivem Preprocessing-Aufwand zu beseitigen. Für Städte mag das ja noch gehen, für Länder und Kontinente wäre das ein klares ko-Kriterium.

Weil die Router nur entlang Kanten routen, sind Wege über Flächen wegen des "immer an der Wand lang" Routings im Routing-Ergebnis manchmal länger als in der Realität längere Wege über Straßen, die die Fläche umgehen. Das führt zu überraschenden Routings. Und das kann man verbessern, natürlich ohne den OSM-Datenbestand aufzublasen und ohne in den eigentlichen Router einzugreifen.

Die Grundidee bestand darin, zwischen dem Auslesen der OSM-Daten und dem Preprozessing der Router-Software (möglichst wenig) [virtuelle] Wege einzufügen, die das Routing-Ergebnis verbessern, ohne die Last signifikant zu erhöhen.

Wir finden bereits die Minimalzahl von Wegen, die zu einem optimalen Routingergebnis führt. Soweit ist das Problem gelöst.

Leider sind das oft zu viele, und man müsste ausdünnen: und das kann man auch, weil zum Erreichen des Zieles überhaupt nicht nötig ist, die optimalen Routen über den Platz anzubieten. Es reichen hinreichend gute, und hinreichend bedeutet hier, dass man günstiger wird als der Weg außenherum. Leider ist die Reduktion von den (zu vielen) "optimalen" Wegen auf eine kleine Menge "notwendiger/hinreichender" Wege nicht trivial.

Da kann man gleich das Rechenzentrum von Google mieten.

Das ist nicht richtig: Ich kann leicht die Ergänzugsways zu allen 150.000 highway-Flächen weltweit bereitstellen. Z.B. als "osmdiff", so dass man die in der Verarbeitungspipe irgendwo mit einfließen lassen kann. Aber eben nur die Optimalen, und nicht einen sinnvoll ausgedünnten Satz.

4) Zur Laufzeit einer Routenberechnung geht eine Polygon-Interpretation schon mal gar nicht - wäre viel zu lahm.

[×] Zustimmung.

Wenn ich also zum Bäcker in der Fuzo fuß-routen möchte, dann erwarte ich, dass es einen idealisierten Weg daran gibt. Per GeoCoding krieg ich die Koordinate vom Bäcker und kann dann eine sehr schnelle Lotfuß-Berechnung lostreten. Ich denke, so funktionieren die meisten Router.

Ja natürlich.

Dass aber aus der Überlegung, wie man mit überschaubarem Aufwand einen Router dazu bringt, Flächen zu nutzen statt sie zu umgehen, die Forderung wird, zentimetergenaues Routing um die Tische der Außengastronomie herum zu jedem POI am Randes des Platzes bereitzustellen, ist für Diskussionen hier völlig normal und auch nicht schlimm.

Es liegt einfach daran, dass es einfacher ist, Visionen zu haben, als eine einzige Zeile Code zu schreiben. Und dass Visionen umso größer werden, je weniger Kenntnisse der Realität sie behindern.

Da hilft nur: Popcorn!

Mampfende Grüße: Wolf

pimapper wrote:

3) Router benötigen gewichtetete Kanten, also Ways. Alles andere ist Unfug und nur mit massivem Preprocessing-Aufwand zu beseitigen. Für Städte mag das ja noch gehen, für Länder und Kontinente wäre das ein klares ko-Kriterium. Da kann man gleich das Rechenzentrum von Google mieten.
4) Zur Laufzeit einer Routenberechnung geht eine Polygon-Interpretation schon mal gar nicht - wäre viel zu lahm.

Zur Laufzeit muss nur der aktuelle Platz optimiert werden, auf dem man sich befindet. Das sind alle Karten-Nodes und Polygonkanten plus eine Node des aktuellen Standorts. Einfaches Graphenproblem, ohne Raytracing. Im Zeitalter von GHz-CPU ist das doch kein Problem oder?

Alle Plätze im Transit können durch wenige virtuelle Wege vollkommen optimal repräsentiert werden, genau gesagt (n*(n-1))/2 beidseitig nutzbare bzw. ein paar Extras bei Einbahnstraßen. Das wären für einen typischen Marktplatz mit 5 Zugangswegen nur 10 virtuelle Wege dazwischen. Ist das ein Problem? So häufig sind die Plätze auch wieder nicht. Routing-Karten bei OsmAnd gibt es Bundesländer-weise, nicht als Planet-File. Der Rechenaufwand dürfte sich in Grenzen halten. Außerdem ist es dann nicht Aufgabe der OSM-Community, sondern des Routingkarten-Erzeugungsprogramms, vollautomatisch.

Also, für Fußgänger wäre das schon ein nettes Feature, mit relativ wenig Rechenaufwand machbar. Muss nur jemand Zeit zum Programmieren haben ...

Wie gesagt, eine schöne studentische Arbeit für die betreffenden Fachbereiche. Die müssen sich sowieso immer neue Themen ausdenken. In einer Masterarbeit will man i.d.R. etwas Neuartiges entwickeln und ist zur Publikation verpflichtet. Sehr viel guter Sourcecode ist bei solchen Arbeiten entstanden.

pimapper wrote:

2) OSM-Daten sind per se schon grottig genug, was die Interpretierbarkeit für Router betrifft.

Das kann man so pauschal nicht sagen. Ich halte es zwar auch für sehr wichtig, Datenfelder möglichst exakt zu definieren und wenig Interpretationsspielräume zu lassen (z.B. max-speed nicht einmal als km/h und einmal als miles-per-hour ins gleiche Datenfeld ohne Einheitenangabe zu schreiben), aber die Praxis zeigt, dass Routing auf OSM durchaus gut funktionieren kann.

Ich hatte mir den Spaß erlaubt, gelegentlich neben meinem kommerziellen Auto-Navigator noch "OsmAnd" mitlaufen zu lassen. Die Anweisungen kommen dann quasi in Stereo. Erstaunlicherweise sind die beiden sich in den meisten Fällen einig gewesen. Dumme Fehler haben sich beide erlaubt. Manchmal war OSM auch besser. Der Fahrspurassistent ist im kommerziellen Navi besser. In manchen Innenstädten hat mich OSM gelegentlich komplett in die Irre geführt (bzw. ich hab's eine Zeitlang beobachtet bis ich das Ding ignoriert hatte und meinen eigenen Weg gefahren bin). Man beurteilt die Routing-Qualität auch gerne nach solchenen eher seltenen Aussetzern. Da kann 99% der Route vollkommen Ok sein. Wenn das Ding einen aber einmal kreuz- und quer durch die City irreführt merkt man sich das.

Vielleicht ist Software denkbar, die derartige seltenen Fehler automatisch erkennt. In dem Sinne ist es vielleicht auch gut, wenn das OSM-Material von kommerziellen Anbietern herangezogen wird, wenn sie mithelfen, solche Fehler zu beseitigen.

Absolut OT:

openzzz wrote:

pimapper wrote:

OSM-Daten sind per se schon grottig genug, was die Interpretierbarkeit für Router betrifft.

Ich hatte mir den Spaß erlaubt, gelegentlich neben meinem kommerziellen Auto-Navigator noch "OsmAnd" mitlaufen zu lassen. […]

Mir fallen jetzt spontan zwei grössere Fehler ein, die ich dabei erlebt habe: 1.: OsmAnd routet teilweise über Feldwege, 2.: das "kommerzielle Navi" routet teilweise über dauerhaft gesperrte Strassen und kennt einige Dinge nicht. Ansonsten ist OsmAnd oft etwas besser (besonders innerstädtisch), allerdings (teils deutlich) langsamer, an Kreuzungen an denen Fahrspuren als eigene Strassen gemappt wurden etwas verwirrend…

openzzz wrote:

Der Fahrspurassistent ist im kommerziellen Navi besser.

…und da muss ich dir leider zustimmen. Die Abwahl von Autobahnen klappt "drüben" auch besser (ist nicht so zwanghaft).

Netzwolf wrote:

Es liegt einfach daran, dass es einfacher ist, Visionen zu haben, als eine einzige Zeile Code zu schreiben.

Code schreiben ist gar nicht so schwer, nur funktionieren tut es danach nicht immer 😄

Nahmd,

rayquaza wrote:

Netzwolf wrote:

Es liegt einfach daran, dass es einfacher ist, Visionen zu haben, als eine einzige Zeile Code zu schreiben.

Code schreiben ist gar nicht so schwer, nur funktionieren tut es danach nicht immer 😄

Wir haben offensichtlich unterschiedliche Vorstellung von “Code schreiben”. 😛

Gruß Wolf

vielleicht stelle ich mir das jetzt zu einfach vor (ich möchte keineswegs behaupten, dass "code zu schreiben einfach wäre"), aber am anfang steht doch bei einem routing meist der "kürzeste" weg - das ist immer eine gerade zwischen start- und zielpunkt. 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. wenn nun auf dieser gerade hindernisse auftauchen (gebäude, bänke, bäume, ... oder aber auch wenn der platz verwinkelt ist), muss die routingsoftware alternative 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 lösung muss also in der routingsoftware selbst liegen. 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.

Moin,

DoDoMR wrote:

[...] muss die routingsoftware alternative 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 lösung muss also in der routingsoftware selbst liegen.

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.

ich glaube, hier thoeretisierts Du das Problem zu sehr.
Im Preprocessing kann man eine doch endliche Anzahl von optimalen Wegen zwischen den Anschlusspunkten finden.
Damit gibt sich über den Platz schonmal ein gewisses Netz von "virtuellen" Wegen im Kartenmaterial.

Damit ergibt sich das Problem "beliebiger Punkt auf dem Platz" zu dem üblichen Routing-Problem "finde den nächstgelegenen (vorhandenen) Weg zu diesem Punkt".
Und hier vertraue ich ganz ehrlich auf den Unterschied zwischen Theorie und Praxis:
In der Theorie sind das unendliche Weiten - in der Praxis aber überschaubare Entfernungen im Meterbereich. (*)

Bereits in einem "praktischen" Netz von optimalen virtuellen Wegen sehe ich da bereits das Problem, dass sich der Router für einen der viel zu eng liegenden Wege entscheiden muss und aufgrund der GPS-Schwankungen viel zu oft "neuberechnet" - wie wäre es da erst bei Deinem "floating" Routing?

Von daher würde ich immer noch von Fall zu Fall ein "generalisiertes Preprocessing der virtuellen Wege von Mapperhand" in Erwägung ziehen.
Auch wenn der automatische Router den menschlichen sicherlich im Prozentbereich schlagen wird. 😉

Gruß
Georg

(*) Ich gehe hierbei zugegeben von europäischen Plätzen aus - vielleicht liegt da mein Vorurteil ...

rayquaza wrote:

Mir fallen jetzt spontan zwei grössere Fehler ein, die ich dabei erlebt habe: 1.: OsmAnd routet teilweise über Feldwege, 2.: das "kommerzielle Navi" routet teilweise über dauerhaft gesperrte Strassen und kennt einige Dinge nicht. Ansonsten ist OsmAnd oft etwas besser (besonders innerstädtisch), allerdings (teils deutlich) langsamer, an Kreuzungen an denen Fahrspuren als eigene Strassen gemappt wurden etwas verwirrend…

Solche Späße erlaubt sich auch mein kommerzielles Navi in Belgien und Holland. Offenbar haben sie dort gelegentlich "Feldwege", die befahren werden dürfen, inklusive Unterboden-Graspolitur. Dummerweise hat das Navi die gemütliche Hauptstraße daneben einfach ignoriert. Wäre wohl einen Tick länger gewesen (aber flotter). Mit den deutschen Straßenkategorien kommt es besser zurecht, obwohl der Kartenhersteller Navteq seine Europazentrale in Eindhoven hat ...

Bei der Geschwindigkeit liegt es teils auch am GPS-Chip. Ich denke mein Smartphone hat nicht so einen guten Kalman-Filter und kann schlechter Aussetzer interpolieren als der SIRF vom Navigerät. Dann muss OsmAnd machmal hinterherhinken, wenn die Position teilweise fehlt. Natürlich ist so eine detaillierte Vektorkarte wie OSM auch aufwendig zu rendern. Man könnte den reduzierten Straßenkarten-Modus mal probieren.

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.

Also, irgendwie kann ich der ganzen Diskussion nur bedingt folgen.
Nicht existente Wege einzubauen, egal ob virtuell oder berechnet, ist für mich eine Notlösung / Workaround.
Virtuell (render=false u.a.) ist dabei beinahe noch erträglich - existiert ja schon hier und da.
Das Problem ist doch eher das OSM Datenmodell. Ich kann nicht ganz nachvollziehen, wie man behaupten kann, dass derartige Berechnungen auf modernen Rechner grundsätzlich machbar wären. Vor kurzem hat mich jemand gefragt, ob es möglich sei, eine (Routing-)Topologie für Europa auf einem 2Gig-RAM rechner zu erstellen. Witzigerweise wäre das möglich, ist es auch, jedoch nicht mit den irrwitzigen Relationen, die OSM irgendwann mal eingeführt hat. Die kann man dann getrost ignorieren ... fast. Klar sind 2Gig heute nicht mehr StateOfTheArt, aber vor kurzem noch. Alles in eine PostGIS-DB reinzupusten und dann beten, dass der Nachtlauf am nächsten Morgen irgendwas vernünftiges produziert hat, ist ebenso suboptimal. Was bleibt ist die Hoffnung, dass Leute nicht irgendwann auf die Idee kommen einen Weg in zehn nacheinander kaskadierte Relationen zu taggen und ganz unten den Straßennamen zu verewigen. ... Tja, dann können wir uns leider nicht beschweren, denn recht hat er ... ist ja richtig so, weil technisch möglich und sogar offiziell so dokumentiert - leider - sogar in einem offiziellem Buch ... ;-(

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.

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

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

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.

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.

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.

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.

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

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!

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

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

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.

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

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

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.

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.

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

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

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

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

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

Ich hab noch ein bisschen gespielt und mein gesammeltes Wissen in eine Wiki-Seite geschrieben.

Virtuelle Wege einzutragen geht eigentlich ganz gut, die Rechenzeit ist für mich akzeptabel, 1 bis 2 Sekunden pro Platz (was bei mir heisst, der Import des Routing-Graphen dauert 20% länger), und wenn man die richtig komplizierten Fälle (etwa die Hecken in Ludwigsburg oder das Forum der hundert Treppen) überspringt, kann man das ganze wesentlich beschleunigen.

Ebenfalls deutlich beschleunigen kann man das Rechnen, wenn man seine Hindernisse sorgfältig auswählt. Man muss ja für alles, was so rumsteht überlegen, ob das einen Fussgänger ernsthaft aufhält. Jedes Loch in der Fläche, das dadurch entsteht, vervielfacht den Aufwand.

Ich hab das recht grosszügig betrachtet. Mit "amenity=* bildet jede Telefonzelle, Parkbank und jeder Papierkorb ein Hindernis. Bäume mit natural=tree ebenfalls. Häuser, Denkmäler, Flüsse, Trambahngleise sind auch Hindernisse und natürlich darf der Rasen nicht betreten werden.

Dabei habe ich auch gelernt, wie vielfältig die Welt der Plätze ist, vieles davon bleibt dem Betrachter verborgen, weil die Mapnik-Karte die Dinge entweder gar nicht rendert (amenity=fountain stehen häufig auf Plätzen, aber auch amenity=bicycle_parking können grosse Flächen einnehmen) oder sie unter den priorisierten highway-Flächen versteckt (Wintersportstätten oder Bäche z.B.).

Herzlichen Dank für die Vorschläge hier, besonders an Netzwolf, der interessante Dinge über Winkel erzählt hat (ich habe Tage damit verbracht, das als Unsinn zu entlarven, bevor ichs dann doch eingebaut hab 😉 ) und couchmapper, der Dijkstra zum Löschen unnötiger Wege vorgeschlagen hat.

Der Routing-Graph über den Sebastians- und den Jakobsplatz, den ich oben als Beispiel verwendet habe, sieht übrigens jetzt so aus:

Die dicken blauen Linien sind die bereits gemappten Wege, die dünnen die zusätzlichen virtuellen.

Und wer mal selbst Routen will, kann mit diesem oder diesem Beispiel anfangen (die Geschwindigkeit liegt nicht an den paar tausend virtuellen wegen, das war schon vorher so... und wenns gar nicht geht, liegts daran, dass ich auch grad dran rumbastel...)

Grüße, Max

Nachtrag: Übrigens kann man an allen Plätzen, bei denen schon Wege drüber gemappt wurden, eher wenig Verbesserung durch automatisch eingetragene Wege erzielen. Bei vielen wurden aber einige Nebenstrassen einfach vergessen.

Wenn ich das richtig verstehe, dann kann man sagen: Glückwunsch 🙂 Sieht sehr gut aus, auch die Dokumentation im Wiki.

Werde mir das mal genauer anschauen und rumprobieren. Bleibt dann nur zu hoffen, dass dies auch andere Router einbauen oder?