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

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

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

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

История

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

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

Применение

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

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

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

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

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

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

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

Реализация построения графа из векторного слоя использует шаблон программирования строитель. За построение графа дорог отвечает так называемый Director. В настоящее время бибилотека располагает только одним директором: QgsLineVectorLayerDirector. Директор определяет алгоритм которой строит граф по линейному векторному слою и одним строителем QgsGraphBuilder, его "руками" строиться граф типа QgsGraph. При желании можно реализовать строителя, который будет строить граф, совместимый с такими библиотеками как BGL или networkX.

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

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

Чтобы получить доступ к функциям библиотеки сетевого анализа необходимо импортировать модуль 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 не задано или не совпадает ни с одним из вышеперечисленных.

Следующим шагом необходимо создать стратегию назначения свойств ребрам графа

properter = QgsDistanceArcProperter()

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

director.addProperter( properter )

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

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

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

Анализ графа

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

Алгоритм Дейкстры находит оптимальный маршрут от одной из вершин графа до всех остальных и значение оптимизируемого параметра. Одним из способов представления результата выполнения алгоритма Дейкстры является дерево кратчайших путей.

Дерево кратчайших путей - это ориентированный взвешенный граф (точнее дерево) обладающий следующими свойствами:

• Только одна вершина не имеет входящих в нее ребер - корень дерева
• Все остальные вершины имеют только одно входящее в них ребро
• Если вершина B достижима из вершины A, то путь соединяющий их единственный и он же кратчайший (оптимальный) на исходном графе.

Таким образом, после получения дерева кратчайших путей нам доступны два метода его анализа:

• Обход дерева в глубину (если хотите в ширину)
• Нисходящий спуск.

Анализ графа выполняет 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.