PgRouting - Wie schneide ich Links ab, wenn ich die maximalen Kosten erreiche?

13

Ich habe ein Polylinien-Shapefile, das ein Straßennetz darstellt, und ein zweites Shapefile, das Punkte enthält. Ich möchte PostGIS (vermutlich PgRouting) verwenden, um von diesen Punkten ausgehende Teilnetze oder Versorgungsbereiche zu identifizieren.

Im Wesentlichen hoffe ich, die Frage zu stellen: "Ab Punkt X, wie weit kann ich bei einem Gesamtreisebudget von 1 km entlang des Straßennetzes in eine bestimmte Richtung gehen?" Das Ergebnis wäre ein Satz abgeschnittener Polylinien, die die gesamte Reichweite der Reisemöglichkeiten bei einem Reisebudget von 1 km darstellen.

Diese GRASS-Analyse scheint genau das zu sein, was ich tun möchte (außer ich möchte dies in PostGIS tun): http://www.gdf-hannover.de/lit_html/grass60_v1.2_en/node57.html#sec: optalloc

Dieses nächste Beispiel scheint fast das zu sein, was ich tun möchte, mit der Ausnahme, dass es die Frage zu beantworten scheint, welche Knoten ich mit einem Reisebudget von X Entfernung anfahren könnte. http://underdark.wordpress.com/2011/02/12/drive-time-isochrones/

Die zweite ist nicht ganz die Antwort, nach der ich suche, da ich möchte, dass die Polylinien auf meine Reisestrecke begrenzt werden. Es ist mir egal, ob ich sie bis zu einem Knoten schaffe.

postgis network pgrouting Peter
quelle
Eine Option, die mir einfällt, ist, meine Polylinien irgendwie in viele Punkte aufzuteilen. Das bringt mich der richtigen Antwort näher, scheint aber ziemlich abgedreht zu sein und bringt mich trotzdem nicht ganz dahin.
Peter

Antworten:

2

Ein Gedanke, den ich hatte, war, 1) die Fahrentfernungsroutine auszuführen und 2) die "points_as_polygon" -Routine von pgRouting (die die Alphashape-Funktion aufruft) zu verwenden, um das kleinste Polygon (die kleinsten Polygone) bei gegebenen Kostenentfernungen basierend auf den Punkten der Fahrentfernungsroutine zu erzeugen kehrt zurück. Dann können Sie alle Straßen innerhalb der Polygone auswählen, die Ihnen einen allgemeinen Eindruck vom Reisen vermitteln.

Wenn Sie der Diskussion auf der pgRouting-Benutzerliste nicht gefolgt sind , haben sie in letzter Zeit mehr Optionen besprochen (Thread von Mai und Juni 2011).

RyanKDalton
quelle
1
Interessante Benutzerlistendiskussionen. Schade, dass die Funktion driving_distance fehlerhaft ist.
underdark
1

Da dies wirklich ein Grafikproblem ist, benötigen Sie die Konnektivität / Topologie + Kosteninformationen. Bei pg_routing ist dies die Tabelle, die Sie an die Algorithmen mit dem kürzesten Pfad senden. In diesem Artikel finden Sie Informationen zum Erstellen einer (ich gehe davon aus, dass Sie bereits eine haben). Tut mir leid, dass ich in pg_routing nicht genau die Funktion angeben kann, die dies tut, aber das Schreiben einer sollte machbar sein. Ich kann Ihnen jedoch sagen, dass Sie, wenn Sie immer wieder den kürzesten_Pfad aufrufen, den unten angegebenen Algorithmus immer wieder ausführen und das Ergebnis verwerfen - überhaupt nicht effizient.

Ihre Lösung läuft dann an jeder Ecke, während Sie sie zu einer "Laufliste" hinzufügen und die Kosten berechnen, bis Ihr Budget (dh die Entfernung) überschritten ist. Wenn das Budget akzeptabel ist (dh das Budget wurde nicht überzogen), fügen Sie die Geometrie auch zu einer "Tasche mit akzeptabler Listengeometrie" hinzu. Sie müssen jede Kante nur genau einmal bearbeiten. Für die allerletzte Kante (bei der Ihre Budgets überzogen sind) müssen Sie die Länge ermitteln und die exakte Entfernung interpolieren, die Sie zurücklegen möchten, und dann das Ergebnis zur "akzeptablen Liste" hinzufügen. Ihr Ergebnis ist eine Vereinigung dieser Geometrietasche.

Ragi Yaser Burhum
quelle
1
Der letzte Schritt ist subtil: Einige Kanten können von beiden Endpunkten aus erreicht werden. Dies kann dazu führen, dass Teile beider Enden oder sogar die gesamte Kante eingeschlossen werden, obwohl das Überschreiten der gesamten Kante von einem der Endpunkte aus das Budgetlimit überschreiten würde. Betrachten Sie beispielsweise die Bewegung von Punkt a entlang eines ungerichteten Graphen mit Kanten der Einheitslänge {(a, b), (a, c), (b, c)} und einem Budget von 1,6. Sie können entweder b oder c zu einem Preis von 1 erreichen, wobei Sie noch 0,6 ausgeben müssen. Dies macht jeden Punkt entlang der Kante (b, c) zugänglich.
whuber
Sie sind richtig :) +1
Ragi Yaser Burhum
1

"Ausgehend von Punkt X, wie weit könnte ich bei einem Gesamtfahrplan von 1 km in eine bestimmte Richtung gehen und dem Straßennetz folgen?"

Da Sie nur eine kleine Region berücksichtigen müssen (maximal 1 km Radius), könnten Sie möglicherweise davonkommen, indem Sie die Verknüpfungen in mehrere kleine Teile aufteilen (abhängig von der Genauigkeit, die Sie erreichen möchten) und die erforderlichen Knoten erstellen. Die resultierenden "hochauflösenden" Netzwerke sollten weiterhin verwaltbar sein.

Underdunkel
quelle