Поиск кратчайшего расстояния на графе дорог. Протестируйте
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Патч в трак будет завтра, ближе к полуночи.
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
3416 посмотрим, что скажут.
Voltron, прости, добавил без локализации. В нашем svn она есть. За окошко about спасибо.
Приоритетными направлениям работы над плагином являются:
1. Интергация с bgl с целью поддержки большего количества алгоритмов на графе. Саму библиотеку я не знаю, так что ждите.
2. Построение графа по полигональным слоям: это, в месте с первым, даст огромные возможности QGis'у в части сетевого анализа. Однако тут нужен развитый "fTools" в ядре к qgis (не дублировать же функционал). Так что придеться поработать и над этим.
Voltron, прости, добавил без локализации. В нашем svn она есть. За окошко about спасибо.
Приоритетными направлениям работы над плагином являются:
1. Интергация с bgl с целью поддержки большего количества алгоритмов на графе. Саму библиотеку я не знаю, так что ждите.
2. Построение графа по полигональным слоям: это, в месте с первым, даст огромные возможности QGis'у в части сетевого анализа. Однако тут нужен развитый "fTools" в ядре к qgis (не дублировать же функционал). Так что придеться поработать и над этим.
-
- Гуру
- Сообщения: 2627
- Зарегистрирован: 29 мар 2007, 14:12
- Репутация: 34
- Откуда: Ukraine
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
C r15068 модуль RoadGraph стал частью QGIS.
stopa85, спасибо и успехов в дальнейшем совершенствовании модуля!
stopa85, спасибо и успехов в дальнейшем совершенствовании модуля!
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Начиная с r15239 в плагине появилась возможность установить "топологическую толерантность".
Если две точки находяться на расстоянии меньше чем порог толерантности то они считаются одной точкой. Это позволяет использовать для вычислений не иделаьно связанные вершины, однако способствует появлению артефактов. Другой проблемой является то что работает это медленно.
Ну а просьба все таже протестировать.
Если две точки находяться на расстоянии меньше чем порог толерантности то они считаются одной точкой. Это позволяет использовать для вычислений не иделаьно связанные вершины, однако способствует появлению артефактов. Другой проблемой является то что работает это медленно.
Ну а просьба все таже протестировать.
- Вложения
-
- скриншот
- снимок5.jpeg (111.33 КБ) 13996 просмотров
-
- Гуру
- Сообщения: 2627
- Зарегистрирован: 29 мар 2007, 14:12
- Репутация: 34
- Откуда: Ukraine
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Небольшой скринкаст от Тима, демонстрирующий модуль в действии.
-
- Гуру
- Сообщения: 977
- Зарегистрирован: 27 янв 2009, 22:57
- Репутация: 258
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
В статье поиск кратчайшего маршрута c помощью Road graph для QGIS
В тексте для windows
В тексте для windows
хорошо бы добавить путь, например: C:\Program Files\Quantum GIS Copiapo\apps\qgis\pluginsзагрузить файл расширения и скопировать его в каталог расширений QGIS
-
- Интересующийся
- Сообщения: 34
- Зарегистрирован: 19 дек 2011, 20:24
- Репутация: 0
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Здравствуйте. Возможно, я делаю, что-то не так. Загружаю проект для Москвы в qgis, полученный вот отсюда: http://gis-lab.info/projects/osm_shp/region . Пытаюсь построить с помощью модуля маршрут. У меня получился маршрут через Битцевский парк, по велодорожкам. Сколько, примерно, по времени должен работать модуль, что бы построить маршрут по Москве, по автомобильным дорогам и как это сделать? У меня модуль работал никак не меньше 10 минут. Можно ли узнать, какие алгоритмы поиска используются в модуле. Спасибо.
-
- Гуру
- Сообщения: 2627
- Зарегистрирован: 29 мар 2007, 14:12
- Репутация: 34
- Откуда: Ukraine
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Видимо, маршрут по дорожкам наиболее короткий . Если не ошибаюсь, используется алгоритм Дейкстры.
-
- Интересующийся
- Сообщения: 34
- Зарегистрирован: 19 дек 2011, 20:24
- Репутация: 0
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Спасибо большое. Конечно, маршрут получился короче, примерно на 2 километра, чем в обход парка. Но как я предложу такой маршрут службе доставки? Если это не велодоставка? А не знаете, сколько по времени должен работать модуль, если проект сохранить в базе PostGIS?
-
- Гуру
- Сообщения: 2627
- Зарегистрирован: 29 мар 2007, 14:12
- Репутация: 34
- Откуда: Ukraine
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Увы, модуль пока не позволяет выполнять такую тонкую настройку. Может вам стоит посмотреть на pgRouting, раз вы все равно планируете хранить данные в PostGIS? Есть еще osm2po, небольшое введение написала underdark.Pifagoroff писал(а):Спасибо большое. Конечно, маршрут получился короче, примерно на 2 километра, чем в обход парка. Но как я предложу такой маршрут службе доставки? Если это не велодоставка?
К сожалению, тестирования на разных источниках данных не проводил, хотя это интересная тема.Pifagoroff писал(а):А не знаете, сколько по времени должен работать модуль, если проект сохранить в базе PostGIS?
-
- Интересующийся
- Сообщения: 34
- Зарегистрирован: 19 дек 2011, 20:24
- Репутация: 0
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
pgRouting я пока не смотрел, только читал аннотации. Хочется найти программу, которая составляла бы автомобильный маршрут, скажем за 10-30 секунд. Тогда, можно для не очень большого числа точек подсчитать матрицу расстояний и попытаться решить задачу коммивояжёра…
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
В GRASS есть целая серия модулей (v.net.*) для сетевого анализа (см. здесь, здесь, а вот презентация в тему). Написано на чистом C, как я понимаю, работает довольно шустро.
Редактор материалов, модератор форума
-
- Интересующийся
- Сообщения: 34
- Зарегистрирован: 19 дек 2011, 20:24
- Репутация: 0
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Спасибо большое за ответ. А не можете привести какие-то цифры, как-то расшифровать понятие "работает довольно шустро". Для какой карты строился маршрут? Скажем слой дорог Москвы по числу полилиний на порядок больше, чем слой дорог для Владимира. А может и больше, чем на порядок. Считает больше минуты или меньше? Можно ли строить маршрут, не по всему слою, а по фильтру, построенному по атрибутам полилиний?
-
- Гуру
- Сообщения: 5173
- Зарегистрирован: 26 сен 2009, 16:26
- Репутация: 793
- Ваше звание: званий не имею
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
На дорогах Москвы не пробовал (кстати, интересно протестировать ) Цифры ищите в сети по словам "GRASS network analysis" или типа того. Предположил, зная обычные скорости работы векторных модулей GRASS и т.к. написано на C.Pifagoroff писал(а):Спасибо большое за ответ. А не можете привести какие-то цифры, как-то расшифровать понятие "работает довольно шустро".
Если буду пробовать, замерю кол-во секунд.Pifagoroff писал(а): Считает больше минуты или меньше?
Можно предварительно вытащить нужные линии в другой "слой", в том числе, по атрибутам.Pifagoroff писал(а): Можно ли строить маршрут, не по всему слою, а по фильтру, построенному по атрибутам полилиний?
Редактор материалов, модератор форума
-
- Интересующийся
- Сообщения: 34
- Зарегистрирован: 19 дек 2011, 20:24
- Репутация: 0
- Откуда: Москва
Re: Поиск кратчайшего расстояния на графе дорог. Протестируй
Можно, конечно, кто же спорит. Можно вообще в ручную, по слою дорог, создать маршрут и длину посчитать и красиво нарисовать на карте…amuriy писал(а): Можно предварительно вытащить нужные линии в другой "слой", в том числе, по атрибутам.
Кто сейчас на конференции
Сейчас этот форум просматривают: Semrush [Bot] и 2 гостя