Форумы GIS-Lab.info

Pifagoroff писал(а):А Voltron говорит, нужно перебирать все дороги, тогда будет честное соревнование по скорости с модулем RoadGraph.

Вот не надо только передергивать.
То, что говорилось относилось к одному частному случаю. А именно к вашему сравнению вашей программы, работающей только с автодорогами, и RoadGraph, который вы гоняли на всех дорогах.

Постороитель маршрута не обязан различать типы дорог. Может, но необязан. И если нужно построить маршрут по каким-то одним дорогам ­— быстрее и проще всего, отфильтровать нужные типы уже с ними работать.

Voltron писал(а):

Pifagoroff писал(а):А именно к вашему сравнению вашей программы, работающей только с автодорогами, и RoadGraph, который вы гоняли на всех дорогах.

Такое сравнение корректно, и вот почему. Я скачиваю слой дорог из интернета (из проекта Gis-Lab), загружаю своей программой в базу. Потом ставлю в программе на карте две точки, нажимаю на кнопочку, получаю через 15 секунд маршрут. Настоящий маршрут заметьте, по которому можно ехать. Сравниваем с RoadGraph. Скачиваю c Gis-Lab карту и проект для qgis. Загружаю в qgis, ставлю на карте две точки и через полчаса … получаю… но понятно, что получаю… Короче, не поймёт меня пользователь, ой не поймёт, если я ему предложу в RoadGraph маршруты строить… Хотя и не обязан построитель маршрутов различать типы дорог, вовсе и не обязан. Про свой навигатор Вы вряд ли так думаете…

Pifagoroff писал(а):Такое сравнение корректно, и вот почему. Я скачиваю слой дорог из интернета (из проекта Gis-Lab), загружаю своей программой в базу. Потом ставлю в программе на карте две точки, нажимаю на кнопочку, получаю через 15 секунд маршрут.

Опять передергиваете. Цитата с вашего сайта

Первое, что нужно сделать – это загрузить слой дорог в базу. При этом будем загружать только полилинии имеющие следующие значения атрибута HIGHWAY:
Очень короткие дороги во дворах
service
Короткие дороги
Tertiary
tertiary_link
residential
unclassified
Протяжённые дороги
secondary
Магистрали, трассы, проспекты, шоссе
motorway
primary
trunk
Развязки
trunk_link
secondary_link
motorway_link
primary_link
Этим мы ограничиваем построение маршрута только по автомобильным дорогам.

Для RoadGraph фильтрация не выполнялась. Вы все еще утверждаете, что сравнение корректно? Извините, в таком случае продолжать разговор не вижу смысла.

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

Загружаю в qgis, ставлю на карте две точки и через полчаса … получаю… но понятно, что получаю…

Во-первых, 99.99999% времени плагин тратит на то что бы из сырых данных сделать граф пригодный для анализа. Расчет кратчайшего маршрута я даже в прогресс-бар не добавлял. Он мгновенен, по сравнению с "из сырых данных..." . Всякого рода навигаторы в своих картах уже имеют эту выжимку, т.е. хранят два набора данных: один для отображения, другой для поиска пути. PgRouting тоже работает с "выжимкой". RoadGraph не работает (пока!) с выжимкой по политическим соображениям.
К этому недостатку можно еще добавить то, что Road Graph требует значительные объемы ОЗУ (особенно в QGIS 1.7, в 1.8 уже полегче будет). Я стараюсь балансировать на гране простоты реализации/возможностей плагина.

Во-вторых, плагин не производит фильтрацию дорог по их типу. Более того, многие "дороги" даже не отображаются на экране (по крайней мере в Тюменской области). Если Вам не нужны велодорожки - удалите их. Средства для этого в QGis'е есть.

В-третьих и самых главных.
Я вижу будущее моего плагина как универсального средства для анализа сети. Да, сейчас он выглядит как приблуда для прокладки маршрута, но в апстриме доступна питон-библиотека с базовыми возможностями, а в моих экспериментальных сборках плагин умеет искать кратчайший путь на растре: смотреть тут. (Сегодня пробовал на растре 1700х3500px. Отрабатывает секунд за 30)
Закончу с растрами, займусь классическими алгоритмами: задача коммивояжера, минимальное дерево Штайнера/Остовное дерево, анализ близости/доступности... но это все для людей, которые понимают с чем имеют дело и зачем оно вообще нужно. Для тех, кому "поставил две точки и вперед" есть Navintel по доступным ценам. Ей, народ, поддержите меня!

Да уж поддержал, куда уж еще См. тезисы на прошлой странице.

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

Да, алгоритм Дейкстры. Все, что классифицирует типы дорог - тоже Дейкстры, только отношение сравнения другое.

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

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

Столько же если не больше.

Да уж поддержал, куда уж еще См. тезисы на прошлой странице.

ericsson, я ждал от тебя что-то вроде "В баню эти навигаторы с их "через 50 метров поворот налево"!!! Давай, stopa85, сделай нам полноценный network-analysis в QGis!!!"

stopa85 писал(а):Ей, народ, поддержите меня!

Куда донейты слать-то? Доку по обвязке я пилю потихоньку.

stopa85 писал(а):Давай, stopa85, сделай нам полноценный network-analysis в QGis!!!"

Как говорится, special for you #4312

