Wie vereinfacht man ein routingfähiges Netzwerk?

24

Ich habe einen Netzwerkgraphen, den ich vereinfachen muss, um die Anzahl der Kanten zu reduzieren . Die Idee wäre, Knoten, die nahe beieinander liegen, zusammenzuführen und die kurzen Verbindungskanten zu entfernen.

Wie könnte dies in PostGIS oder GRASS erreicht werden? Oder gibt es bessere Ansätze, um ein solches Netzwerk automatisch zu vereinfachen?

Ich habe die ST_SnapToGrid-Funktion bereits ausprobiert, bin aber mit den Ergebnissen nicht zufrieden (grau = Original, schwarz = Schnappschuss):

Bildbeschreibung hier eingeben

Underdunkel
quelle
1
Tun Sie dies, um eine netzwerkbasierte Analyse zu vereinfachen oder zu Anzeigezwecken? Wenn es das erstere ist, welche Analyse wird durchgeführt?
whuber
Es ist für die Analyse auf kürzestem Weg.
Underdunkel
2
Da viele der Algorithmen mit dem kürzesten Pfad O (E + V) sind, benötigen Sie diese Vereinfachung möglicherweise nicht einmal? Im anderen Extremfall können Sie für solche Analysen häufig drastisch aggressivere Vereinfachungen vornehmen. Zum Beispiel kann diese Gruppe von drei parallelen Segmenten und ihren angrenzenden Segmenten auf der linken Seite (die wie ein H-in-a-Box aussehen) durch ein Dreieck ersetzt werden, wenn kein Ursprung oder Ziel in diesen Segmenten liegt. Ich erwähne dies, weil ich sicher bin, dass es (Nicht-GIS-) Code für solche Operationen an (abstrakten) Diagrammen gibt.
Whuber
Möchten Sie die Geometrie der Kanten (z. B. Kurven) beibehalten oder reicht nur die Topologie + Knoten XY aus? Müssen Sie auch sicherstellen, dass Knoten in verschiedenen Z (z. B. Überführungen) nicht zusammenschnappen?
AnserGIS
Topologie ist der Schlüssel. Die Geometrie kann sich etwas ändern. Z Auftrag muss erhalten bleiben.
Underdunkel

Antworten:

7

Das nächste, was ich bisher gesehen habe, ist folgendes:

v.clean input=roads output=snap5rmline tool=snap,rmline thresh=5 

Es schnappt die Straßen mit einer Toleranz von 5 Metern und entfernt alle Null-Längen-Linien. Es ist keine optimale Lösung, da es eher zufällig an einem Scheitelpunkt zu rasten scheint.

Bildbeschreibung hier eingeben

Underdunkel
quelle
In der Tat ist das Ergebnis vielleicht nicht genau, aber die Verwendung von v.clean ist interessant, danke für das Teilen
simo
Ist das Bild im Gras erstellt?
NetConstructor.com
Das Bild zeigt die in QGIS visualisierten Ergebnisse von GRASS v.clean.
Underdunkel
Haben Sie Probleme mit der Aufrechterhaltung "seltsamer Kreuzungen" oder mit der Neigung getrennter Straßen?
Dassouki
Wie wäre es mit der Verarbeitung von ST_SnapToGrid nach v.clean?
kttii
5

Hast du das GRASS v.generalize ausprobiert ?

v.generalizeHier können Sie den Generalisierungsalgorithmus mit dem method- Attribut auswählen . Es gibt eine Menge: douglas, douglas_reduction, lang, reduction, reumann, boyle, slide_averaging, distance_weighting, chaiken, hermite, snakes, network, displacement .

Und weitere Parameter wie threshold, degree_thresh, angle_thresh(je nach gewählten Algorithmus) können Sie helfen, ein genaues Ergebnis zu erhalten.

Hier kommt ein Tutorial .

