Routing auf Flächen

Communities Deutschland (Germany)
1

Nachdem nebenan (im Bürgersteigthread) ja mal wieder über den Sinn und Unsinn von Flächen in OSM diskutiert wurde (wir uns jetzt aber davon entfernt haben, u.a. deshalb hier ein neues Thema), will ich mal wieder ein paar Punkte in den Raum werfen.

Hauptargument gegen Flächen (für Straßen, Bürgersteige und Co.) ist ja, das es das Routing nicht leichter macht und nur dem Rendering diene. Viele Vorschläge, die bis jetzt gemacht wurden, zielen deshalb (und zur Erhaltung der Abwärtskompatibilität) darauf ab, dass Flächen und Linien getrennt erfasst werden, die einen für’s Rendern, die anderen für’s Routing (und Rendern in niedrigen Zoomstufen). Nun ist das aber ja schon deshalb nicht besonders toll, weil man eben zwei Datenbankobjekte pro realem Objekt hat. Heute bin ich über diesen Link gestolpert, in dem es zwar nicht genau um unsere Anwendungen, aber soweit ich das sehe doch um unser Problem geht. Ich kann nicht behaupten, jedes Detail genau verstanden zu haben, aber ich dachte, ich werfe mal in die Runde, was ich meine, dass man daraus für uns schließen kann (ich verwende im Folgenden das Wort ‘Graph’ für das was wir aktuell haben, weil mir gerade kein besseres einfällt. Nichtsdestotrotz ist auch das Gebilde aus konvexen Polygonen ein Graph):

Flächen sind ausreichend für eine routingfähige Beschreibung, folgendes preprocessing vorausgesetzt: Straßenflächen müssten in konvexe Polygone aufgebrochen werden, aber das sollte relativ unaufwendig sein, falls es keine bessere Möglichkeit gibt, sind Dreiecke auf jeden Fall eine Lösung, führen allerdings zu den meisten Wegpunkten.
Das ergibt netto ziemlich genau das Gleiche wie ein Graph, wie wir ihn aktuell verwenden, ist also für’s Routing genauso gut zu gebrauchen, mit den gleichen Algorithmen. Berechnet man zu jedem Polygon den Flächenschwerpunkt (was afaik relativ effizient geht) (oder auch jeweils einen beliebigen Punkt im Polygon) und verbindet diese korrekt miteinander, erhält man einen absolut identischen Graphen wie wir in aktuell haben, der auch zum Rendern in niedrigen Zoomstufen geeignet sein dürfte. Diese Schritte können leicht an einem frühen Punkt im Prozess gemacht werden, so dass die Endanwendungen nicht angepasst werden müssen (bspw. Navis, bei denen in die Programmierung nicht eingegriffen werden kann und die daher auf Graphen angewiesen sind), so dass beispielsweise schon die OSMF neben den direkten Planetfiles auch bereits tesselierte oder in Graphen umgewandelte Auszüge.

