Самый простой способ получить граф - это преобразовать osm в польский формат (mp). Там граф представлен очень разумно. Для этого есть скрипт - osm2mp.pl.
Написал в форумную почту.
Ну вот для подготовки подобного графа я и сделал свой плугин, про который упоминал выше.
Устанавливаете osmosis, затем устанавливаете плугин osmrouting версии 1.2 (например в подкаталог plugins в текущем каталоге), качаете нужный регион с gis-lab и запускаете подобную строку:
osmosis --read-pbf RU-LEN.osm.pbf --lp --build-routing-graph graphLevel=secondary minorGraphsAction=drop --split-routing-graph --directed-graph-lines --write-xml RU-LEN_graph.osm.bz2
В данном пример выполняется фильтрация дорожного графа Ленобласти уровня secondary (с выкидыванием изолятов), далее этот граф разбивается по перекрёсткам и создаются двунаправленные линии. Результат можно открыть в JOSM и посмотреть. Если удовлетворяет - делаете процедуру конвертации полученного графа в вашу БД.
Плугин пока не обрабатывает отношения запретов проезда, но их обработку относительно легко добавить, если понадобятся.
Парни, а может я бы дал структуру своей БД, а вы бы её заполнили?
Я заплачУ.
Ко всей базе треков osm бы такое
Там бы еще максимальная скорость и высота (над GTOPO30 хотя бы) не помешали бы, как ограничение. Вот нафига там авиатреки?
Помочь разобраться - это завсегда пожалуйста.
А вот возиться с чужой задачей, пусть даже за деньги - тут желающих обычно мало.
На работе своих задач хватает…
[irony]рисовать авиамаршруты[/irony]
Где-то была тема для предложений о работе…
А по-моему, звучит весьма заманчиво.
Но с базами данных я знаком весьма поверхностно, так что сомневаюсь, что могу предлагать свои руки в этом вопросе.
Вот если бы перевести что-нибудь требовалось…
Ну, с базами данных я и сам разберусь, но мне просто нужна понятная структура с данными.
https://dl.dropbox.com/u/11083106/DATA.rar
Файл с базой. Там создано три узла и три ребра. Свойства узлов и ребер там задаются заморочено, поэтому для пробега можно просто создать отдельную таблицу, я бы её потом преобразовал.
Хм… А нельзя ли в каком-нть переносимом формате?
MSSQL под рукой нет.
А что есть?
Чтобы структуру посмотреть, dbf или даже csv достаточно
День добрый. В догонку к поднятой теме: а существуют в природе сервисы или API (платные или бесплатные), рассчитывающие помимо маршрута между точками, еще и последовательность проезда?
Т.е. входные данные: начальная точка, конечная и куча промежуточных в неопределенном порядке.
На выходе: последовательность проезда между промежуточными точками (для простоты по критерию “минимальный суммарный пробег”)
P.S. Если нет на базе OSM, то может есть на базе еще чего (2gis, Я.карты и т.п.), но чтобы считался и межгород, и внутригородские маршруты по РФ.
Задача коммивояжера, штоле?
Да, типа того.
Это NP-полная задача.
Да знаю я ее как решать каноничным способом и при каноничных условиях. Но зачем?
Дело в том, что я не вижу большого смысла изобретать велосипед, и уж тем более, как топикстартер, выкачивать гиги данных дорожного графа, обновлять всё это хозяйство регулярно, писать и отлаживать алгоритмы прокладки маршрута, вникать в форматы, при условии, что я сам не создаю новый суперпуперплатныйкоммерческий сервис. В остальных случаях зачем тратить такую гору ресурсов? Всё уже украдено написано до нас, вопрос лишь в том, чтобы найти подходящую, пусть даже платную, реализацию.
И, к слову, даже если у меня точек всего штук 20, нужно будет построить матрицу расстояний 20х20, сгенерить кучу запросов и обработать их. В том же OSRM построение “таблиц расстояний” запрещено, за что следует бан.
Конкретно для Свердловской области в стародавние времена существовала программа “СвО на блюдечке”, решавшая эту задачу и предоставлявшая платный API. Всё устраивало, но фирма-производитель загнулась и творение перестало отвечать реалиям.
Гугль имеет подобную бесплатную реализацию “Дирекшенс”, но дорожный граф для РФ убог до безобразия, праймари почти нет, нет даже некоторых транков.
ОСМ из того, что видел, справляется с задачей отлично и имеет самую актуальную базу, но все виденные реализации строят маршрут между точками, уже выстроенными в правильном порядке.