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

Эта страница опубликована в основном списке статей сайта
по адресу http://gis-lab.info/qa/road-graph2.html

Статья содержит подробное описание расширения свободной к ГИС Quantum GIS модуля Road Graph.

Road graph — расширение свободной ГИС с открытым исходным кодом Quantum GIS, позволяющее осуществлять поиск оптимального маршрута на заданном графе дорог. Расширение автоматически устанавливается вместе с QGIS, начиная с версии 1.6, автор модуля — Сергей Якушев (stopa85).

Эта статья - расширенное описание модуля, старую, упрощенную версию описания можно найти здесь.

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

QGIS c активированным Road graph. Загружены слои OSM на Тюменскую область, красным цветом отображается проложенный маршрут.

Установка

Road graph является расширением ядра QGIS, поэтому достаточно установить QGIS со всеми зависимостями (подробнее) и в Менеджере модулей («Модули — Управление модулями») активировать модуль Road graph.

Активация Road graph в Менеджере модулей

После активации модуль добавляет свою панель в левой части окна QGIS и создает вложенный пункт в меню «Вектор» (новые экспериментальные версии QGIS) или пункт в меню «Модули» (Версии QGIS 1.6, 1.7). Панель может быть скрыта/показана с помощью пункта меню «Вид — Панели — Кратчайший маршрут».

Панель модуля Road graph

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

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

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

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

QGIS c подсветкой направления дорог, реализованной при помощи стилей

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

ВНИМАНИЕ: при редактировании слоя дорог в качестве СК проекта необходимо использовать СК слоя. Это вызвано тем, что при пересчете координат между разными СК возникают погрешности, что может приводить к появлению разрывов даже при включенном «прилипании».

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

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

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

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

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

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

Перед использованием рекомендуется выполнить настроку модуля. Для этого вызовите диалог настройки из меню «Вектор — Road graph — Параметры модуля Road graph».

Диалог настройки Road graph

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

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

Поиск пути с нулевой топологической толерантностью (в слой дорог введен искусственный артефакт)

Поиск пути с ненулевой (0.00005) топологической толерантностью (в слой дорог введен искусственный артефакт)

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

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

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

На вкладке «По умолчанию» задаются значения параметров по умолчанию, которые будут использоваться, если модуль не сможет извлечь информацию из указанных полей или если эти поля отсутствуют.

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

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