Netzwerkanalysebibliothek¶

Allgemeine Informationen¶

Ein typischer Anwendungsfall sieht so aus:

1. Graphen aus Geodaten erstellen (Typischerweise Polylinien Vektorlayer)

2. Graphenanalyse durchführen

3. Analyseergebnisse verwenden (z.B. für Visualisierungszwecke)

Einen Graphen erstellen¶

Als erstes müssen die Eingabedaten vorbereitet werden, d.h. ein Vektorlayer muss in einen Graphen konvertiert werden. Alle weiteren Aktionen verwenden diesen Graphen und nicht den Vektorlayer.

Als Quelle können wir jeden Polylinienvektorlayer verwenden. Vertices der Polylinien werden zu Knoten des Graphen und Segmente der Polylinien werden zu Kanten des Graphen. Wenn mehrere Vertices die gleichen Koordinaten haben, dann repräsentieren sie den selben Knoten. So werden zwei Kanten, die einen gemeinsamen Knoten haben, miteinander verbunden.

Darüber hinaus ist es während der Graphenerstellung möglich, eine beliebige Anzahl zusätzlicher Punkte auf den Eingabevektorlayer zu “fixieren” (engl. “tie”). Für jeden zusätzlichen Punkt wird eine Übereinstimmung gefunden, entweder der nächstgelegene Knoten des Graphen oder die nächstgelegene Kante. Im letzteren Fall wird die Kante geteilt und ein neuer Knoten hinzugefügt.

Vektorlayerattribute und die Länge eines Segements können als Eigenschaften einer Kante verwendet werden.

Converting from a vector layer to the graph is done using the Builder programming pattern. A graph is constructed using a so-called Director. There is only one Director for now: QgsLineVectorLayerDirector. The director sets the basic settings that will be used to construct a graph from a line vector layer, used by the builder to create the graph. Currently, as in the case with the director, only one builder exists: QgsGraphBuilder, that creates QgsGraph objects. You may want to implement your own builders that will build a graphs compatible with such libraries as BGL or NetworkX.

To calculate edge properties the programming pattern strategy is used. For now only QgsDistanceArcProperter strategy is available, that takes into account the length of the route. You can implement your own strategy that will use all necessary parameters. For example, RoadGraph plugin uses a strategy that computes travel time using edge length and speed value from attributes.

Es ist Zeit, den Prozess näher zu beleuchten.

Um diese Bibliothek zu verwenden, muss zuerst das networkanalysis-Modul importiert werden.

from qgis.networkanalysis import *

Ein paar Beispiele einen director zu erzeugen

# don't use information about road direction from layer attributes,
# all roads are treated as two-way
director = QgsLineVectorLayerDirector(vLayer, -1, '', '', '', 3)

# use field with index 5 as source of information about road direction.
# one-way roads with direct direction have attribute value "yes",
# one-way roads with reverse direction have the value "1", and accordingly
# bidirectional roads have "no". By default roads are treated as two-way.
# This scheme can be used with OpenStreetMap data
director = QgsLineVectorLayerDirector(vLayer, 5, 'yes', '1', 'no', 3)

Um einen Director zu konstruieren, wird ein Vektorlayer übergeben, der als Quelle für die Graphenstruktur dient und Informationen über erlaubte Bewegung auf jedem Straßensegment enthält (uni- oder bidirektionale Bewegung, direkte oder umgekehrte Richtung). Der Aufruf sieht folgendermaßen aus:

director = QgsLineVectorLayerDirector(vl, directionFieldId,
                                      directDirectionValue,
                                      reverseDirectionValue,
                                      bothDirectionValue,
                                      defaultDirection)

Folgende Liste fasst die Bedeutung der Parameter zusammen:

• vl — Vektorlayer, der zur Erstellung des Graphen verwendet wird

• directionFieldId — Index des Feldes der Attributtabelle, in dem Informationen zur Straßenrichtung gespeichert sind. Falls `` -1`` wird diese Informationen nicht benutzt. Ganzzahl (integer).

