Important

La traduction est le fruit d’un effort communautaire auquel vous pouvez vous joindre. Cette page est actuellement traduite à 58.93%.

19. Bibliothèque d’analyse de réseau

Indication

Les extraits de code sur cette page nécessitent les importations suivantes si vous êtes en dehors de la console pyqgis :

from qgis.core import (
  QgsVectorLayer,
  QgsPointXY,
)

La bibliothèque d’analyse de réseau peut être utilisée pour :

• créer un graphe mathématique à partir des données géographiques (couches vecteurs de polylignes)

• mettre en œuvre les méthodes de base de la théorie des graphes (actuellement, seul l’algorithme de Dijkstra est utilisé)

Voici un résumé d’un cas d’utilisation typique:

1. créer un graphe depuis les données géographiques (en utilisant une couche vecteur de polylignes)

2. lancer une analyse de graphe

3. utiliser les résultats d’analyse (pour les visualiser par exemple)

19.1. Construire un graphe

La première chose à faire est de préparer les données d’entrée, c’est à dire de convertir une couche vecteur en graphe. Les actions suivantes utiliseront ce graphe et non la couche.

As a source we can use any polyline vector layer. Nodes of the polylines become graph vertices, and segments of the polylines are graph edges. If several nodes have the same coordinates then they are the same graph vertex. So two lines that have a common node become connected to each other.

Pendant la création d’un graphe, il est possible de « forcer » (« lier ») l’ajout d’un ou de plusieurs points additionnels à la couche vecteur d’entrée. Pour chaque point additionnel, un lien sera créé: le sommet du graphe le plus proche ou l’arc de graphe le plus proche. Dans le cas final, l’arc sera séparé en deux et un nouveau sommet sera ajouté.

Les attributs de la couche vecteur et la longueur d’un segment peuvent être utilisés comme propriétés du segment.

La conversion d’une couche vectorielle vers le graphe se fait en utilisant le modèle de programmation Builder. Un graphe est construit en utilisant ce qu’on appelle un Director. Il n’y a qu’un seul Director pour le moment : QgsVectorLayerDirector. Le Director définit les paramètres de base qui seront utilisés pour construire un graphique à partir d’une couche de vecteurs linéaires, utilisée par le builder pour créer le graphique. Actuellement, comme dans le cas du director, un seul constructeur existe : QgsGraphBuilder, qui crée des objets QgsGraph. Vous pouvez vouloir implémenter vos propres constructeurs qui construiront un graphe compatible avec des bibliothèques telles que BGL ou NetworkX.

To calculate edge properties the programming pattern strategy is used. For now only QgsNetworkDistanceStrategy strategy (that takes into account the length of the route) and QgsNetworkSpeedStrategy (that also considers the speed) are available. You can implement your own strategy that will use all necessary parameters.

Il est temps de plonger dans le processus.

1. First of all, to use this library we should import the analysis module:

   from qgis.analysis import *
   

2. Then some examples for creating a director:

   # Don't use information about road direction from layer attributes,
   # all roads are treated as two-way
   director = QgsVectorLayerDirector(
       vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
   )
   

   # 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 = QgsVectorLayerDirector(
       vectorLayer, 5, "yes", "1", "no", QgsVectorLayerDirector.DirectionBoth
   )
   

   To construct a director, we should pass a vector layer that will be used as the source for the graph structure and information about allowed movement on each road segment (one-way or bidirectional movement, direct or reverse direction). The call looks like this (find more details on the parameters at qgis.analysis.QgsVectorLayerDirector):

   director = QgsVectorLayerDirector(
       vectorLayer,
       directionFieldId,
       directDirectionValue,
       reverseDirectionValue,
       bothDirectionValue,
       defaultDirection,
   )
   

3. Il est ensuite impératif de créer une stratégie de calcul des propriétés des arcs:

   # The index of the field that contains information about the edge speed
   attributeId = 1
   # Default speed value
   defaultValue = 50
   # Conversion from speed to metric units ('1' means no conversion)
   toMetricFactor = 1
   strategy = QgsNetworkSpeedStrategy(attributeId, defaultValue, toMetricFactor)
   

