중요

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

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

힌트

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

from qgis.core import (
  QgsVectorLayer,
  QgsPointXY,
)

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

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

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

RoadGraph 핵심 플러그인에서 기본 함수들을 내보내서 네트워크 분석 알고리즘을 생성했습니다. 이제 플러그인에서 또는 파이썬 콘솔에서 직접 이 라이브러리의 메소드들을 사용할 수 있습니다.

19.1. 일반 정보

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

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

  2. 그래프 분석 실행

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

19.2. 그래프 작성하기

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

어떤 폴리라인 벡터 레이어라도 소스로 사용할 수 있습니다. 폴리라인의 노드(node)는 그래프의 꼭짓점(vertex)이 되고, 폴리라인의 선분(segment)은 그래프의 변(edge)이 됩니다. 노드 몇 개가 동일한 좌표에 있을 경우 그 노드들은 동일한 그래프 꼭짓점이 됩니다. 따라서 공통 노드를 가진 2개의 선분은 서로 연결됩니다.

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

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

빌더 프로그래밍 패턴을 사용해서 벡터 레이어를 그래프로 변환합니다. 소위 말하는 디렉터(Director)를 사용해서 그래프를 작성합니다. 현재 디렉터는 QgsVectorLayerDirector 클래스 하나뿐입니다. 디렉터는 라인 벡터 레이어로부터 그래프를 작성하는 데 쓰일 기본 설정을 설정하는데, 빌더가 이를 사용해서 그래프를 생성합니다. 현재 존재하는 빌더는 디렉터의 경우와 마찬가지로 QgsGraph 클래스 객체를 생성하는 QgsGraphBuilder 클래스 하나뿐입니다. 여러분은 BGL 또는 NetworkX 같은 라이브러리와 호환되는 그래프를 작성하는 사용자 정의 빌더를 구현하기를 원할 수도 있습니다.

변(edge) 속성을 계산하기 위해서는 전략(strategy) 프로그래밍 패턴을 사용합니다. 현재로서는 (경로(route)의 길이를 연산에 넣는) QgsNetworkDistanceStrategy 전략과 (속도도 연산에 넣는) QgsNetworkSpeedStrategy 전략만 사용할 수 있습니다. 필요한 모든 파라미터를 사용하는 사용자 정의 전략을 구현할 수도 있습니다. 예를 들어 RoadGraph 플러그인은 속성으로부터 변 길이와 속도 값을 사용해서 이동 시간을 계산하는 전략을 사용합니다.

이제 실제로 해봅시다.

가장 먼저, 이 라이브러리를 사용하려면 분석 모듈을 가져와야 합니다:

from qgis.analysis import *

다음은 디렉터를 생성하는 몇 가지 방법의 예시입니다:

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

디렉터를 작성하려면, 그래프 구조 및 각 도로 선분 상에서 허용되는 (일방통행인지 양방향인지, 순방향인지 역방향인지) 움직임에 대한 정보의 소스로 사용할 벡터 레이어를 전달해야 합니다. 이 호출은 다음처럼 보일 것입니다:

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

각 파라미터가 의미하는 바는 다음과 같습니다:

  • vectorLayer — 그래프를 작성하기 위해 사용하는 벡터 레이어

  • directionFieldId — 도로 방향에 관한 정보가 저장된 속성 테이블 필드의 인덱스. 값이 -1 일 경우 방향 정보를 전혀 사용하지 않습니다. 정수형입니다.

  • directDirectionValue — 순방향 (라인의 첫 번째 포인트에서 마지막 포인트로 이동하는) 도로의 필드 값. 문자열입니다.

  • reverseDirectionValue — 역방향 (라인의 마지막 포인트에서 첫 번째 포인트로 이동하는) 도로의 필드 값. 문자열입니다.

  • bothDirectionValue — 양방향 (첫 번째 포인트에서 마지막으로도 마지막에서 첫 번째로도 이동할 수 있는) 도로의 필드 값. 문자열입니다.

  • defaultDirection — 기본 도로 방향. directionFieldId 필드가 설정되지 않은 도로 또는 앞에서 설명한 값 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)

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

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

이제 그래프를 생성할 빌더를 사용할 수 있습니다. QgsGraphBuilder 클래스 작성자(constructor)는 인자 몇 개를 받습니다:

  • crs — 사용할 좌표계. 필수 인자입니다.

  • otfEnabled — “실시간(on-the-fly)” 재투영을 사용할지 여부. 기본값은 True (OTF 사용)입니다.

  • topologyTolerance — 위상 허용 오차. 기본값은 0입니다.

  • ellipsoidID — 사용할 타원체. 기본값은 “WGS84”입니다.

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

또 분석 작업에 사용할 포인트 몇 개를 다음과 같이 정의할 수 있습니다:

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

이제 모든 준비가 끝났기 때문에, 그래프를 작성하고 이 포인트들을 그래프에 “결속(tie)”시킬 수 있습니다:

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

그래프를 만드는 데 시간이 좀 걸릴 수도 있습니다. (레이어에 있는 피처의 개수 및 레이어 크기에 따라 다릅니다.) tiedPoints 는 “결속”된 포인트들의 좌표 목록입니다. 빌더의 작업이 완료되면 분석에 사용할 수 있는 그래프를 얻게 됩니다:

graph = builder.graph()

다음 코드를 사용하면 포인트들의 꼭짓점 인덱스들을 얻을 수 있습니다:

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

19.3. 그래프 분석

네트워크 분석은 다음 두 가지 질문에 대한 답을 찾는 데 사용됩니다. 어떤 꼭짓점들이 연결되어 있는가? 그리고 어떻게 최단 경로를 찾을 것인가? 네트워크 분석 라이브러리는 이 문제를 해결하기 위해 데이크스트라 알고리즘(Dijkstra’s algorithm)을 제공합니다.

데이크스트라 알고리즘은 그래프의 한 꼭짓점에서 다른 모든 꼭짓점으로 가는 최단 경로와 최적화 파라미터의 값을 찾습니다. 그 결과는 최단 경로 트리로 나타낼 수 있습니다.

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

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

  • 다른 모든 꼭짓점은 들어오는 변을 딱 하나 가지고 있습니다.

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

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

여러분이 최단 경로 트리를 탐색하고 싶은 경우 shortestTree() 메소드가 유용합니다. 이 메소드는 언제나 새 그래프 객체(QgsGraph 클래스)를 생성하며 다음 변수 3개를 받습니다:

  • source — 입력 그래프

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

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

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

dijkstra() 메소드도 동일한 인자를 받지만, 2개의 배열을 반환합니다. 첫 번째 배열 요소 n 은 들어오는 변의 인덱스를 또는 들어오는 변이 없는 경우 -1을 담습니다. 두 번째 배열 요소 n 은 트리의 루트에서 n 꼭짓점까지의 거리를 또는 루트에서 n 꼭짓점에 도달할 수 없는 경우 DOUBLE_MAX를 담습니다.

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

다음은 shortestTree() 메소드로 생성한 그래프를 사용해서 최단 경로 트리를 표시하는 매우 단순한 코드입니다. (Layers 패널에서 라인스트링 레이어를 선택한 다음 좌표를 여러분 자신의 좌표로 대체하십시오.)

경고

이 코드를 예제로써만 사용하십시오. 이 코드는 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('testdata/network.gpkg|layername=network_lines', 'lines')
 8director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth)
 9strategy = QgsNetworkDistanceStrategy()
10director.addStrategy(strategy)
11builder = QgsGraphBuilder(vectorLayer.crs())
12
13pStart = QgsPointXY(1179661.925139,5419188.074362)
14tiedPoint = director.makeGraph(builder, [pStart])
15pStart = tiedPoint[0]
16
17graph = builder.graph()
18
19idStart = graph.findVertex(pStart)
20
21tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)
22
23i = 0
24while (i < tree.edgeCount()):
25  rb = QgsRubberBand(iface.mapCanvas())
26  rb.setColor (Qt.red)
27  rb.addPoint (tree.vertex(tree.edge(i).fromVertex()).point())
28  rb.addPoint (tree.vertex(tree.edge(i).toVertex()).point())
29  i = i + 1

동일한 목적이지만 dijkstra() 메소드를 사용하는 코드입니다:

 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('testdata/network.gpkg|layername=network_lines', 'lines')
 8
 9director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth)
10strategy = QgsNetworkDistanceStrategy()
11director.addStrategy(strategy)
12builder = QgsGraphBuilder(vectorLayer.crs())
13
14pStart = QgsPointXY(1179661.925139,5419188.074362)
15tiedPoint = director.makeGraph(builder, [pStart])
16pStart = tiedPoint[0]
17
18graph = builder.graph()
19
20idStart = graph.findVertex(pStart)
21
22(tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idStart, 0)
23
24for edgeId in tree:
25  if edgeId == -1:
26    continue
27  rb = QgsRubberBand(iface.mapCanvas())
28  rb.setColor (Qt.red)
29  rb.addPoint (graph.vertex(graph.edge(edgeId).fromVertex()).point())
30  rb.addPoint (graph.vertex(graph.edge(edgeId).toVertex()).point())

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

