Поиск кратчайшего расстояния на графе дорог. Протестируйте

[stopa85]

Патч в трак будет завтра, ближе к полуночи.

[stopa85]

3416 посмотрим, что скажут.

Voltron, прости, добавил без локализации. В нашем svn она есть. За окошко about спасибо.

Приоритетными направлениям работы над плагином являются:
1. Интергация с bgl с целью поддержки большего количества алгоритмов на графе. Саму библиотеку я не знаю, так что ждите.

2. Построение графа по полигональным слоям: это, в месте с первым, даст огромные возможности QGis'у в части сетевого анализа. Однако тут нужен развитый "fTools" в ядре к qgis (не дублировать же функционал). Так что придеться поработать и над этим.

[Voltron]

C r15068 модуль RoadGraph стал частью QGIS.
stopa85, спасибо и успехов в дальнейшем совершенствовании модуля!

[stopa85]

Начиная с r15239 в плагине появилась возможность установить "топологическую толерантность".

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

Ну а просьба все таже протестировать.

[Voltron]

Небольшой скринкаст от Тима, демонстрирующий модуль в действии.

[bim2010]

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

загрузить файл расширения и скопировать его в каталог расширений QGIS

хорошо бы добавить путь, например: C:\Program Files\Quantum GIS Copiapo\apps\qgis\plugins

[Pifagoroff]

Здравствуйте. Возможно, я делаю, что-то не так. Загружаю проект для Москвы в qgis, полученный вот отсюда: http://gis-lab.info/projects/osm_shp/region . Пытаюсь построить с помощью модуля маршрут. У меня получился маршрут через Битцевский парк, по велодорожкам. Сколько, примерно, по времени должен работать модуль, что бы построить маршрут по Москве, по автомобильным дорогам и как это сделать? У меня модуль работал никак не меньше 10 минут. Можно ли узнать, какие алгоритмы поиска используются в модуле. Спасибо.

[Voltron]

Видимо, маршрут по дорожкам наиболее короткий . Если не ошибаюсь, используется алгоритм Дейкстры.

[Pifagoroff]

Спасибо большое. Конечно, маршрут получился короче, примерно на 2 километра, чем в обход парка. Но как я предложу такой маршрут службе доставки? Если это не велодоставка? А не знаете, сколько по времени должен работать модуль, если проект сохранить в базе PostGIS?

[Voltron]

Спасибо большое. Конечно, маршрут получился короче, примерно на 2 километра, чем в обход парка. Но как я предложу такой маршрут службе доставки? Если это не велодоставка?

Увы, модуль пока не позволяет выполнять такую тонкую настройку. Может вам стоит посмотреть на pgRouting, раз вы все равно планируете хранить данные в PostGIS? Есть еще osm2po, небольшое введение написала underdark.

А не знаете, сколько по времени должен работать модуль, если проект сохранить в базе PostGIS?

К сожалению, тестирования на разных источниках данных не проводил, хотя это интересная тема.

[Pifagoroff]

pgRouting я пока не смотрел, только читал аннотации. Хочется найти программу, которая составляла бы автомобильный маршрут, скажем за 10-30 секунд. Тогда, можно для не очень большого числа точек подсчитать матрицу расстояний и попытаться решить задачу коммивояжёра…

[Александр Мурый]

В GRASS есть целая серия модулей (v.net.*) для сетевого анализа (см. здесь, здесь, а вот презентация в тему). Написано на чистом C, как я понимаю, работает довольно шустро.

[Pifagoroff]

Спасибо большое за ответ. А не можете привести какие-то цифры, как-то расшифровать понятие "работает довольно шустро". Для какой карты строился маршрут? Скажем слой дорог Москвы по числу полилиний на порядок больше, чем слой дорог для Владимира. А может и больше, чем на порядок. Считает больше минуты или меньше? Можно ли строить маршрут, не по всему слою, а по фильтру, построенному по атрибутам полилиний?

[Александр Мурый]

Спасибо большое за ответ. А не можете привести какие-то цифры, как-то расшифровать понятие "работает довольно шустро".

На дорогах Москвы не пробовал (кстати, интересно протестировать ) Цифры ищите в сети по словам "GRASS network analysis" или типа того. Предположил, зная обычные скорости работы векторных модулей GRASS и т.к. написано на C.

Считает больше минуты или меньше?

Если буду пробовать, замерю кол-во секунд.

Можно ли строить маршрут, не по всему слою, а по фильтру, построенному по атрибутам полилиний?

Можно предварительно вытащить нужные линии в другой "слой", в том числе, по атрибутам.

[Pifagoroff]

Можно предварительно вытащить нужные линии в другой "слой", в том числе, по атрибутам.

Можно, конечно, кто же спорит. Можно вообще в ручную, по слою дорог, создать маршрут и длину посчитать и красиво нарисовать на карте…