Damit wäre hoffentlich geklärt, dass es ausreicht Flächen zu erfassen und dass die zugehörigen Linien nicht notwendig sind. Bleiben einige Probleme (ohne Anspruch auf Vollständigkeit):

  • Genauigkeit: Sicher kann man argumentieren, dass es in den allermeisten Fällen garnicht möglich ist, die Flächen mit ausreichender Genauigkeit zu erfassen. Solange man auf GPS-Tracks angewiesen ist das natürlich so. Aber in immer mehr Gegenden können wir hochauflösende Luftbilder verwenden und wenn die korrekt ausgerichtet sind (anhand von GPS-Tracks und co.), lässt sich eine befriedigende Genauigkeit erreichen. Und was ist mit Gegenden, in denen man die nicht hat? Ich denke, beide Systeme können relativ problemlos nebeneinander existieren:
  • Abwärtskompatibilität, Gleichzeitigkeit: Wir können nicht überall alle Wege mit Flächen erfassen. Schon garnicht sofort, aber auch auf lange Sicht dürfte das weder möglich noch gewollt sein. Aber das muss ja auch nicht. Es spricht nichts dagegen, Wege wie bisher beizubehalten, wo keine Flächen existieren. Wenn an den Schnittstellen die Wege mit den Flächen verbunden sind, steht einem Routing nichts im Wege.
  • Richtungsabhängigkeit: Zugegebenermaßen ein größeres Problem. Aktuell fällt mir keine vernünftige Lösung dazu ein. Sinnvoll wäre vielleicht, wenn Flächenobjekte in der kommenden API neben den reinen Knoten- und Taglisten auch eine Rotation speichern würden. Ob man daraus allerdings solche Dinge wie Einbahnstraßen vernünftig berechnen kann, bin ich mir noch nicht im Klaren. Fällt jemandem etwas besseres ein? (Auch wenn eine Ausrichtung für Flächen für dieses Problem nicht nützt, fände ich sie trotzdem sinnvoll - für Dinge wie die Frontseite eines Hauses beispielsweise).

Meinungen, Ideen, Wünsche? Will mir jemand sagen, dass ich spinne und heimgehn soll? Nur raus damit :wink:

2

Wenn Du als proof-of-concept mal einen entsprechenden Router programmierst und sagst, wie man Einbahnstraßen
als Flächen mappen kann, dann lass ich mich überzeugen. :smiley:

Momentan schafft es kein mir bekannter Router über als MP-gemappte Pedestrian Areas zu routen (nicht mal
am Rand entlang).

Chris

3

Beim Routing auf Flächen muss man zwei Dinge unterscheiden.

  1. Routing auf “echten” Flächen

Wenn man sich frei auf einer Fläche bewegen kann (z.B. Fußgängerzone), dann ist ein Verfahren zum Routing über Flächen tatsächlich angebracht. Ja, es gibt solche Verfahren, und wir könnten sie bei OSM schon heute gut gebrauchen.

Trotz der theoretischen Machbarkeit routen leider alle unsere Programme immer noch am Rand von Plätzen entlang.

  1. Routing auf Straßen, die als Flächen repräsentiert sind

Wenn ich die Route für ein Auto auf einer Straße berechne, dann will ich bei der Routendarstellung keine Kurven schneiden etc., sondern tatsächlich parallel zu einer Mittellinie navigieren. Für diesen Anwendungsfall ist das Routing auf einem gewöhnlichen Graphen eigentlich genau der richtige Ansatz.

Die Aufgabenstellung dort wäre also, aus flächig gemappten Straßen eine Darstellung wie unsere heutige zurückzuberechnen. Dann kann man natürlich auch wieder mit den bekannten Algorithmen arbeiten.

Bis wir aber Werkzeuge haben, mit denen man eine solche Datendarstellung (die man übrigens nicht nur fürs Routing, sondern auch fürs Rendering braucht, sobald man z.B. eine Beschriftung längs der Straße platzieren möchte) gut und ausreichend effizient aus Flächenstrukturen errechnen kann, werden wir nicht darum herum kommen, diese Datenstruktur noch manuell zu pflegen, ggf. eben zusätzlich zu Flächen.

4

… und Steigungen, richtungsabhängige Verkehrsbeschränkungen und Abbiegerestriktionen. :wink:

Gruß,
ajoessen

5

Wenn man möchte, wäre das kein Problem. Allerdings würde das wie bei 3D Gebäuden etwas Disziplin vorraussetzen. Man könnte die Fläche vom Startpunkt aus betrachten (in Straßenmitte). Damit hätte man den Bezugspunkt für die richtungsabhängigen Dinge.

6

LOL

“kein Problem”, “etwas Disziplin” und OSM: Davon kann man sich zwei beliebig aussuchen, dafuer muss man dann aber zwangslaeufig auf das dritte verzichten.

Gruss
Torsten

7

