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

Nahmd,

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

Für den Router taggen ist böse.

Gruß Wolf

Edit: Kommentar zum Router ergänzt.

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,

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?

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

“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,

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.

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.

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…

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.

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

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,

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… :slight_smile:

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

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.

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.

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,

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.

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

Gruß Wolf

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.

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

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,

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

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

Wer gewinnt die Ausschreibung? :stuck_out_tongue:

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,

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.

Du hast fleißig durch Relevanzdiskussion dazu beigetragen.

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.

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

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? :slight_smile: