네트워크 분석 라이브러리¶

일반 정보¶

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

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

2. 그래프 분석 실행

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

그래프 만들기¶

가장 먼저 해야 할 일은 입력 데이터를 준비하는 것인데, 벡터 레이어를 그래프(수학적으로 간략화된 연결관계)로 변환하는 것입니다. 이후의 모든 작업은 레이어가 아니라 이 그래프를 사용합니다.

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

또, 그래프 생성 중에 입력 벡터 레이어에 추가적인 포인트를 몇 개라도 “고정”(다른 용어로는 “결속”) 시킬 수 있습니다. 각 추가 포인트에 대응하는, 가장 가까운 그래프 버텍스 또는 가장 가까운 그래프 엣지를 찾을 것입니다. 후자의 경우 엣지가 나뉘어 새 버텍스가 추가됩니다.

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

Converting from a vector layer to the graph is done using the Builder programming pattern. A graph is constructed using a so-called Director. There is only one Director for now: QgsLineVectorLayerDirector. The director sets the basic settings that will be used to construct a graph from a line vector layer, used by the builder to create the graph. Currently, as in the case with the director, only one builder exists: QgsGraphBuilder, that creates QgsGraph objects. You may want to implement your own builders that will build a graphs compatible with such libraries as BGL or NetworkX.

To calculate edge properties the programming pattern strategy is used. For now only QgsDistanceArcProperter strategy is available, that takes into account the length of the route. You can implement your own strategy that will use all necessary parameters. For example, RoadGraph plugin uses a strategy that computes travel time using edge length and speed value from attributes.

이제 실제로 해 봅시다.

제일 먼저, 라이브러리를 이용하기 위해 networkanalysis 모듈을 임포트해야 합니다.

from qgis.networkanalysis import *

다음은 director를 생성하는 몇 가지 방법의 예시입니다.

# don't use information about road direction from layer attributes,
# all roads are treated as two-way
director = QgsLineVectorLayerDirector(vLayer, -1, '', '', '', 3)

# 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 = QgsLineVectorLayerDirector(vLayer, 5, 'yes', '1', 'no', 3)

director를 생성하려면 벡터 레이어를 넘겨줘야 하는데, 이 레이어는 그래프 구조 및 각 도로 엣지에서 허용되는 움직임(단방향 또는 양방향, 순방향 또는 역방향)에 대한 정보를 위한 자료로 쓰이게 됩니다. 다음과 같이 함수를 호출합니다.

director = QgsLineVectorLayerDirector(vl, directionFieldId,
                                      directDirectionValue,
                                      reverseDirectionValue,
                                      bothDirectionValue,
                                      defaultDirection)

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

• vl — 그래프 생성에 사용되는 벡터 레이어

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

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

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

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

• defaultDirection — 기본 도로 방향. directionFieldId 항목이 설정되지 않거나, 앞의 항목들에서 설정한 3가지 값이 아닐 경우에 이 값을 쓰게 됩니다. 정수형입니다. 1 은 순방향, 2 는 역방향, 3 은 양방향을 의미합니다.

그 다음 edge 속성을 계산하기 위해 strategy를 생성해야 합니다.

properter = QgsDistanceArcProperter()

그리고 drirector에게 이 strategy에 대해 알려줍니다.

director.addProperter(properter)

이제 그래프를 생성할 builder를 사용할 수 있습니다. QgsGraphBuilder 클래스 생성자는 다음 몇 가지 인자를 받습니다.

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

• otfEnabled — 실시간(on the fly) 재투영 사용 여부 결정. 기본값은 True.

• topologyTolerance — 위상오차 허용치. 기본값은 0.

• ellipsoidID — 사용할 타원체. 기본값은 WGS84.

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

또 분석 작업에 사용할 포인트를 몇 개 다음과 같이 정의합니다.

startPoint = QgsPoint(82.7112, 55.1672)
endPoint = QgsPoint(83.1879, 54.7079)

이제 모든 준비가 끝났으므로 그래프를 만들고 이 포인트들을 그래프에 “결속(tie)”시킬 수 있습니다.

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

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

graph = builder.graph()

다음 코드를 이용하면 포인트들의 vertex 인덱스들을 얻을 수 있습니다.

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

그래프 분석¶

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

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

최단 경로 트리는 다음과 같은 속성을 가진 방향성과 가중치가 적용된 그래프(더 정확히는 트리)입니다.

• 들어오는 edge가 없는 vertex는 단 하나, 트리의 루트뿐입니다.

• 다른 모든 vertex는 들어오는 edge를 딱 하나 가지고 있습니다.

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

To get the shortest path tree use the methods shortestTree() and dijkstra() of QgsGraphAnalyzer class. It is recommended to use method dijkstra() because it works faster and uses memory more efficiently.

