Viktigt

Översättning är en gemenskapsinsats du kan gå med i. Den här sidan är för närvarande översatt till 75.00%.

19. Bibliotek för nätverksanalys

Råd

Kodsnuttarna på den här sidan behöver följande import om du befinner dig utanför pyqgis-konsolen:

from qgis.core import (
  QgsVectorLayer,
  QgsPointXY,
)

Biblioteket för nätverksanalys kan användas för att:

• skapa en matematisk graf från geografiska data (polylinje-vektorlager)

• implementera grundläggande metoder från grafteori (för närvarande endast Dijkstras algoritm)

Kortfattat kan ett typiskt användningsfall beskrivas som:

1. skapa graf från geodata (vanligtvis polylinjevektorlager)

2. analys av körgrafer

3. använda analysresultat (t.ex. visualisera dem)

19.1. Bygga upp en graf

Det första du behöver göra — är att förbereda indata, det vill säga att konvertera ett vektorlager till en graf. Alla ytterligare åtgärder kommer att använda denna graf, inte lagret.

Som källa kan vi använda vilket polylinjevektorlager som helst. Polylinjernas noder blir grafvertexer och polylinjernas segment blir grafkanter. Om flera noder har samma koordinater är de samma grafvertex. Två linjer som har en gemensam nod blir alltså kopplade till varandra.

Under skapandet av grafen är det dessutom möjligt att ”fixera” (”knyta”) ytterligare ett antal punkter till det ingående vektorlagret. För varje ytterligare punkt hittas en matchning — den närmaste grafvertexen eller den närmaste grafkanten. I det senare fallet delas kanten och ett nytt vertex läggs till.

Vektorlagrets attribut och längden på en kant kan användas som egenskaper för en kant.

Konvertering från ett vektorlager till grafen görs med hjälp av programmeringsmönstret Builder. En graf konstrueras med hjälp av en så kallad Director. Det finns bara en Director för tillfället: QgsVectorLayerDirector. Director anger de grundläggande inställningar som ska användas för att konstruera en graf från ett linjevektorlager, som används av byggaren för att skapa grafen. För närvarande finns det, precis som i fallet med director, bara en byggare: QgsGraphBuilder, som skapar QgsGraph-objekt. Du kanske vill implementera dina egna byggare som bygger en graf som är kompatibel med sådana bibliotek som BGL eller 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.

Det är dags att dyka in i processen.

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. Det är då nödvändigt att skapa en strategi för att beräkna kantegenskaper

   # 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. Och berätta för chefen om denna strategi

   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. Grafisk analys

Nätverksanalys används för att hitta svar på två frågor: vilka toppar som är anslutna och hur man hittar den kortaste vägen. För att lösa dessa problem tillhandahåller biblioteket för nätverksanalys Dijkstras algoritm.

Dijkstras algoritm hittar den kortaste vägen från en av grafens hörnpunkter till alla de andra och värdena på optimeringsparametrarna. Resultaten kan representeras som ett träd med kortaste vägen.

Trädet med den kortaste vägen är en riktad viktad graf (eller mer exakt ett träd) med följande egenskaper:

• endast ett toppunkt har inga inkommande kanter - trädets rot

• alla andra toppar har bara en inkommande kant

• om toppunkt B kan nås från toppunkt A, så är vägen från A till B den enda tillgängliga vägen och den är optimal (kortast) i denna graf

För att få trädet med den kortaste vägen används metoderna shortestTree() och dijkstra() i klassen QgsGraphAnalyzer. Det rekommenderas att använda metoden dijkstra() eftersom den är snabbare och använder minnet mer effektivt.

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 — ingångsgraf

• startVertexIdx — index för punkten på trädet (trädets rot)

• criterionNum — antal edge-egenskaper som ska användas (börjar från 0).

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

Metoden dijkstra() har samma argument, men returnerar en tupel av arrayer:

• I den första arrayen innehåller element n index för den inkommande kanten eller -1 om det inte finns några inkommande kanter.

• I den andra arrayen innehåller elementet n avståndet från trädets rot till toppunkt n eller DOUBLE_MAX om toppunkt n inte kan nås från roten.

(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).

Varning

Använd denna kod endast som ett exempel, den skapar många QgsRubberBand-objekt och kan vara långsam på stora datamängder.

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. Hitta de kortaste vägarna

För att hitta den optimala vägen mellan två punkter används följande tillvägagångssätt. Båda punkterna (start A och slut B) är ”bundna” till grafen när den byggs. Sedan använder vi metoden shortestTree() eller dijkstra() för att bygga trädet med den kortaste vägen med roten i startpunkten A. I samma träd hittar vi också slutpunkten B och börjar gå genom trädet från punkt B till punkt A. Hela algoritmen kan skrivas som:

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

Vid denna punkt har vi vägen, i form av den inverterade listan över vertex (vertex listas i omvänd ordning från slutpunkt till startpunkt) som kommer att besökas under resan med denna väg.

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. Tillgängliga områden

Tillgänglighetsområdet för toppunkt A är den delmängd av grafens toppunkter som är tillgängliga från toppunkt A och där kostnaden för vägarna från A till dessa toppunkter inte är större än ett visst värde.

Detta kan tydliggöras med följande exempel: ”Det finns en brandstation. Vilka delar av staden kan en brandbil nå på 5 minuter? 10 minuter? 15 minuter?”. Svaren på dessa frågor är brandstationens tillgänglighetsområden.

För att hitta områden med tillgänglighet kan vi använda metoden dijkstra() i klassen QgsGraphAnalyzer. Det räcker att jämföra elementen i kostnadsarrayen med ett fördefinierat värde. Om cost[i] är mindre än eller lika med ett fördefinierat värde, ligger vertex i inom tillgänglighetsområdet, annars ligger det utanför.

Ett svårare problem är att få fram gränserna för tillgänglighetsområdet. Den nedre gränsen är den uppsättning vertex som fortfarande är tillgängliga, och den övre gränsen är den uppsättning vertex som inte är tillgängliga. I själva verket är detta enkelt: det är tillgänglighetsgränsen baserad på kanterna i trädet med den kortaste vägen för vilken källvertexen för kanten är tillgänglig och målvertexen för kanten inte är det.

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