• directDirectionValue — Feldwert für Straßen mit direkter Richtung (vom ersten zum letzten Punkt). Zeichenkette (string).

• reverseDirectionValue — Feldwert für Straßen mit umgekehrter Richtung (vom letzten zum ersten Punkt). Zeichenkette (string).

• bothDirectionValue — Feldwert für bidirektionale Straßen (in beide Richtungen befahrbar, vom ersten Punkt zum letzten und vom letzten zum ersten). Zeichenkette (string).

• defaultDirection — Voreinstellung für die Straßenrichtung. Dieser Wert wird für die Straßen verwendet, bei denen das Feld directionFieldId nicht gesetzt ist oder sich von einem der drei oben angegebenen Werte unterscheidet. Ganzzahl (integer). 1 zeigt die direkte Richtung an, 2 bezeichnet die umgekehrte Richtung und 3 bezeichnet beide Richtungen.

Nun muss eine Strategie für die Ermittlung der Kanteneigenschaften festgelegt werden

properter = QgsDistanceArcProperter()

und der Director über diese Strategie informiert werden

director.addProperter(properter)

Nun kann der Builder verwendet werden, der den Graphen erzeugt. Der Konstruktor der Klasse QgsGraphBuilder erhält verschiedene Argumente:

• KBS — verwendetes Koordinatenbezugssystem. Verpflichtendes Argument.

• otfEnabled — “Spontanprojektion” verwenden oder nicht. Voreinstellung: True (Spontanprojektion verwenden)

• topologyTolerance — topologische Toleranz. Voreinstellung 0.

• ellipsoidID — Verwendetes Ellipsoid to use. Voreinstellung “WGS84”.

# only CRS is set, all other values are defaults
builder = QgsGraphBuilder(myCRS)

Zusätzlich könne verschiedene Punkte definiert werden, die in der Analyse verwendet werden sollen, z.B.

startPoint = QgsPoint(82.7112, 55.1672)
endPoint = QgsPoint(83.1879, 54.7079)

Nun ist alles bereit um den Graphen erstellen zu können und diese Punkte an den Graphen zu “binden”

tiedPoints = director.makeGraph(builder, [startPoint, endPoint])

Das Erstellen des Graphen kann einige Zeit dauern (abhängig von der Anzahl der Features der Eingabelayers und der Layergröße). `` tiedPoints`` ist eine Liste mit Koordinaten von “angebundenen” Punkten. Wenn der Build-Vorgang abgeschlossen ist, kann der Graph abgerufen und für die Analyse verwendet werden.

graph = builder.graph()

MIt diesem Code erhalten wir die Indizes unserer Knoten

startId = graph.findVertex(tiedPoints[0])
endId = graph.findVertex(tiedPoints[1])

Graphenanalyse¶

Die Netzwerkanalyse wird verwendet, um Antworten auf zwei Fragen zu finden: Welche Knoten sind verbunden und wie findet man einen kürzesten Pfad? Um diese Probleme zu lösen, stellt die Netzwerkanalyse-Bibliothek den Dijkstra-Algorithmus zur Verfügung.

Dijkstras Algorithmus findet den kürzesten Pfad von einem der Knoten des Graphen zu allen anderen und die Werte der Optimierungsparameter. Die Ergebnisse können als ein Baum für die kürzesten Pfade dargestellt werden.

Der Baum der kürzesten Pfade ist ein gerichteter und gewichteter Graph (genauer: Baum) mit den folgenden Eigenschaften:

• Genau ein Knoten besitzt keine ankommende Kante — Die Wurzel des Baumes

• Alle anderen Knoten haben genau eine ankommende Kante

• Wenn Knoten B von Knoten A aus erreichbar ist, dann ist der Pfad von A nach B der einzige verfügbare und optimale (kürzeste) auf diesem Graph