Soweit ich weiß haben diejenigen sie seit mehreren Jahren im Geschäft sitzen auch keine bessere Lösung als eine doppelte Erfassung der Objekte mit zwei logischen Ebenen: die eine für´s Routing die andere für die Darstellung. Es ist natürlich nicht schön, dass ein Objekt zweimal vorhanden ist, die Lösung ist aber plump und einfach, also fehlerresistent und leicht begreiflich für Anfänger.

8

Was nicht unterschätzt werden sollte.

Gruß
ajoessen

9

Naja, der größte Teil des Routings ist ja nicht, ne nette Linie in die Karte zu zeichnen, sondern eine Liste von Anweisungen im Stile von “An der nächsten Kreuzung links abbiegen in die Hauptstraße”. Und dafür ist es ja völlig wurscht, ob man nun eine Linie in der Straßenmitte oder eine ganze Straße betrachtet.

@viw: Klar kann man Flächen von einem Startpunkt aus betrachten. Aber wie oben schon erwähnt, fände ich einen Rotationswert für Flächen einfacher und verständlicher. Der Editor könnte in entsprechender Zoomstufe einfach einen Pfeil zeigen und per Klick darauf kann man den drehen oder einen exakten Wert für die Rotation (bspw. Abweichung von der Nordrichtung) angeben. Das würde auch das 3D Rendering (bzw. das Mappen für’s 3D Rendering) wesentlich leichter gestalten. Stellt sich nur die Frage: Ist es mathematisch/technisch mit vertretbarem Aufwand möglich aus der Rotation der (kovexen) Fläche herauszufinden in welche Richtungen ein bestimmtes Tag gilt oder nicht? Und: Wenn wir Rotationen speichern, können wir das an den für den Mappern einfacheren konkaven Flächen (mit Löchern) machen oder funktioniert das nicht (was ich befürchte) und wenn nicht, was kann man tun um es dem Mapper möglichst einfach zu machen.

@marek kleciak: Dass auch die Profis (noch) nichts besseres haben, ist ein gutes Argument. Einfacher, verständlicher und vor allem fehlerresistenter, gerade für Anfänger, denke ich aber nicht, dass es ist. Ohne logischen Zusammenhang zwischen den Objekten können sich leicht Unterschiede einschleichen, die dann manchmal kaum nachvollzogen werden können (bspw. eine Straße, deren Linienrepräsentation ein surface=gravel und deren Flächenrepräsentation ein surface=asphalt hat - was ist den nun korrekt? Oder die Fläche und die Linie werden an unterschiedliche Orte verschoben). So gesehen denke ich, dass wir mit einem System, in dem nicht für ein Objekt zwei Datenbankobjekte existieren besser fahren würden. Gerade weil wir gegenüber den Profis nicht die Disziplin und Kenntnis sicherstellen können, um ein System mit zwei unabhängigen (oder gar komplex abhängigen) logischen Ebenen zu betreiben.

@all: Ja, aktuell routet kaum ein Router überhaupt über Flächen und wenn, dann nur am Rand entlang. Und ich habe weder Zeit, Lust und Wissen um das selbst zu ändern noch will ich in irgendeiner Weise den Programmierern unserer Router irgenetwas vorschreiben. Es geht mir nur darum, für die Zukunft darüber zu diskutieren, wie unser Datenmodell aussehen sollte und ob es eben wirklich, wie in bisherigen Vorschlägen, notwendig ist, zusätzlich zu Flächen auch Linien zu erfassen oder nicht. Und eben am Besten so weit auszudiskutieren, dass das Ergebnis für ein komplettes Proposal taugt und die Schlüsse daraus auch gleich als Wünsche für die Funktionalität der nächsten API Version aufgenommen werden können. Sollte aber jemand so einen Router schreiben wollen, fände ich das durchaus gut und würde nach Möglichkeit auch gerne dabei helfen.