stopa85 абсолютно прав!
У меня алгоритм Дейкстры на готовом графе работает менее 1 секунды.
На матрице 1000x1000 узлов выполняется за 0,28 секунды. Пробовал и на больших массивах < 1 сек. Основное время тратится на загрузку из базы в массив.
И еще, практически всегда можно выделить из общего графа дорог ту часть, которая необходима для анализа и работы алгоритма Дейкстры, т.е. нет необходимости анализировать весь граф. С помощью индексирования избавляюсь в анализе от “неинформационных” узлов, т.е. например полилиния может содержать 50 узлов, а достаточно двух.
Pifagoroff разве можно при текущем состоянии информации в OSM (сырые данные) в принципе построить правильный транспортный граф?Я, например, внутри одного населенного пункта вижу несколько других(на самом деле это должны быть улицы). Посмотрите на Ваш район, где Вы живете и хорошо знаете дорожную обстановку. Для тестов, курсовой, дипломный …подойдет, не более.
stopa85 ждем продолжения Вашей замечательной работы. Полностью поддерживаю.
Просто есть такой способ освоения материала - провокация.
Хорошо было бы пообсуждать алгоритмы, которые Вы планируете реализовывать.

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

Такой функционал востребован в работах по экологической безопасности. Я читал одну интересную канадскую работу, посвящённую транспортировке опасных грузов. Там припрокладке маршрута учитывалось не только расстояние между точками, но и плотность населения и вероятность ДТП. Причём плотность населения, если не ошибаюсь, была в виде растра.

В идеале, хотелось бы, чтобы плагин расчитывал самый быстрый/которкий маршрут с учётом нескольких дополнительных параметров, и даже с учётом значений из растровой подложки.

Что бы еще можно было добавить в плагине? Например, поиск кратчайшего маршрута для сети городского транспорта. Как добраться из одной точки города в другую с минимальным количеством пересадок и за кратчайшее время / кр.путь.

Во-первых: в баню эти навигаторы с их "через 50 метров поворот налево"!!! Давай, stopa85, сделай нам полноценный network-analysis в QGIS!!

Во-вторых: поигрался с кратчайшим маршрутом в GRASS по дорогам Москвы.
Машина: Lenovo Ideapad V560 (Core i3, 2.53GHz, память 3Gb)
ОС: Ubuntu 10.04.03 LTS
GRASS 6.4.2svn49260.

Координаты начальных/конечных точек маршрутов А-А' и Б-Б' --- на картинке, дороги отфильтрованы как упоминалось выше в теме (только автомобильные), почищена топология, всего 144624 линий.
Время построения засекалось с помощью утилиты time.

Маршрут А-А': Маршрут Б-Б': Не сочтите за оффтоп, просто для сравнения ПО

bim2010 писал(а):На матрице 1000x1000 узлов выполняется за 0,28 секунды.

Я счастлив! Только где-это вы видели матрицы 1000x1000? Можт 10 000 х 10 000 больше похоже на правду? или даже 100 000?

amuriy писал(а):Во-первых: в баню эти навигаторы с их "через 50 метров поворот налево"!!! Давай, stopa85, сделай нам полноценный network-analysis в QGIS!!

Во-вторых: поигрался с кратчайшим маршрутом в GRASS по дорогам Москвы.
Машина: Lenovo Ideapad V560 (Core i3, 2.53GHz, память 3Gb)
ОС: Ubuntu 10.04.03 LTS
GRASS 6.4.2svn49260.

Координаты начальных/конечных точек маршрутов А-А' и Б-Б' --- на картинке, дороги отфильтрованы как упоминалось выше в теме (только автомобильные), почищена топология, всего 144624 линий.
Время построения засекалось с помощью утилиты time.

Маршрут А-А':

Код: Выделить всё

time echo "1 37.134567 56.029486 37.945861 55.794829" | v.net.path in=moscow_roads_clean_filter out=moscow_roads_clean_filter_path1 --o

real   0m6.404s
user   0m6.048s
sys    0m0.340s

Маршрут Б-Б':

Код: Выделить всё

time echo "2 37.561133 55.471948 37.470181 56.024938" | v.net.path in=moscow_roads_clean_filter out=moscow_roads_clean_filter_path2 --o

real    0m6.410s
user    0m6.048s    
sys     0m0.332s

network_Moscow_path_1_2.png

Не сочтите за оффтоп, просто для сравнения ПО

Вот это уже кое-что... И не так уж плохо для моей программки! Ей Богу не плохо!

Pifagoroff писал(а): Вот это уже кое-что... И не так уж плохо для моей программки! Ей Богу не плохо!

Прекрасно, надеюсь, вы уже подали заявку на премию Тьюринга?
И да, кстати, вы не хотите выпустить вашу программу под открытой лицензией?

Я счастлив! Только где-это вы видели матрицы 1000x1000? Можт 10 000 х 10 000 больше похоже на правду? или даже 100 000?

На самом деле тестировал на трехмерной матрице 1000*1000*1000
На алгоритме Дейкстры транспортная задача не заканчивается.
Для организации, имеющей в справочнике потенциальных клиентов около 3000 организаций, необходимо было в течение 1 дня осуществить доставку менее 1000 клиентам.
stopa85 уже Вам писал, что реальный транспортный граф и набор данных для отображения это две больших разницы.
Так и сам транспортный граф по одним и тем же объектам не один.
В одном случае г. Москва = 1 узел
Во втором случае г. Москва = 64 узлов = зоны (кол-во зон определялось эмпирически)
В третьем случае г. Москва = кол-во перекрестков + кол-во точек доставки
И т.д. …
Переход с одного уровня на другой делаю с помощью индексов (хотя можно было и в отдельном слое).Поставив произвольно точки А и Б на карте через сколько узлов у Вас проходит маршрут?
Если у Вас их 1000 и более Вы неправильно строите транспортный граф, или скажем не оптимально.

Другой пример: осмеры нарисовали памятники Курган Бессмертия и самолет в виде полигонов, каждый из которых состоит из более 50 точек. А я считаю эти POI как два точечных объекта.