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

Материал из GIS-Lab
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
Строка 116: Строка 116:
В основе сетевого анализа лежат задача связности вершин графа и задача поиска кратчайших путей. Для решения этих задач в библиотеке network-analysis реализован [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B алгоритм Дейкстры].
В основе сетевого анализа лежат задача связности вершин графа и задача поиска кратчайших путей. Для решения этих задач в библиотеке network-analysis реализован [http://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B алгоритм Дейкстры].


Алгоритм Дейкстры находит оптимальный маршрут от одной из вершин графа до всех остальных и значение оптимизируемого параметра. Одним из способов представления результата выполнения алгоритма Дейкстры является [http://en.wikipedia.org/wiki/Shortest_path_tree дерево кратчайших путей].
Алгоритм Дейкстры находит оптимальный маршрут от одной из вершин графа до всех остальных и значение оптимизируемого параметра. Хорошим способов представления результата выполнения алгоритма Дейкстры является [http://en.wikipedia.org/wiki/Shortest_path_tree дерево кратчайших путей].


[[Файл:network-analysis-02.png|740px|thumb|center|<center>Дерево кратчайших путей с корнет в вершине №1</center>]]
[[Файл:network-analysis-02.png|740px|thumb|center|<center>Дерево кратчайших путей с корнем в вершине №1</center>]]


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


Дерево кратчайших путей можно получить пользуясь методам shortestTree или методом dijkstra класса [http://doc.qgis.org/api/classQgsGraphAnalyzer.html QgsGraphAnalyzer].
Дерево кратчайших путей можно получить пользуясь методом shortestTree или методом dijkstra класса [http://doc.qgis.org/api/classQgsGraphAnalyzer.html QgsGraphAnalyzer].
   
   
Метод <tt>shortestTree</tt> создает новый графовый объект (всегда QgsGraph) и принимает три аргумента:
Метод <tt>shortestTree</tt> создает новый графовый объект (всегда QgsGraph) и принимает три аргумента:
Строка 142: Строка 142:
</syntaxhighlight>
</syntaxhighlight>


Таким образом, после получения дерева кратчайших путей нам доступны два метода его анализа:
Вот так выглядит простейший способ отобразить дерево кратчайших путей для метода shortestTree (только замените координаты начальной точки на свои, а также выделите слой дорог в списке слоёв карты)
* Обход дерева в глубину (если хотите в ширину)
<syntaxhighlight lang="python">
* Движение от узла дерева к его корню
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 ] )


Анализ графа выполняет [http://doc.qgis.org/api/classQgsGraphAnalyzer.html QgsGraphAnalyzer]. Вот так можно получить дерево кратчайших путей с корнем в точке startPoint
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
 
</syntaxhighlight>
 
Так для метода dijkstra:


<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
tree = QgsGraphAnalyzer.shortestTree( graph, startId, 0 )
from PyQt4.QtCore import *
</syntaxhighlight>
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 )


Метод <tt>shortestTree</tt> принимает три аргумента:
( tree, costs ) = QgsGraphAnalyzer.dijkstra( graph, idStart, 0 )
* <tt>source</tt> — исходный граф
* <tt>startVertexIdx</tt> — индекс точки на графе (корень дерева)
* <tt>criterionNum</tt> — порядковый номер используемой стратегии (отсчет ведется от 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() )


<syntaxhighlight lang="python">
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() ]
</syntaxhighlight>
</syntaxhighlight>


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


Вот работающий пример для Консоли Python QGIS (только замените координаты начальной и конечной точки на свои, а также выделите слой дорог в списке слоёв карты)
Вот работающий пример для Консоли Python QGIS (только замените координаты начальной и конечной точки на свои, а также выделите слой дорог в списке слоёв карты)
<syntaxhighlight lang="python">
<syntaxhighlight lang="python">
from PyQt4.QtCore import *
from PyQt4.QtCore import *

Версия от 12:19, 19 января 2012

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

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

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

История

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

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

Применение

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

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

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

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

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

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

Граф полученный без дополнительных точек
Результирующий граф с двумя дополнительными точками. Красной точки соответствует вершина №5. Зеленой точки соответствует вновь добавленная вершина №9

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

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

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

Дерево кратчайших путей с корнем в вершине №1

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

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

Дерево кратчайших путей можно получить пользуясь методом shortestTree или методом dijkstra класса QgsGraphAnalyzer.

Метод shortestTree создает новый графовый объект (всегда QgsGraph) и принимает три аргумента:

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

Метод dijkstra имеет аналогичные параметры. Возвращаемое значение - кортеж из двух массивов. В первом массиве i-ый элемент содержит -1 если это корень дерева или вершина не достижима из корня, в противном случае - индекс дуги входящий в i-ю вершину. Во втором массиве i-ый элемент содержит дистанцию от корня дерева до i-вершины если вершина достижима из корня или максимально большое число которое может хранить тип С++ double (эквивалент плюс бесконечности) если вершина не достижима.

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

Вот так выглядит простейший способ отобразить дерево кратчайших путей для метода shortestTree (только замените координаты начальной точки на свои, а также выделите слой дорог в списке слоёв карты)

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(-0.743804,0.22954)
 
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() )

Нахождение кратчайших путей

Вот работающий пример для Консоли 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 )

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

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

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.