이 시점에서 이 경로를 지나가는 동안 거치게 될 꼭짓점들의 역순 목록의 형태로 경로를 얻게 됩니다. (꼭짓점들이 종단 포인트에서 시작 포인트 순서로 역순으로 나열됩니다.)

다음은 shortestTree() 메소드를 사용하는 QGIS 파이썬 콘솔의 예시 코드입니다 (TOC(Table of Contents)에 라인스트링 레이어를 불러와 선택한 다음 코드에 있는 좌표를 여러분의 좌표로 대체해야 할 수도 있습니다):

 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('testdata/network.gpkg|layername=network_lines', 'lines')
 9builder = QgsGraphBuilder(vectorLayer.sourceCrs())
10director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth)
11
12startPoint = QgsPointXY(1179661.925139,5419188.074362)
13endPoint = QgsPointXY(1180942.970617,5420040.097560)
14
15tiedPoints = director.makeGraph(builder, [startPoint, endPoint])
16tStart, tStop = tiedPoints
17
18graph = builder.graph()
19idxStart = graph.findVertex(tStart)
20
21tree = QgsGraphAnalyzer.shortestTree(graph, idxStart, 0)
22
23idxStart = tree.findVertex(tStart)
24idxEnd = tree.findVertex(tStop)
25
26if idxEnd == -1:
27    raise Exception('No route!')
28
29# Add last point
30route = [tree.vertex(idxEnd).point()]
31
32# Iterate the graph
33while idxEnd != idxStart:
34    edgeIds = tree.vertex(idxEnd).incomingEdges()
35    if len(edgeIds) == 0:
36        break
37    edge = tree.edge(edgeIds[0])
38    route.insert(0, tree.vertex(edge.fromVertex()).point())
39    idxEnd = edge.fromVertex()
40
41# Display
42rb = QgsRubberBand(iface.mapCanvas())
43rb.setColor(Qt.green)
44
45# This may require coordinate transformation if project's CRS
46# is different than layer's CRS
47for p in route:
48    rb.addPoint(p)

다음은 동일한 예시이지만 dijkstra() 메소드를 사용하는 코드입니다:

 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('testdata/network.gpkg|layername=network_lines', 'lines')
 9director = QgsVectorLayerDirector(vectorLayer, -1, '', '', '', QgsVectorLayerDirector.DirectionBoth)
10strategy = QgsNetworkDistanceStrategy()
11director.addStrategy(strategy)
12
13builder = QgsGraphBuilder(vectorLayer.sourceCrs())
14
15startPoint = QgsPointXY(1179661.925139,5419188.074362)
16endPoint = QgsPointXY(1180942.970617,5420040.097560)
17
18tiedPoints = director.makeGraph(builder, [startPoint, endPoint])
19tStart, tStop = tiedPoints
20
21graph = builder.graph()
22idxStart = graph.findVertex(tStart)
23idxEnd = graph.findVertex(tStop)
24
25(tree, costs) = QgsGraphAnalyzer.dijkstra(graph, idxStart, 0)
26
27if tree[idxEnd] == -1:
28    raise Exception('No route!')
29
30# Total cost
31cost = costs[idxEnd]
32
33# Add last point
34route = [graph.vertex(idxEnd).point()]
35
36# Iterate the graph
37while idxEnd != idxStart:
38    idxEnd = graph.edge(tree[idxEnd]).fromVertex()
39    route.insert(0, graph.vertex(idxEnd).point())
40
41# Display
42rb = QgsRubberBand(iface.mapCanvas())
43rb.setColor(Qt.red)
44
45# This may require coordinate transformation if project's CRS
46# is different than layer's CRS
47for p in route:
48    rb.addPoint(p)

19.3.2. 도달 가능 영역

꼭짓점 A의 도달 가능 영역(area of availability)이란 꼭짓점 A에서 접근할 수 있고, 꼭짓점 A에서 이 꼭짓점들까지의 경로 비용이 지정된 값을 초과하지 않는, 그래프 꼭짓점들의 부분집합을 말합니다.

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

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

도달 가능 영역의 경계를 구하는 일은 좀 더 어려운 문제입니다. 하단 경계는 도달 가능한 꼭짓점들의 집합이고, 상단 경계는 도달 불가능한 꼭짓점들의 집합입니다. 사실 단순합니다 — 변의 소스 꼭짓점에 접근할 수 있고 변의 대상 꼭짓점에는 접근할 수 없는 최단 경로 트리의 변들을 바탕으로 한 도달 가능 경계입니다.

다음은 그 예시입니다:

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