4. Et d’informer le directeur à propos de cette stratégie:

   director = QgsVectorLayerDirector(vectorLayer, -1, "", "", "", 3)
   director.addStrategy(strategy)
   

5. Now we can use the builder, which will create the graph, using the QgsGraphBuilder class constructor.

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

6. Also we can define several points, which will be used in the analysis. For example:

   startPoint = QgsPointXY(1179720.1871, 5419067.3507)
   endPoint = QgsPointXY(1180616.0205, 5419745.7839)
   

7. Now all is in place so we can build the graph and « tie » these points to it:

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

   Building the graph can take some time (which depends on the number of features in a layer and layer size). tiedPoints is a list with coordinates of « tied » points.

8. When the build operation is finished we can get the graph and use it for the analysis:

   graph = builder.graph()
   

9. With the next code we can get the vertex indexes of our points:

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

19.2. Analyse de graphe

Networks analysis is used to find answers to two questions: which vertices are connected and how to find a shortest path. To solve these problems the network analysis library provides Dijkstra’s algorithm.

Dijkstra’s algorithm finds the shortest route from one of the vertices of the graph to all the others and the values of the optimization parameters. The results can be represented as a shortest path tree.

L’arbre du chemin le plus court est un graphique pondéré dirigé (ou plus précisément un arbre) ayant les propriétés suivantes :

• Seul un arc n’a pas d’arcs entrants: la racine de l’arbre.

• all other vertices have only one incoming edge

• Si un arc B est atteignable depuis l’arc A alors le chemin de A vers B est le seul chemin disponible et il est le chemin optimal (le plus court) sur ce graphe.

Pour obtenir l’arbre du chemin le plus court, utilisez les méthodes shortestTree() et dijkstra() de la classe QgsGraphAnalyzer. Il est recommandé d’utiliser la méthode dijkstra() car elle fonctionne plus rapidement et utilise la mémoire de manière plus efficace.

The shortestTree() method is useful when you want to walk around the shortest path tree. It always creates a new graph object (QgsGraph) and accepts three variables:

• source — Graphique d’entrée

• startVertexIdx — index du point sur l’arbre (la racine de l’arbre)

• criterionNum — nombre de propriétés de bord à utiliser (à partir de 0).

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

La méthode dijkstra() a les mêmes arguments mais renvoie un tuple de tableaux :

• In the first array, element n contains index of the incoming edge or -1 if there are no incoming edges.

• In the second array, element n contains the distance from the root of the tree to vertex n or DOUBLE_MAX if vertex n is unreachable from the root.