Und, bei allen berechtigt angesprochenen Problemen mit (reinen) Flächen: Das System würde auch manches Problem, das wir aktuell haben beheben. Allen voran: Mappen von getrennten Richtungen und zusammengehörigen Wegen. Es gibt ja bereits Tags für unterschiedliche Straßeneigenschaften in unterschiedliche Richtungen, aber bei komplexeren Situationen wird es schnell unübersichtlich. Das Problem ist, dass unsere linienhafte Repräsentation Wechsel nur an Knotenpunkten kennt, weshalb getrennte Linien nur da taugen, wo eben nicht überall gewechselt werden kann (aka bauliche Trennung). Mit Flächen ist das völlig problemlos: Überall, wo die Flächen aneinandergrenzen (aka zwei Punkte in Folge teilen) ist ein Wechsel überall möglich. Wo bauliche Trennung (und sei es nur der doppelte Mittelstreifen) vorliegt, teilen sich die Flächen keine Knoten und ein Wechsel ist nicht möglich. Es sind auch Dinge möglich wie: Zwischen Straße und Fußweg ist ein Grasstreifen. Definiert man den als begehbar, können Fußgänger auch darüber geroutet werden. Oder es liegt eine (flächig gemappte) barrier dazwischen, dann ist logischerweise kein Wechsel möglich. Insofern sehe ich mindestens ebensoviele Vor- wie Nachteile, so dass es es wert wäre, sich für die Zukunft genauer mit solchen Konzepten zu befassen.

10

Wir haben heute doch schon genug Probleme mit übersichtlicheren Flächen wie landuse/natural. Da will ich mir das bei Straßen, die zum überwiegenden Teil sehr gut durch Linien repräsentiert werden können, nicht auch noch antun.

In Dortmund wurde das letztes Jahr bereits versucht. Meine Erfahrung ist, dass man dort wo Straßen (zusätzlich) als Flächen gemappt sind, praktisch keine Änderungen oder Fehlerbereinigung mehr durchführen kann, da alles viel zu vollgestopft ist.

Auf Plätzen, wo man beliebig fahren/gehen kann/darf sind die Flächen in Ordnung, bei allem anderen verkomplizieren sie die Dinge nur unnötig.

JM2C
Edbert (EvanE)

11

+1 (Wegen der Probleme mit Flächen und MP’s)
Wenn alle Straßen/Spuren width-Angaben hätten, könnten die Renderer das doch auswerten und daraus Flächendarstellungen generieren :confused:
Blieben “nur noch” die Plätze.

12

Für den Einwand nr. 1 habe ich eine Antwort: Flächenbeschreibung (z.B surface) hat Vorrang vor Linienbeschreibung, da an einer Fläche (bzw. Flächen) wesentlich mehr abgebildet werden kann ale an einem Vektor. Bei nr. 2 würde ich eine automatisierte Prüfung einführen die anzeigt dass ein Fehler vorliegt: Etwa ähnlich der anzeige der doppelten Elemente in Potlatch 2.

Grüße,
Marek

13

@Edbert: Ist das nicht eher ein Problem der unzureichender Editoren und allgemein der größer werdenden Datenmengen? Und glaubst du nicht, dass das Problem zumindest etwas geringer würde, wenn man die zusätzlichen Linien entfallen lassen könnte (und die Notwendigkeiten, die sich aus der Kombination ergeben)?

@hurdygurdyman: width-Angaben sind keine Lösung: Sie sind nicht kontinuierlich (genug), sprich bilden Änderungen im Verlauf des Weges schlecht ab und vor allem: Offensichtliche Fehler (überschneidende Flächen) sind praktisch nicht direkt erkennbar. Außerdem bieten sie nicht die anderen von mir herausgestellten Vorteile von Flächen, beispielsweise das Routing quer zur Straßenrichtung.

@marek kleciak: Ja, aber das ist doch Flickwerk. Wer soll denn da durchblicken, wenn sich Werte widersprechen und Linien oder Flächen ohne Partner an falschen Orten rumfliegen. Sicher, man kann so Eindeutigkeit wiederherstellen - aber weder wird es dabei einfacher noch hat es sonst nennenswerte Vorteile. Es bindet nur Kräfte, die man sinnvoller einsetzen könnte.

