Поиск кратчайшего маршрута 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 )
Актуальная документацию всегда можно получить в разделе QGIS network analysis library описания QGIS API.