Библиотека сетевого анализа QGIS: описание и примеры

Внимание! Т.к. модуль активно развивается, статья может содержать устаревшую информацию.

QGIS network-analysis library — библиотека входящая в состав свободной ГИС Quantum GIS, которая:

• может создавать математический граф из географических данных (линейных векторных слоев), пригодный для анализа методами теории графов
• реализует базовые методы теории графов (в настоящее время только метод Дейкстры)

История

Библиотека QGIS network-analysis появилась путем экспорта базовых функций из плагина RoadGraph в отдельную библиотеку.

Начиная с ee19294562, появилась возможность использовать функционал библиотеки в своих расширениях, а также из Консоли Python QGIS.

Применение

Алгоритм применения библиотеки network-analysis можно записать в трех шагах:

1. Получить граф из географических данных
2. Анализировать граф
3. Использовать результат анализа графа в своих целях, например, визуализировать

Получение графа

Первое, что нужно сделать — это подготовить исходные данные, т.е. преобразовать векторный слой в граф. Все дальнейшие действия будут выполняться именно с ним.

В качестве источника графа может выступать любой линейный векторный слой. Узлы линий образуют множество вершин графа. В качестве ребер графа выступают отрезки линий векторного слоя. Узлы имеющие одинаковые координаты образуют единую вершину графа. Таким образом две линии имеющие общий узел оказываются связанными между собой.

В дополнение к этому при построении графа можно привязать к векторному слою любое количество дополнительных точек. Для каждой дополнительной точки будет найдено соответствие - либо ближайшая вершина графа, либо ближайшее ребро. В последнем случае ближайшее ребро будет разбито на две части и будет добавлена общая вершина.

Для того чтобы назначать ребрам графа характеристики (время движения по ребру, протяженность пути, стоимость) используется паттерн проектирования стратегия

Для построения графа из векторного слоя используется шаблон программирования строитель. За построение графа дорог отвечает так называемый Director. В настоящее время бибилотека располагает только одним директором: QgsLineVectorLayerDirector, которой строит граф по линейному векторному слою.

Рассмотрим создание графа более подробно.

Чтобы получить доступ к функциям библиотеки сетевого анализа необходимо импортировать модуль networkanalysis

from qgis.networkanalysis import *

Теперь нужно создать директора

# не использовать информацию о направлении движения из атрибутов слоя, все дороги трактуются как двустронние
director = QgsLineVectorLayerDirector( vLayer, -1, '', '', '', 3 )

# информация о направлении движения находится в поле с индексом 5. Односторонние дороги с прямым направлением
# движения имееют значение атрибута "yes", односторонние дороги с обратным направлением — "1", и соответственно
# двусторонние ­дороги — "no". По умолчанию дороги считаются двусторонними. Такая схема подходит для использования
# c данными OpenStreetMap
director = QgsLineVectorLayerDirector( vLayer, 5, 'yes', '1', 'no', 3 )

В конструктор директора передается линейный векторный слой, по которому будет строиться граф, а также информация о характере движения по каждому сегменту дороги (разрешенное направление, одностороннее или двустороннее движение). Рассмотрим эти параметры:

• vl — векторный слой, по которому будет строиться граф.
• directionFieldId — индекс поля атрибутивной таблицы, которое содержит информацию о направлении движения. -1 не использовать эту информацию
• directDirectionValue — значение поля, соответствующее прямому направлению движения (т.е. движению в порядке создания точек линии, от первой к последней)
• reverseDirectionValue — значение поля, соответствующее обратному направлению движения (от последней точки к первой)
• bothDirectionValue — значение поля, соответствующее двустроннему движению (т.е. допускается движение как от первой точки к последней, так и в обратном направлении)
• defaultDirection — направление движения по умолчанию. Будет использоваться для тех участков дорог, у которых значение поля directionFieldId не задано или не совпадает ни с одним из вышеперечисленных.