To get the shortest path tree use the methods shortestTree() and dijkstra() of QgsGraphAnalyzer class. It is recommended to use method dijkstra() because it works faster and uses memory more efficiently.

Die Methode shortestTree() ist nützlich, wenn Sie den Baum des kürzesten Pfads durchlaufen möchten. Sie erzeugt immer ein neues Graphenobjekt (QgsGraph) und akzeptiert drei Variablen:

• source — Eingabe Graph

• startVertexIdx — Index eines Knoten des Baumes (Wurzel des Baumes)

• criterionNum — Nummer der zu verwendenden Kanteneigenschaft (start bei 0)

tree = QgsGraphAnalyzer.shortestTree(graph, startId, 0)

Die Methode dijkstra() hat dieselben Argumente, gibt aber zwei Arrays zurück. Im ersten Arrayelement enthält i den Index der ankommenden Kante oder -1, wenn keine ankommenden Kanten vorhanden sind. Im zweiten Arrayelement enthält i den Abstand von der Wurzel des Baums zum Knoten i oder DOUBLE_MAX, wenn der Knoten i vom Stamm nicht erreichbar ist.

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, startId, 0)

Here is some very simple code to display the shortest path tree using the graph created with the shortestTree() method (select linestring layer in TOC and replace coordinates with your own). Warning: use this code only as an example, it creates a lots of QgsRubberBand objects and may be slow on large data-sets.

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.743804, 0.22954)
tiedPoint = director.makeGraph(builder, [pStart])
pStart = tiedPoint[0]

graph = builder.graph()

idStart = graph.findVertex(pStart)

tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

i = 0;
while (i < tree.arcCount()):
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (tree.vertex(tree.arc(i).inVertex()).point())
  rb.addPoint (tree.vertex(tree.arc(i).outVertex()).point())
  i = i + 1

Das Selbe unter Verwendung der dijkstra() Methode

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-1.37144, 0.543836)
tiedPoint = director.makeGraph(builder, [pStart])
pStart = tiedPoint[0]

graph = builder.graph()

idStart = graph.findVertex(pStart)

(tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

for edgeId in tree:
  if edgeId == -1:
    continue
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (graph.vertex(graph.arc(edgeId).inVertex()).point())
  rb.addPoint (graph.vertex(graph.arc(edgeId).outVertex()).point())

assign Т = B
while Т != A
    add point Т to path
    get incoming edge for point Т
    look for point ТТ, that is start point of this edge
    assign Т = ТТ
add point А to path

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

idStart = tree.findVertex(tStart)
idStop = tree.findVertex(tStop)

if idStop == -1:
  print "Path not found"
else:
  p = []
  while (idStart != idStop):
    l = tree.vertex(idStop).inArc()
    if len(l) == 0:
      break
    e = tree.arc(l[0])
    p.insert(0, tree.vertex(e.inVertex()).point())
    idStop = e.outVertex()

  p.insert(0, tStart)
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
idStop = graph.findVertex(tStop)

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

if tree[idStop] == -1:
  print "Path not found"
else:
  p = []
  curPos = idStop
  while curPos != idStart:
    p.append(graph.vertex(graph.arc(tree[curPos]).inVertex()).point())
    curPos = graph.arc(tree[curPos]).outVertex();

  p.append(tStart)

  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(65.5462, 57.1509)
delta = qgis.utils.iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1

rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
rb.setColor(Qt.green)
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() + delta))
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() + delta))

tiedPoints = director.makeGraph(builder, [pStart])
graph = builder.graph()
tStart = tiedPoints[0]

idStart = graph.findVertex(tStart)

(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

upperBound = []
r = 2000.0
i = 0
while i < len(cost):
  if cost[i] > r and tree[i] != -1:
    outVertexId = graph.arc(tree [i]).outVertex()
    if cost[outVertexId] < r:
      upperBound.append(i)
  i = i + 1

for i in upperBound:
  centerPoint = graph.vertex(i).point()
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
  rb.setColor(Qt.red)
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() + delta))
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() + delta))