중요

번역은 여러분이 참여할 수 있는 커뮤니티 활동입니다. 이 페이지는 현재 57.14% 번역되었습니다.

19. 네트워크 분석 라이브러리

힌트

PyQGIS 콘솔을 사용하지 않는 경우 이 페이지에 있는 코드 조각들을 다음과 같이 가져와야 합니다:

from qgis.core import (
  QgsVectorLayer,
  QgsPointXY,
)

네트워크 분석 라이브러리는 다음에 사용할 수 있습니다:

  • 지리 데이터(폴리라인 벡터 레이어)로부터 수학적인 그래프를 생성할 수 있습니다.

  • 그래프 이론으로부터 기본 메소드들을 (현재로서는 데이크스트라(Dijkstra) 알고리즘만) 구현할 수 있습니다.

이 라이브러리의 전형적인 용도를 간단히 설명하면 다음과 같습니다:

  1. 지리 데이터(일반적으로 폴리라인 벡터 레이어)로부터 그래프 생성

  2. 그래프 분석 실행

  3. 분석 결과 이용 (예를 들어 분석 결과의 시각화 등)

19.1. 그래프 작성하기

가장 먼저 해야 할 일은 입력 데이터를 준비하는, 다시 말해 벡터 레이어를 그래프로 변환하는 것입니다. 이후의 모든 작업은 레이어가 아니라 이 그래프를 사용할 것입니다.

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.

또, 그래프를 생성하는 도중에 입력 벡터 레이어에 추가적인 포인트를 몇 개라도 “고정(fix)”(다른 용어로는 “결속(tie)”)시킬 수 있습니다. 각 추가 포인트에 대응하는, 가장 가까운 그래프 꼭짓점 또는 가장 가까운 그래프 변을 찾을 것입니다. 후자의 경우 변을 분할해서 새 꼭짓점을 추가합니다.

벡터 레이어의 속성과 변 길이를 그래프 변의 속성으로 쓸 수 있습니다.

빌더 프로그래밍 패턴을 사용해서 벡터 레이어를 그래프로 변환합니다. 소위 말하는 디렉터(Director)를 사용해서 그래프를 작성합니다. 현재 디렉터는 QgsVectorLayerDirector 클래스 하나뿐입니다. 디렉터는 라인 벡터 레이어로부터 그래프를 작성하는 데 쓰일 기본 설정을 설정하는데, 빌더가 이를 사용해서 그래프를 생성합니다. 현재 존재하는 빌더는 디렉터의 경우와 마찬가지로 QgsGraph 클래스 객체를 생성하는 QgsGraphBuilder 클래스 하나뿐입니다. 여러분은 BGL 또는 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.

이제 실제로 해봅시다.

  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:

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

    1# Use field with index 5 as source of information about road direction.
2# one-way roads with direct direction have attribute value "yes",
3# one-way roads with reverse direction have the value "1", and accordingly
4# bidirectional roads have "no". By default roads are treated as two-way.
5# This scheme can be used with OpenStreetMap data
6director = QgsVectorLayerDirector(
7    vectorLayer, 5, "yes", "1", "no", QgsVectorLayerDirector.DirectionBoth
8)

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

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

  3. 그 다음 변의 속성을 계산하기 위한 전략을 생성해야 합니다:

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

  4. 그리고 디렉터에 이 전략을 알려줍니다:

    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. 그래프 분석

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.

최단 경로 트리는 다음 속성들을 가진 방향성 가중치 그래프(더 정확하게는 트리)입니다:

  • 들어오는 변이 없는 꼭짓점은 단 하나, 트리의 루트(root)뿐입니다.

  • all other vertices have only one incoming edge

  • 꼭짓점 A에서 꼭짓점 B에 도달할 수 있다면, A에서 B로의 경로는 사용할 수 있는 단 하나의 경로이며 이 그래프 상에서 최적(최단) 경로입니다.

최단 경로 트리를 생성하려면 QgsGraphAnalyzer 클래스의 shortestTree() 와 dijkstra() 메소드를 사용하십시오. dijkstra() 메소드를 사용할 것을 권장합니다. 더 빠르고 메모리를 더 효율적으로 사용하기 때문입니다.

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 — 입력 그래프

  • startVertexIdx — 트리 상에 있는 포인트의 인덱스 (트리의 루트)

  • criterionNum — 사용할 변 속성의 번호 (0에서 시작)

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

The dijkstra() method has the same arguments, but returns a tuple of arrays:

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

경고

이 코드를 예제로써만 사용하십시오. 이 코드는 QgsRubberBand 클래스 객체를 많이 생성하기 때문에 대용량 데이터셋의 경우 느려질 수도 있습니다.

 1from qgis.core import *
 2from qgis.gui import *
 3from qgis.analysis import *
 4from qgis.PyQt.QtCore import *
 5from qgis.PyQt.QtGui import *
 6
 7vectorLayer = QgsVectorLayer(
 8    "testdata/network.gpkg|layername=network_lines", "lines"
 9)
10director = QgsVectorLayerDirector(
11    vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
12)
13strategy = QgsNetworkDistanceStrategy()
14director.addStrategy(strategy)
15builder = QgsGraphBuilder(vectorLayer.crs())
16
17pStart = QgsPointXY(1179661.925139, 5419188.074362)
18tiedPoint = director.makeGraph(builder, [pStart])
19pStart = tiedPoint[0]
20
21graph = builder.graph()
22
23idStart = graph.findVertex(pStart)
24
25tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)
26
27i = 0
28while i < tree.edgeCount():
29    rb = QgsRubberBand(iface.mapCanvas())
30    rb.setColor(Qt.red)
31    rb.addPoint(tree.vertex(tree.edge(i).fromVertex()).point())
32    rb.addPoint(tree.vertex(tree.edge(i).toVertex()).point())
33    i = i + 1