Следующим шагом необходимо создать стратегию назначения свойств ребрам графа. Стратегия рассчитывает свойства ребра, запрашивая данные у директора, и именно основываясь на свойствах ребер будет выполняться поиск оптимального маршрута. Пока в библиотеке реализована только одна стратегия, учитывающая длину маршрута: QgsDistanceArcProperter. При необходимости, можно создать свою стратегию, которая будет учитывать необходимые параметры. Например, в модуле Road graph используется стратегия, вычисляющая время движения по ребру графа на основании длины ребра и поля скорости.

properter = QgsDistanceArcProperter()

Сообщаем директору об используемой стратегии. Один директор может использовать несколько стратегий

director.addProperter( properter )

Теперь создаем строителя, который собственно и будет строить граф заданного типа. Стандартный строитель QgsGraphBuilder строит граф типа QgsGraph. При желании можно написать свою реализацию, которая будет строить граф, совместимый с такими библиотеками как Boost или networkX.

Конструктор строителя принимает следующие параметры:

• crs — используемая система координат. Обязательный параметр.
• otfEnabled — указывает на использование перепроецирования «на лету». По умолчанию true.
• topologyTolerance — топологическая толерантность. Значение по умолчанию 0.
• ellipsoidID — используемый эллипсоид. По умолчанию "WGS84".

# задана только используемая СК, все остальные параметры по умолчанию
builder = QgsGraphBuilder( myCRS )

Также можно задать одну или несколько точек, которые будет использоваться при анализе. Например так:

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

Затем строим граф и «привязываем» к нему точки

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

Построение графа может занять некоторое время (зависит от количества обектов в слое и размера самого слоя). После построения мы получим граф, пригодный для анализа

graph = builder.graph()

Теперь можно получить индексы наших точек

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

Анализ графа

Анализ графа выполняет QgsGraphAnalyzer. Вот так можно получить дерево кратчайших путей с корнем в точке startPoint

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

Метод shortestTree принимает три аргумента:

• source — исходный граф
• startVertexIdx — индекс точки на графе (корень дерева)
• criterionNum — порядковый номер используемой стратегии (отсчет ведется от 0).

На выходе мы получим граф, тип которого зависит от используемого строителя. Отобразить дерево на карте можно при помощи следующего кода

id = tree.findVertex( tiedPoint[ 0 ] )
not_begin = [ id ]
rb = QgsRubberBand( qgis.utils.iface.mapCanvas() )
rb.setWidth( 3 )

while len( not_begin ) > 0:
  curId = not_begin[ 0 ]
  not_begin = not_begin[ 1: ]
  rb.addPoint( tree.vertex( curId ).point() )
  f = 1
  for i in tree.vertex( curId ).outArc():
    if f == 1:
      not_begin = [ tree.arc( i ).inVertex() ] + not_begin
      f = 0
    else:
      not_begin = not_begin + [ tree.arc( i ).inVertex() ]

Для получения кратчайшего маршрута между двумя точками используется следующий подход. Обе точки (начальная A и конечная B) «привязываются» к графу на этапе построения, затем при помощи метода shortestTree получаем дерево кратчайших маршрутов с корнем в начальной точке A. В этом же дереве находим конечную точку B. Начинаем спуск по дереву от точки B к точке А. Для этого:

1. добавляем точку B в маршрут
2. берем ребро, которое входит в точку B
3. находим точку Т, из которой это ребро выходит
4. добавляем точку T в маршрут
5. проверям, входят ли какие-то ребра в вершину T. Если входящих ребер нет, то T = A и построение маршрута окончено. В противном случае повторям все действия с п. 2 но уже для точки T

Вот работающий пример для Консоли Python QGIS (только замените координаты начальной и конечной точки на свои, а также выделите слой дорог в списке слоёв карты)

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.4697, 56.989 )
pStop = QgsPoint( 65.4722, 57.2445 )

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

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

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

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

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)

Актуальная документация

Актуальную документацию всегда можно получить в разделе QGIS network analysis library описания QGIS API.