simo
quelle
Vielen Dank für den Link. Ich versuche es, obwohl ich nicht wirklich verstehe, welche Kombination aus Methoden- und Schwellenwerten das gesuchte Ergebnis liefert.
Underdunkel
Ich kann wirklich keine v.generalize-Methode finden, die das macht, was ich will.
Underdunkel
2
Schade, der Befehl ist reich an vielen Algorithmen, aber wie Sie bereits sagten, ist es wahrscheinlich ziemlich kompliziert, das erwartete Ergebnis zu erzielen. Vielleicht ein Generalisierungsalgorithmus-Guru? Hast du auch die Schlangenmethode ausprobiert ?
Simo
Hier ist er kein Algo-Guru, aber ich finde, dass die Schlangen-Methode für einige meiner v.genralize-Läufe, die ich in der Vergangenheit gemacht habe, die beste ist.
Maning
1
Für das Protokoll wurden die Parameter ab heute in GRASS SVN vereinfacht. Ein Teil von GRASS werden 6.4.2.
MarkusN
4

Ich habe das nicht getan, aber ich denke, ich kann eine Richtung vorschlagen.

  1. Erstellen Sie mit PostGIS eine Topologie für Ihr Diagramm.
  2. Finde alle Knoten mit nur zwei Kanten.
  3. Heile die Ränder.

ST_ModEdgeHeal führt eine Kante mit der anderen zusammen. ST_NewEdgeHeal ersetzt beide durch eine neue Kante.

Handbuch zur PostGIS-Topologie

Sean
quelle
Danke @Sean. Wird das etwas anderes tun, als zwei Kanten zusammenzuführen? Haben Sie eine Idee, wie Sie kurze Kanten entfernen und ihre Knoten miteinander verbinden können?
Underdunkel
@Underdark, ich sehe nichts Einfaches. Sie könnten alles in PL / SQL machen, aber das hilft wahrscheinlich nicht. Können Sie zuerst ST_SnapToGrid ausführen?
Sean
1

@underdark, ich sehe, dass Sie ein Tool zum Verdichten von Linien in Sextante geschrieben haben. Daher schlage ich den folgenden Algorithmus vor, um ein "zufälliges" Fangen eines Ihrer Punkte zu vermeiden.

Wählen Sie die Liniensegmente aus, die Sie basierend auf ihrer Länge entfernen möchten.

Erstellen Sie für jedes dieser Segmente einen Punkt im Mittelpunkt

Löschen Sie das kleine Segment

Jetzt können Sie ST_Snap in PostGIS verwenden (siehe Beispiel hier )

BEARBEITEN: Beachten Sie, dass Sie in Ihrem Fall auch v.net zuerst verwenden könnten , um die Pseudoknoten zu entfernen (Knoten, der nur zwei Linien verbindet).

radouxju
quelle
Bitte erläutern Sie, wie v.net zum Entfernen von Pseudoknoten verwendet werden kann. Danke
Osmjit
0

Weiterleitung, wie Michaël Michaud dies auf der OpenJUMP-Entwicklerliste analysiert hat:

> Interesting question. There has been so much research works about
> generalization that it is surely not a simple task. I have tested the
> following approach with mitigated results :
> - make the layer planar with the noder plugin
> - detect small cycles with the graph plugin
> - merge adjacent cycles
> - create a point inside each cycles surface
> - remove network segments along these cycles (query + DE-9IM)
> - detect roads touching the cycles
> - project the center points of cycles to the road endpoints ==> replace small roundabout by simple nodes
> 
> Possible improvements (probably need a dedicated plugin)
> - make it work on non planar graph (or just remove bridges/tunnels from the graph)
> - replace small edges between two nodes with degree 3+ by a single node,    not only small cycles
> - process iteratively starting with smallest edges/cycles
user30184
quelle
Vielen Dank für das Posten dieser Antwort. Ich bin ein bisschen verwirrt, warum Sie den Graphen in die Ebene zwingen würden. Straßennetze sind schließlich keine ebenen Graphen (Brücken, Tunnel).
Underdunkel
Nur weil Michaël einen schnellen Test mit vorhandenen Grafikwerkzeugen gemacht hat, die er für OpenJUMP geschrieben hat und die derzeit keine nicht-planaren Grafiken unterstützen. Überspringen Sie den ersten Schritt, wenn QGIS und GRASS über ähnliche Tools verfügen, die nicht planare Grafiken unterstützen.
user30184
Ich halte dies für den richtigen Ansatz - trennen Sie das Netzwerk in ebene Graphen. In jedem ebenen Graphen ist das Problem einfacher - zum Beispiel könnte man den obigen Ansatz verwenden oder einfach das TIN kurzer Straßenkanten triangulieren und aussortieren. Extrahieren Sie dann die Straßenränder erneut und fügen Sie die Ebenen zusammen.
AnserGIS