Поиск кратчайшего маршрута c помощью Road graph для QGIS

Road graph — расширение QGIS, позволяющее осуществлять поиск кратчейшего маршрута на заданном графе дорог. Входит в состав QGIS, начиная с r15068 (0a76ab4212), автор модуля - Сергей Якушев (stopa85).

Установка

При использовании более-менее актуальной версии QGIS никаких дополнительных действий по установке модуля выполнять не нужно, так как Road graph является расширением ядра QGIS. Достаточно установить QGIS со всеми зависимостями (подробнее) и в Менеджере модулей (Модули - Управление модулями) активировать модуль Road graph.

После активации модуль добавляет свою панель в левой части окна QGIS и создает вложенный элемент в меню Вектор.

Работа с расширением

Основные возможности расширения:

• расчет маршрута, его протяженности и времени пути
• оптимизация по критерию расстояния или времени
• экспорт маршрута в векторный слой

В версиях QGIS 1.6, 1.7 присутствует возможность подсветки направления движения дорог (работает медленно, чаще всего используется в целях проверки настроек). Начиная с 1.8 неподдерживается.

В качестве слоя дорог можно использовать любой линейный векторный слой в формате, поддерживаемом QGIS. Две линии, имеющие общую точку считаются связанными между собой. Внимание: при редактировании слоя дорог в качестве СК проекта необходимо использовать СК слоя. Это вызвано тем, что при пересчете координат между разными СК возникают погрешности, что может приводить к появлению разрывов даже при включенном «прилипании».

В атрибутивной таблице слоя могут присутствовать и задействоваться следующие поля:

• скорость движения по участку дороги — числовое поле
• направление движения — любой тип, приводимый к строке. Прямое и обратное направления соответствуют односторонней дороге, оба направления — двусторонней.

Если значение какого-либо поля не задано, или поле отсутствует — используется значение по умолчанию, изменить которое можно в настройках расширения.

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

Нажатие на кнопку «Calculate» запустит поиск кратчайшего маршрута с использованием критерия оптимизации, заданного выпадающим списком «Criterion». Кнопка «Export» служит для экспорта построенного маршрута в новый векторный слой, а при помощи кнопки «Clear» выполняется очистка полей с координатами начальной и конечной точек, а также из области карты удаляются сами точки и построенный маршрут.

Настройки модуля

При использовании слоя дорог, в котором присутствуют артефакты в виде небольших разрывов между вершинами полилиний, необходимо установит «топологическую толерантность». Топологическая толерантность - это расстояние между двумя соседними вершинами, при котором они интерпретируются как одна и та же вершина графа. Эта величина должна быть как можно меньше (чем меньше - тем лучше).

Библиотека network-analysis

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

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

 from qgis.networkanalysis import *

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

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

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

Например

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

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

Следующим шагом необходимо создать стратегию назначения свойств ребрам графа. Стратегия рассчитывает свойства ребра, запрашивая данные у директора, и именно основываясь на свойствах ребер будет выполняться поиск оптимального маршрута. Пока в библиотеке реализована только одна стратегия, учитывающая длину маршрута: 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() ]

Для получения кратчайшего маршрута между двумя точками используется метод shortestpath</>.

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