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,
)

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

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é)

La bibliothèque d’analyse de réseau a été créée en exportant les fonctions de l’extension principale RoadGraph. Vous pouvez en utiliser les méthodes dans des extensions ou directement dans la console Python.

18.1. Information générale

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)

18.2. 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.

Comme source de données, on peut utiliser n’importe quelle couche vecteur de polylignes. Les nœuds des polylignes deviendront les sommets du graphe et les segments des polylignes seront les arcs du graphes. Si plusieurs nœuds ont les mêmes coordonnées alors ils composent le même sommet de graphe. Ainsi, deux lignes qui ont en commun un même nœud sont connectées ensemble.

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 vecteur vers le graphe se fait à l’aide du modèle de programmation Builder. Un graphe est construit à l’aide d’un « Director ». Il n’y a qu’un seul Director pour l’instant : QgsVectorLayerDirector. Le director définit les paramètres de base qui seront utilisés pour construire un graphe à partir d’une couche vecteur linéaire, utilisée par le constructeur pour créer le graphe. 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.

Pour calculer les propriétés des bords, on utilise le modèle de programmation strategy. Pour l’instant, seules les stratégies QgsNetworkDistanceStrategy (qui prend en compte la longueur du trajet) et QgsNetworkSpeedStrategy (qui prend également en compte la vitesse) sont disponibles. Vous pouvez mettre en œuvre votre propre stratégie qui utilisera tous les paramètres nécessaires. Par exemple, le plugin RoadGraph utilise une stratégie qui calcule le temps de parcours en utilisant la longueur des bords et la valeur de la vitesse à partir des attributs.

Il est temps de plonger dans le processus.

Tout d’abord, pour utiliser cette bibliothèque, nous devons importer le module d’analyse

from qgis.analysis import *

Ensuite, quelques exemples pour créer un directeur

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
# 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)

Pour construire un directeur, il faut lui fournir une couche vecteur qui sera utilisée comme source pour la structure du graphe ainsi que des informations sur les mouvements permis sur chaque segment de route (sens unique ou déplacement bidirectionnel, direct ou inversé). L’appel au directeur se fait de la manière suivante

1
2
3
4
5
6
director = QgsVectorLayerDirector(vectorLayer,
                                      directionFieldId,
                                      directDirectionValue,
                                      reverseDirectionValue,
                                      bothDirectionValue,
                                      defaultDirection)

Voici la liste complète de la signification de ces paramètres:

  • vectorLayer — couche vecteur utilisée pour construire le graphe

  • directionFieldId — index du champ de la table d’attribut où est stockée l’information sur la direction de la route. Si -1 est utilisé, cette information n’est pas utilisée. Un entier.

  • directDirectionValue — valeur du champ utilisé pour les routes avec une direction directe (déplacement du premier point de la ligne au dernier). Une chaîne de caractères.

  • reverseDirectionValue — valeur du champ utilisé pour les routes avec une direction inverse (déplacement du dernier point de la ligne au premier). Une chaîne de caractères.

  • bothDirectionValue — valeur du champ utilisé pour les routes bidirectionelles (pour ces routes, on peut se déplacer du premier point au dernier et du dernier au premier). Une chaîne de caractères.

  • defaultDirection — direction de la route par défaut. Cette valeur sera utilisée pour les routes où le champ directionFieldId n’est pas défini ou a une valeur différente de l’une des trois valeurs spécifiées ci-dessus. Les valeurs possibles sont :

    • « QgsVectorLayerDirector.DirectionForward » — Aller simple direct

    • QgsVectorLayerDirector.DirectionBackward — Inversion à sens unique

    • QgsVectorLayerDirector.DirectionBoth — Dans les deux sens

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

1
2
3
4
5
6
7
# 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)

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

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

Nous pouvons maintenant utiliser le constructeur, qui va créer le graphique. Le constructeur de la classe QgsGraphBuilder prend plusieurs arguments :

  • crs — système de référence des coordonnées à utiliser. Argument obligatoire.

  • otfEnabled — utiliser la reprojection « à la volée » ou non. Par défaut const:True (utilisez OTF).

  • TopologyTolerance — tolérance topologique. La valeur par défaut est 0.

  • ellipsoidID — ellipsoïde à utiliser. Par défaut « WGS84 ».

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