19.2.1. 최단 경로 찾기

두 포인트 사이의 최적 경로를 찾기 위해 다음 접근법을 사용합니다. 두 포인트 (시작 포인트 A와 종단 포인트 B) 모두 작성 시 그래프에 “결속”됩니다. 그 다음 shortestTree() 또는 dijkstra() 메소드를 사용해서 트리의 루트가 시작 포인트 A인 최단 경로 트리를 생성합니다. 이 트리에서 종단 포인트 B를 찾아, 트리 안에서 B에서 A로 가는 경로를 탐색합니다. 이 전체 알고리즘을 다음처럼 작성할 수 있습니다:

1assign T = B
2while T != B
3    add point T to path
4    get incoming edge for point T
5    look for point TT, that is start point of this edge
6    assign T = TT
7add 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:

 1from qgis.core import *
 2from qgis.gui import *
 3from qgis.analysis import *
 4
 5from qgis.PyQt.QtCore import *
 6from qgis.PyQt.QtGui import *
 7
 8vectorLayer = QgsVectorLayer(
 9    "testdata/network.gpkg|layername=network_lines", "lines"
10)
11director = QgsVectorLayerDirector(
12    vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
13)
14strategy = QgsNetworkDistanceStrategy()
15director.addStrategy(strategy)
16
17builder = QgsGraphBuilder(vectorLayer.sourceCrs())
18
19startPoint = QgsPointXY(1179661.925139, 5419188.074362)
20endPoint = QgsPointXY(1180942.970617, 5420040.097560)
21
22tiedPoints = director.makeGraph(builder, [startPoint, endPoint])
23tStart, tStop = tiedPoints
24
25graph = builder.graph()
26idxStart = graph.findVertex(tStart)
27
28tree = QgsGraphAnalyzer.shortestTree(graph, idxStart, 0)
29
30idxStart = tree.findVertex(tStart)
31idxEnd = tree.findVertex(tStop)
32
33if idxEnd == -1:
34    raise Exception("No route!")
35
36# Add last point
37route = [tree.vertex(idxEnd).point()]
38
39# Iterate the graph
40while idxEnd != idxStart:
41    edgeIds = tree.vertex(idxEnd).incomingEdges()
42    if len(edgeIds) == 0:
43        break
44    edge = tree.edge(edgeIds[0])
45    route.insert(0, tree.vertex(edge.fromVertex()).point())
46    idxEnd = edge.fromVertex()
47
48# Display
49rb = QgsRubberBand(iface.mapCanvas())
50rb.setColor(Qt.green)
51
52# This may require coordinate transformation if project's CRS
53# is different from layer's CRS
54for p in route:
55    rb.addPoint(p)

19.2.2. 도달 가능 영역

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.

다음 질문을 통해 이를 더 명확히 알 수 있습니다. “소방서가 있다. 소방차가 5분/10분/15분 안에 도착할 수 있는 도시의 구역은 어디인가?” 이 질문에 대한 답이 바로 소방서의 도달 가능 영역입니다.

도달 가능 영역을 찾으려면 QgsGraphAnalyzer 클래스의 dijkstra() 메소드를 사용하면 됩니다. 비용 배열의 요소들을 사전 정의된 값과 비교하는 것으로 충분합니다. cost[i]가 사전 정의 값 이하인 경우, 꼭짓점 i는 도달 가능 영역 안에 있는 것이고, 초과하는 경우 밖에 있는 것입니다.

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:

 1director = QgsVectorLayerDirector(
 2  vectorLayer, -1, "", "", "", QgsVectorLayerDirector.DirectionBoth
 3)
 4strategy = QgsNetworkDistanceStrategy()
 5director.addStrategy(strategy)
 6builder = QgsGraphBuilder(vectorLayer.crs())
 7
 8
 9pStart = QgsPointXY(1179661.925139, 5419188.074362)
10delta = iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1
11
12rb = QgsRubberBand(iface.mapCanvas())
13rb.setColor(Qt.green)
14rb.addPoint(QgsPointXY(pStart.x() - delta, pStart.y() - delta))
15rb.addPoint(QgsPointXY(pStart.x() + delta, pStart.y() - delta))
16rb.addPoint(QgsPointXY(pStart.x() + delta, pStart.y() + delta))
17rb.addPoint(QgsPointXY(pStart.x() - delta, pStart.y() + delta))
18
19tiedPoints = director.makeGraph(builder, [pStart])
20graph = builder.graph()
21tStart = tiedPoints[0]
22
23idStart = graph.findVertex(tStart)
24
25(tree, cost) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)
26
27upperBound = []
28r = 1500.0
29i = 0
30tree.reverse()
31
32while i < len(cost):
33    if cost[i] > r and tree[i] != -1:
34        outVertexId = graph.edge(tree [i]).toVertex()
35        if cost[outVertexId] < r:
36            upperBound.append(i)
37    i = i + 1
38
39for i in upperBound:
40    centerPoint = graph.vertex(i).point()
41    rb = QgsRubberBand(iface.mapCanvas())
42    rb.setColor(Qt.red)
43    rb.addPoint(QgsPointXY(centerPoint.x() - delta, centerPoint.y() - delta))
44    rb.addPoint(QgsPointXY(centerPoint.x() + delta, centerPoint.y() - delta))
45    rb.addPoint(QgsPointXY(centerPoint.x() + delta, centerPoint.y() + delta))
46    rb.addPoint(QgsPointXY(centerPoint.x() - delta, centerPoint.y() + delta))