Поиск кратчайшего маршрута 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» выполняется очистка полей с координатами начальной и конечной точек, а также из области карты удаляются сами точки и построенный маршрут.

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

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

Модуль может правильно обрабатывать дороги с разным характером движения: одностроннее или двустороннее. Для этого необходимо, чтобы в атрибутивной таблице слоя присутствовало поле с указанием типа дороги. Его нужно выбрать в выпадающем списке «Поле направления» с настройках модуля и задать значения для прямого, обратного и двустроннего движения. Под прямым направлением понимается движение в порядке создания точек линии, от первой точки до последней. Соответственно, обратное направление это движение от последней точки линии к первой. Эти два варианта задают односторонние дороги.

Рассмотрим настройку на примере данных OpenStreetMap. В качестве поля направления выбираем "oneway", тогда двусторонней дороге будет соответствовать значение "no", прямому направлению односторонней дороги будет соответствовать значение "yes", a обратному — какое-либо другое значение, например "123". На вкладке «По умолчанию» для поля «Направление» выбираем «Двустороннее направление», чтобы дороги, не подпадающие под описанную выше схему трактовались как двусторонние. Все, теперь модуль будет различать дороги и строить маршруты с учетом характера движения по дорогам.

Библиотека 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.