사용자가 최단 경로 트리를 다각적으로 검토해보고 싶다면 shortestTree() 메소드가 유용합니다. 이 메소드는 항상 (QgsGraph 클래스의) 새 그래프 오브젝트를 생성하며, 다음 3개의 변수를 받습니다.

• source — 입력 그래프

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

• criterionNum — 사용할 경계선 속성의 개수 (0부터 시작)

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

dijkstra() 메소드의 경우 인자는 같지만 2개의 배열(array)을 반환합니다. 첫 번째 배열의 i 요소는 들어오는 엣지의 인덱스를 담고 있고, 만일 들어오는 엣지가 없을 경우 -1 값을 담게 됩니다. 두 번째 배열의 i 요소는 트리의 루트에서 버텍스 i까지의 거리를 담고 있고, 만일 루트에서 버텍스 i까지 도달할 수 없는 경우에는 DOUBLE_MAX 값을 담게 됩니다.

(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() method (select linestring layer in TOC and replace coordinates with your own). Warning: use this code only as an example, it creates a lots of QgsRubberBand objects and may be slow on large data-sets.

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.743804, 0.22954)
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.arcCount()):
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (tree.vertex(tree.arc(i).inVertex()).point())
  rb.addPoint (tree.vertex(tree.arc(i).outVertex()).point())
  i = i + 1

다음은 dijkstra() 메소드로 동일한 작업을 하는 코드입니다.

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-1.37144, 0.543836)
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(qgis.utils.iface.mapCanvas())
  rb.setColor (Qt.red)
  rb.addPoint (graph.vertex(graph.arc(edgeId).inVertex()).point())
  rb.addPoint (graph.vertex(graph.arc(edgeId).outVertex()).point())

assign Т = B
while Т != A
    add point Т to path
    get incoming edge for point Т
    look for point ТТ, that is start point of this edge
    assign Т = ТТ
add point А to path

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
tree = QgsGraphAnalyzer.shortestTree(graph, idStart, 0)

idStart = tree.findVertex(tStart)
idStop = tree.findVertex(tStop)

if idStop == -1:
  print "Path not found"
else:
  p = []
  while (idStart != idStop):
    l = tree.vertex(idStop).inArc()
    if len(l) == 0:
      break
    e = tree.arc(l[0])
    p.insert(0, tree.vertex(e.inVertex()).point())
    idStop = e.outVertex()

  p.insert(0, tStart)
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(-0.835953, 0.15679)
pStop = QgsPoint(-1.1027, 0.699986)

tiedPoints = director.makeGraph(builder, [pStart, pStop])
graph = builder.graph()

tStart = tiedPoints[0]
tStop = tiedPoints[1]

idStart = graph.findVertex(tStart)
idStop = graph.findVertex(tStop)

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

if tree[idStop] == -1:
  print "Path not found"
else:
  p = []
  curPos = idStop
  while curPos != idStart:
    p.append(graph.vertex(graph.arc(tree[curPos]).inVertex()).point())
    curPos = graph.arc(tree[curPos]).outVertex();

  p.append(tStart)

  rb = QgsRubberBand(qgis.utils.iface.mapCanvas())
  rb.setColor(Qt.red)

  for pnt in p:
    rb.addPoint(pnt)

from PyQt4.QtCore import *
from PyQt4.QtGui import *

from qgis.core import *
from qgis.gui import *
from qgis.networkanalysis import *

vl = qgis.utils.iface.mapCanvas().currentLayer()
director = QgsLineVectorLayerDirector(vl, -1, '', '', '', 3)
properter = QgsDistanceArcProperter()
director.addProperter(properter)
crs = qgis.utils.iface.mapCanvas().mapRenderer().destinationCrs()
builder = QgsGraphBuilder(crs)

pStart = QgsPoint(65.5462, 57.1509)
delta = qgis.utils.iface.mapCanvas().getCoordinateTransform().mapUnitsPerPixel() * 1

rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
rb.setColor(Qt.green)
rb.addPoint(QgsPoint(pStart.x() - delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() - delta))
rb.addPoint(QgsPoint(pStart.x() + delta, pStart.y() + delta))
rb.addPoint(QgsPoint(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 = 2000.0
i = 0
while i < len(cost):
  if cost[i] > r and tree[i] != -1:
    outVertexId = graph.arc(tree [i]).outVertex()
    if cost[outVertexId] < r:
      upperBound.append(i)
  i = i + 1

for i in upperBound:
  centerPoint = graph.vertex(i).point()
  rb = QgsRubberBand(qgis.utils.iface.mapCanvas(), True)
  rb.setColor(Qt.red)
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() - delta))
  rb.addPoint(QgsPoint(centerPoint.x() + delta, centerPoint.y() + delta))
  rb.addPoint(QgsPoint(centerPoint.x() - delta, centerPoint.y() + delta))