(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() or the dijkstra() method (select linestring layer in Layers panel and replace coordinates with your own).

Avertissement

Utilisez ce code uniquement à titre d’exemple, il crée beaucoup d’objets QgsRubberBand et peut être lent sur de grands ensembles de données.

shortestTree()dijkstra()

from qgis.core import *
from qgis.gui import *
from qgis.analysis import *
from qgis.PyQt.QtCore import *
from qgis.PyQt.QtGui import *

vectorLayer = QgsVectorLayer(
    "testdata/network.gpkg|layername=network_lines", "lines"
)
director = QgsVectorLayerDirector(
    vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
)
strategy = QgsNetworkDistanceStrategy()
director.addStrategy(strategy)
builder = QgsGraphBuilder(vectorLayer.crs())

pStart = QgsPointXY(1179661.925139, 5419188.074362)
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.edgeCount():
    rb = QgsRubberBand(iface.mapCanvas())
    rb.setColor(Qt.red)
    rb.addPoint(tree.vertex(tree.edge(i).fromVertex()).point())
    rb.addPoint(tree.vertex(tree.edge(i).toVertex()).point())
    i = i + 1

19.2.1. Trouver les chemins les plus courts

Pour trouver le chemin optimal entre deux points, l’approche suivante est utilisée. Les deux points (début A et fin B) sont « liés » au graphique lors de sa construction. Ensuite, en utilisant la méthode shortestTree() ou dijkstra() nous construisons l’arbre du chemin le plus court avec une racine au point de départ A. Dans le même arbre, nous trouvons également le point de fin B et commençons à parcourir l’arbre du point B au point A. L’algorithme complet peut être écrit sous la forme :

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

At this point we have the path, in the form of the inverted list of vertices (vertices are listed in reversed order from end point to start point) that will be visited during traveling by this path.

Here is the sample code for QGIS Python Console (you may need to load and select a linestring layer in TOC and replace coordinates in the code with yours) that uses the shortestTree() or dijkstra() method:

shortestTree()dijkstra()

from qgis.core import *
from qgis.gui import *
from qgis.analysis import *

from qgis.PyQt.QtCore import *
from qgis.PyQt.QtGui import *

vectorLayer = QgsVectorLayer(
    "testdata/network.gpkg|layername=network_lines", "lines"
)
director = QgsVectorLayerDirector(
    vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
)
strategy = QgsNetworkDistanceStrategy()
director.addStrategy(strategy)

builder = QgsGraphBuilder(vectorLayer.sourceCrs())

startPoint = QgsPointXY(1179661.925139, 5419188.074362)
endPoint = QgsPointXY(1180942.970617, 5420040.097560)

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

graph = builder.graph()
idxStart = graph.findVertex(tStart)

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

idxStart = tree.findVertex(tStart)
idxEnd = tree.findVertex(tStop)

if idxEnd == -1:
    raise Exception("No route!")

# Add last point
route = [tree.vertex(idxEnd).point()]

# Iterate the graph
while idxEnd != idxStart:
    edgeIds = tree.vertex(idxEnd).incomingEdges()
    if len(edgeIds) == 0:
        break
    edge = tree.edge(edgeIds[0])
    route.insert(0, tree.vertex(edge.fromVertex()).point())
    idxEnd = edge.fromVertex()

# Display
rb = QgsRubberBand(iface.mapCanvas())
rb.setColor(Qt.green)

# This may require coordinate transformation if project's CRS
# is different from layer's CRS
for p in route:
    rb.addPoint(p)

19.2.2. Surfaces de disponibilité

The area of availability for vertex A is the subset of graph vertices that are accessible from vertex A and the cost of the paths from A to these vertices are not greater that some value.

Plus clairement, cela peut être illustré par l’exemple suivant: « Il y a une caserne de pompiers. Quelles parties de la ville peuvent être atteintes par un camion de pompier en 5 minutes ? 10 minutes ? 15 minutes ? » La réponse à ces questions correspond aux surface de disponibilité de la caserne de pompiers.

Pour trouver les zones de disponibilité, nous pouvons utiliser la méthode dijkstra() de la classe QgsGraphAnalyzer. Il suffit de comparer les éléments du tableau des coûts avec une valeur prédéfinie. Si le coût [i] est inférieur ou égal à une valeur prédéfinie, alors le sommet i est à l’intérieur de la zone de disponibilité, sinon il est à l’extérieur.

A more difficult problem is to get the borders of the area of availability. The bottom border is the set of vertices that are still accessible, and the top border is the set of vertices that are not accessible. In fact this is simple: it is the availability border based on the edges of the shortest path tree for which the source vertex of the edge is accessible and the target vertex of the edge is not.

Here is an example:

director = QgsVectorLayerDirector(
  vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
)
strategy = QgsNetworkDistanceStrategy()
director.addStrategy(strategy)
builder = QgsGraphBuilder(vectorLayer.crs())


pStart = QgsPointXY(1179661.925139, 5419188.074362)
delta = iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1

rb = QgsRubberBand(iface.mapCanvas())
rb.setColor(Qt.green)
rb.addPoint(QgsPointXY(pStart.x() - delta, pStart.y() - delta))
rb.addPoint(QgsPointXY(pStart.x() + delta, pStart.y() - delta))
rb.addPoint(QgsPointXY(pStart.x() + delta, pStart.y() + delta))
rb.addPoint(QgsPointXY(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 = 1500.0
i = 0
tree.reverse()

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

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