Viktigt

Översättning är en gemenskapsinsats du kan gå med i. Den här sidan är för närvarande översatt till 100.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)

Biblioteket för nätverksanalys skapades genom att exportera grundläggande funktioner från RoadGraphs kärnplugin och nu kan du använda dess metoder i plugins eller direkt från Python-konsolen.

19.1. Allmän information 

Kortfattat kan ett typiskt användningsfall beskrivas som:

skapa graf från geodata (vanligtvis polylinjevektorlager)
analys av körgrafer
använda analysresultat (t.ex. visualisera dem)

19.2. 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 skiktet.

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.

För att beräkna kantegenskaper används programmeringsmönstret strategy. För närvarande finns endast QgsNetworkDistanceStrategy strategi (som tar hänsyn till ruttens längd) och QgsNetworkSpeedStrategy (som även tar hänsyn till hastigheten) tillgängliga. Du kan implementera din egen strategi som kommer att använda alla nödvändiga parametrar. Plugin-programmet RoadGraph använder t.ex. en strategi som beräknar restiden med hjälp av kantlängd och hastighetsvärde från attribut.

Det är dags att dyka in i processen.

För att kunna använda det här biblioteket måste vi först importera analysmodulen

from qgis.analysis import *

Sedan några exempel på hur man skapar en direktör

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

För att konstruera en director måste vi skicka ett vektorlager som kommer att användas som källa för grafstrukturen och information om tillåten rörelse på varje vägsegment (enkelriktad eller dubbelriktad rörelse, direkt eller omvänd riktning). Samtalet ser ut så här

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

Och här är en fullständig lista över vad dessa parametrar betyder:

vectorLayer — vektorlager som används för att bygga grafen
directionFieldId — index för attributtabellens fält, där information om vägars riktning lagras. Om -1, använd inte denna information alls. Ett heltal.
directDirectionValue — fältvärde för vägar med direkt riktning (förflyttning från första linjepunkten till den sista). En sträng.
reverseDirectionValue — fältvärde för vägar med omvänd riktning (förflyttning från sista linjepunkten till den första). En sträng.
bothDirectionValue — fältvärde för dubbelriktade vägar (för sådana vägar kan vi flytta från första punkten till sista och från sista till första). En sträng.
defaultDirection — standard vägriktning. Detta värde kommer att användas för de vägar där fältet directionFieldId inte är inställt eller har ett annat värde än något av de tre värden som anges ovan. Möjliga värden är:
- QgsVectorLayerDirector.DirectionForward — Enkelriktad direkt
- QgsVectorLayerDirector.DirectionBackward — Enkelriktad backning
- QgsVectorLayerDirector.DirectionBoth — Tvåvägs

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)

Och berätta för chefen om denna strategi

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

Nu kan vi använda byggaren, som kommer att skapa grafen. Klassens QgsGraphBuilder konstruktor tar flera argument:

crs — koordinatreferenssystem att använda. Obligatoriskt argument.
otfEnabled — använd ”on the fly” reprojection eller inte. Som standard True (använd OTF).
topologyTolerance — topologisk tolerans. Standardvärdet är 0.
ellipsoidID — ellipsoid att använda. Som standard ”WGS84”.

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

Vi kan också definiera flera punkter som kommer att användas i analysen. Till exempel

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

Nu är allt på plats så att vi kan bygga grafen och ”knyta” dessa punkter till den

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

Att bygga grafen kan ta lite tid (vilket beror på antalet funktioner i ett lager och lagrets storlek). tiedPoints är en lista med koordinater för ”bundna” punkter. När byggprocessen är klar kan vi hämta grafen och använda den för analysen

graph = builder.graph()

Med följande kod kan vi få fram toppunktsindexen för våra punkter

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

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

Metoden shortestTree() är användbar när du vill gå runt i trädet med den kortaste vägen. Den skapar alltid ett nytt grafobjekt (QgsGraph) och accepterar tre variabler:

källa — 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 matriser:

I den första matrisen innehåller element n index för den inkommande kanten eller -1 om det inte finns några inkommande kanter.
I den andra matrisen 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)

Här är en mycket enkel kod för att visa trädet med den kortaste vägen med hjälp av grafen som skapats med metoden shortestTree() (välj linjestringskiktet i panelen Layers och ersätt koordinaterna med dina egna).

Varning

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

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

Samma sak men med metoden 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, 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())

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

Här är exempelkoden för QGIS Python Console (du kan behöva ladda och välja ett linjestringslager i TOC och ersätta koordinaterna i koden med dina) som använder metoden shortestTree()

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)
strategy = QgsNetworkDistanceStrategy()
director.addStrategy(strategy)

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)

Och här är samma exempel men med metoden 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)
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)

19.3.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 kostnadsmatrisen 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.

Här följer ett exempel

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

19. Bibliotek för nätverksanalys

19.1. Allmän information

19.2. Bygga upp en graf

19.3. Grafisk analys

19.3.1. Hitta de kortaste vägarna

19.3.2. Tillgängliga områden

19.1. Allmän information 

19.2. Bygga upp en graf 

19.3. Grafisk analys 

19.3.1. Hitta de kortaste vägarna 

19.3.2. Tillgängliga områden 