14

Ja, OSM ist doch ein Flickwerk :slight_smile: :slight_smile: :slight_smile: Die Werte dürfen sich widersprechen, da im Zweifelsfall abhängig der Zoomstufe entwefder die eine, oder die andere ebene genommen wird.
Ein Nennenswerter Vorteil ist die Echte Flächendarstellung also die verbesserte Wiedererkennung der Straßensituation unter OSM. Und dies ist wichtig da unter OSM schon erste Augmented Reality Lösungen entstehen (wie der Zufall es will, wieder Lodz : http://www.youtube.com/watch?v=cM3L-var7uI )

Ein sinvoller Argument ist: es bindet die Kräfte: Ich habe soeben gesehen, wie ungenau z.B. New York gemappt ist, da sind grundlegende Dinge die fehlen. Trotzdem, OSM hat sich immer ungleich entwickelt…

15

Klar, aber gegenüber reinen Flächen ist die echte Flächendarstellung kein Vorteil. Und dass es an unterschiedlichen Stellen ungenau oder unterschiedlich gemapptes gibt, ist ja auch ganz normal. Ich meine nur, dass es keine gute Idee ist, zu einem realen Objekt mehrere sich widersprechende Angaben in der Datenbank zu haben. Also, wo ist der Vorteil des doppelt-mappens?

16

Die zusätzliche Komplexität ist nicht unnötig. Es ist technisch unmöglich, die Informationen, die man mit Flächen darstellen könnte, in Linien mit Tags zu verpacken.

Das liefert aber keine guten Ergebnisse, denn Straßen in bebauten Gebieten haben keine konstante Breite. Und selbst dort, wo die Breite einigermaßen gleichmäßig ist, ist es praktisch unmöglich für Mapper, sie genau genug anzugeben. Ich habe bei allen meinen 3D-Experimenten noch nie den Fall gehabt, dass eine Straße mit width-Tag exakt zu den eingezeichneten Gebäuden gepasst hätte.

errts Vorschlag, nur Flächen zu mappen, ist zwar technische Zukunftsmusik, aber im großen und ganzen technisch umsetzbar - und ich kann mir vorstellen, dass unsere Renderer und Router in einigen Jahren gut genug dafür sind. Linien mit width hingegen können für etliche Straßen nicht mal in der Theorie funktionieren.

17

Ich glaube, dass die Probleme geringer werden, wenn man die Flächen weg lässt.

Edbert (EvanE)

18

ok, aber solange wir nicht flächendeckend ausreichend detaillierte und aktuelle Luftbilder zur Verfügung haben, wäre das eine Möglichkeit, Straßenflächen näherungsweise genauer abzubilden.
Die Frage ist doch, wo OSM hin will. Soll es eine möglichst effektive Datenbasis zum Routing und zur Orientierung sein, dann reicht Generalisierung bzw. Abstraktion. Soll es eine möglichst genaue Abbildung der Wirklichkeit sein, kann man auch gleich die Luftbilder selbst nehmen.

19

Wohin OSM will würde ich nicht so festlegen. Denn es gab und gibt immer wieder den Aufschrei, wenn es um Flächen auf und in anderen Flächen geht. Es gibt also Menschen, welche auswerten wollen wieviel Fläche von Gebäuden belegt ist. Daher bemängeln sie das mit Verfügbarkeit von Luftbildern Gebäude in Gebäuden gezeichnet werden.
Gleiches gilt für Flächen von Wohngebieten. Hier wird immer wieder darüber diskutiert ob Straßen dazu gehören oder nicht. Warum soll es nicht auch Menschen geben, welche wissen wollen wieviel Fläche durch Verkehrsinfrastruktur beansprucht wird. Im übrigen gibts darüber sogar Statistiken, weil solche Kennzahlen für die Lebensqualität herangezogen werden.
Die Frage bei den Flächen wäre für mich eher noch wie wir dann Dinge wie Gleise darstellen möchten.

20

Die Frage, wo OSM hin will, finde ich sehr wichtig.
Eine möglichst effektive Datenbasis zum Routing bzw. zur Orientierung ist das eine.
Flächenauswertungen und anderes mehr, was damit zusammenhängt, erinnert mich an Katasterkarten und ist etwas ganz anderes.
Warum muß man das alles in einen Topf werfen?
Daß es sowohl für das Eine als für das Andere Bedarf gibt, ist offensichtlich, sonst würden wir das hier nicht diskutieren.
Auch daß größer werdene Interessenkonflikte und Probleme mit der Wartbarkeit der unvermeidbar sind, wenn wir bei der aktuellen Form des Datenmanagements bleiben, zeichnet sich deutlich in diesen Diskussionen ab.

Wie an anderer Stelle bereits dargelegt ist es eine Frage der Zielsetzung, was als notwendig und sinnvoll erachtet wird. Für nicht nur meine Zielsetzung ist das Erfassen der Straßen in Flächenform völlig überflüssig. Und da es mindestens zu einer Verdoppelung der auf die Straßen und Wege entfallenden Datenmenge führt, und das Konsequenzen bei der Handhabung der Daten hat (Übersichtlichkeit, Downloadmengen/-zeit > Traffic, filtern, rendern …) lehne ich es ab, diese Idee zu unterstützen.
Da die Flächendarstellung der Straßen nicht für alle Anwendungen sinnvoll ist, wird das Rendern der Straßen unnötig kompliziert bzw. verlängert, wenn die Flächen wieder in Linien zurückgerechnet werden müssen. Statt der auch bei Schnitten unkompliziert zu handhabenden Linien erhalten wir mit Sicherheit nicht nur einfach Flächen, sondern auch garantiert unübersichtliche Multipolygone, deren Flächen sich aus mehreren Randlinien zusammensetzen und die dann beim Schneiden dieselben Probleme machen, wie die als Multipolygone erfaßten Flüsse.

Wenn denn unbedingt Straßenflächen erfaßt werden sollen, dann bitte auf einer Art separaten Layer, auf den man beispielsweise mit JOSM umschalten können sollte. Die einfachen Linien müssen für die unkomplizierte Auswertung erhalten bleiben. Ich finde sie unverzichtbar.

Und da wir gerade bei Zukunftsmusik sind: Wie in einem guten Zeichenprogramm müßte man grundsätzlich die Daten je nach Art des Objektes auf verschiedenen Layern ablegen können. Anhand der Tags würde dann automatisch geprüft, ob der gewählte Layer der richtige ist. Unbekannte Tag/Key-Kombinationen landen in einem separaten Layer > Prüfungsebene. So fallen Tippfehler und neue Kreationen sofort auf. Im ersten Fall (Tippfehler) korrigiert der Mapper selbst. Im zweiten Fall haben die Katenbastler die Möglichkeit nachzusehen, was es an Neuerungen gibt und können entscheiden, ob sie die neuen Ideen ignorieren oder in ihre Renderregeln einbauen wollen. …
Anstatt für bestimmte Anwendungen die Daten mühsam nach relevanten Tags zu durchforsten und “kleinzufiltern”, wählt man für das Download bestimmte Datenkategorien aus: Straßen, Wege, Landflächen, bebaute Flächen, Grenzen, POIs, Landpunkte etc., filtert diese gegebenenfalls noch nach individuellen Kriterien und läßt sie dann vom Renderer verarbeiten.
Schon jetzt bietet z.B. Composer an, zwei verschiedene *.osm-Dateien gemeinsam rendern zu lassen. Dieses System müßte so erweitert werden, daß beliebig viele OSM-Dateien kombiniert werden können.

… Naja, Zukunftsmusik eben … OSM-Utopia sozusagen … :wink:

Gruß
tippeltappel