Nous pouvons également définir plusieurs points qui seront utilisés dans l’analyse, par exemple:

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

Maintenant que tout est en place, nous pouvons construire le graphe et lier ces points dessus:

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

La construction du graphe peut prendre du temps (qui dépend du nombre d’entités dans la couche et de la taille de la couche). tiedPoints est une liste qui contient les coordonnées des points liés. Lorsque l’opération de construction est terminée, nous pouvons récupérer le graphe et l’utiliser pour l’analyse:

graph = builder.graph()

Avec le code qui suit, nous pouvons récupérer les index des arcs de nos points:

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

18.3. Analyse de graphe

L’analyse de graphe est utilisée pour trouver des réponses aux deux questions: quels arcs sont connectés et comment trouver le plus court chemin ? Pour résoudre ces problèmes la bibliothèque d’analyse de graphe fournit l’algorithme de Dijkstra.

L’algorithme de Dijkstra trouve le plus court chemin entre un des arcs du graphe par rapport à tous les autres en tenant compte des paramètres d’optimisation. Ces résultats peuvent être représentés comme un arbre du chemin le plus court.

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.

  • Tous les autres arcs n’ont qu’un seul arc entrant.

  • 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 de 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 est plus rapide et utilise la mémoire de manière plus efficace.

La méthode shortestTree est utile lorsque vous voulez vous promener dans l’arbre qui a le chemin le plus court. Elle crée toujours un nouvel objet graphique (QgsGraph) et accepte trois 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 deux tableaux. Dans le premier tableau, l’élément n contient l’index du front entrant ou -1 s’il n’y a pas de front entrant. Dans le second tableau, l’élément n contient la distance entre la racine de l’arbre et le sommet n ou DOUBLE_MAX si le sommet n est inaccessible depuis la racine.

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

Voici un code très simple pour afficher l’arbre du chemin le plus court en utilisant le graphique créé avec la méthode shortestTree (sélectionner la couche de chaîne de caractères dans le panneau couches et remplacer les coordonnées par les vôtres).

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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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

Même chose mais en utilisant la méthode dijkstra.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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, costs) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)

for edgeId in tree:
  if edgeId == -1:
    continue
  rb = QgsRubberBand(iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (graph.vertex(graph.edge(edgeId).fromVertex()).point())
  rb.addPoint (graph.vertex(graph.edge(edgeId).toVertex()).point())

18.3.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 final B et commençons à parcourir l’arbre du point B au point A. L’algorithme complet peut être écrit sous la forme :

1
2
3
4
5
6
7
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

A ce niveau, nous avons le chemin, sous la forme d’une liste inversée d’arcs (les arcs sont listés dans un ordre inversé, depuis le point de la fin vers le point de démarrage) qui seront traversés lors de l’évolution sur le chemin.

Voici un exemple de code pour la console Python QGIS (vous devrez peut-être charger et sélectionner une couche de chaîne de caractères dans la table des matières et remplacer les coordonnées dans le code par les vôtres) qui utilise la méthode shortestTree.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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')
builder = QgsGraphBuilder(vectorLayer.sourceCrs())
director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth)

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 than layer's CRS
for p in route:
    rb.addPoint(p)

Et voici le même échantillon mais en utilisant la méthode dijkstra.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
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)
idxEnd = graph.findVertex(tStop)

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

if tree[idxEnd] == -1:
    raise Exception('No route!')

# Total cost
cost = costs[idxEnd]

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

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

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

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

18.3.2. Surfaces de disponibilité

La surface de disponibilité d’un arc A est le sous-ensemble des arcs du graphe qui sont accessibles à partir de l’arc A et où le coût des chemins à partir de A vers ces arcs ne dépasse pas une certaine valeur.

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.

Un problème plus difficile à régler est d’obtenir les frontières de la surface de disponibilité. La frontière inférieure est constituée par l’ensemble des arcs qui sont toujours accessibles et la frontière supérieure est composée des arcs qui ne sont pas accessibles. En fait, c’est très simple: c’est la limite de disponibilité des arcs de l’arbre du plus court chemin pour lesquels l’arc source de l’arc est accessible et l’arc cible ne l’est pas.

Voici un exemple:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
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(), True)
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(), True)
    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))