Работа с графом дорог

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

leaf - в вики, ключевые слова osmosis, osm2pgsql.

Про локальную копию - Ezhick подсказал (кстати если его подонимать в личке он наверное и побольше расскажет :slight_smile: )

Айдишники не совсем постоянны:

Заменили одновейную улицу 2хвейной (старую грохнули создали 2 новых) - естественно будет 2 новых объекта с новыми айдишниками никак не связанными с пердыдущими.
Распилили 1 улицу на 2 (3, 4, 5…) связанных куска - 1 объект остался прежним - сохранил айдишник, второй (3ий, 4ый, 5ый…) получили новые, опять же не связанные с тем что был.

С точками примерно та же петрушка.

И да, что печально - это поведение на совести редактора т.к. постоянства айдишников ничто не гарантирует.

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

Про айдишники.

Всплывала на форуме тема про алгоритмы сравнения графов: дескать как бы посчитать такую метрику для участков графа, чтобы 1 участок графа полученный из другого с незначительными правками (1 ребро заменили на 2 параллельных либо 1 ребро заменили на цепь ребер) имел близкую метрику. Правда дальше теоретических рассуждений дело не пошло.

Ну и ещё. Если вы хотите пробки - то в любом случае все роутинговые веи, думается, надо разбивать на 2 одновейных. Иначе как вы скажете в какую сторону пробка?

Ой, вот тут вы не правы. Совсем. И, главное, топикстартер про пробки ничего не говорил!!!

совсем никак не связанные? или всё-таки можно вычислить произошедшие изменения?
я тут пока изучаю и где-то натыкался на то что есть какая-то “версионализация” в OSM. Ведется ли что-то вроде истории версий? Хотя это не особо облегчит задачу.
Да, надо будет хорошенько подумать как с этими обновлениями поступать.

Заранее, спасибо. Как только с основами разберусь и если что-то будет непонятно обращусь.

Ну теоретически некоторые изменения можно вытащить из истории:

Если линию поделить на 2 сегмента это равносильно:
создать 1 новый сегмент с половиной точек из старого.
отредактировать старый сегмент сохранив в нем половину точек.
(josm, potlatch1, potlatch2 вроде так и делают).

Соответственно 1 кусок сохранит часть истории вея, так же будет ревизия в которой точки с такими то айди были удалены из вея 1 и включены в новый вей 2.

Но опять же никто не мешает редактору сформировать xml с изменениями след. образом:
Грохнуть старый, создать 2 новых вея - в этом случае у новых версия будет 1 история пропадет. Останется теоретическая возможность вытащить ревизию в которой это произошло и по id точек догадаться что линию распилили. Но это геморой наижутчайший.

Проще вам наверное експеримент поставить где-нибудь в тундре, посоздавать веев поизменять их, поредактировать атрибуты, подобавлять/поудалять точек. По объединять/по разделять линии и т.п. и посмотреть что пишется в историю и в osm-change.xml, на пальцах это не шибко понятно выглядит.

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

Можно вести свою базу с нужными объектами и их версиями, и периодически скачивать номера версий этих объектов. При обнаружении изменения версии докачивать объекты.

А сколько приблизительно весит база с графом дорог России в ОСМ? Как часто происходят изменения? Насколько они масштабные обычно?

Изменения происходят ежесекундно, а конкретно в графе дорог РФ… Да черт его знает, может, раз в минуту, может, раз в 10 минут.

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

Насколько я знаю, отдельную выгрузку только с графом дорог (тем более России) никто не делает. Можно взять полную выгрузку России, например с gis-labа (по невероятному стечению обстоятельств на данный момент выгрузка недоступна), и с помощью osmosisа отфильтровать по нужным тегам (highway=).
Как часто происходят изменения? Да постоянно
, ежесекундно кто-то что-то где-то правит. Касаются ли эти изменения графа - вполне вероятно. Но очень уж масштабных изменений обычно нет.


    • Щелкнуть на “ticker”

Я сделал себе скрипт, чтобы импортировать из osm в mongoDB, там можно делать что угодно довольно просто. Бью пути на сегменты (между 2 точками), считаю для них веса, дальше буду пробовать алгоритмы трассировки.

Вот, например, как в mongo выглядит запрос, который делает из путей сегменты, сохраняя теги (чтобы можно было учитывать у каждого сегмента полосность и покрытие)

db.way.find().forEach(function(w) {
    var nodes = w.nodes.map(function(v) { return v.ref }), // make nodes array of `ref` attributes of nodes in the ways
        from = nodes.slice(0, nodes.length - 1), // first nodes of segments are all but the last node
        to = nodes.slice(1); // last nodes of segments are all but the first node
    /* if nodes were [1, 2, 3], I need [1, 2] and [2, 3] to make [[1, 2], [2, 3]] */
    var zip = function(v) { // pop from both `from` and `to` arrays and make them a segment with way's id, way's tags
            db.segments.save({way: w.id, tags: w.tags, from: from.shift(), to: to.shift()});
        };
    from.map(zip); // map is quicker than the `for` loop
});

Работать с базой данных на JavaScript - это колоссальное облегчение участи программиста!

А сколько всего “рёбер” в графе дорог России?
Может кто-то знает, как это проверить не скачивая всю карту…

На карте этого нет. Только когда конкретно построишь граф, тогда и узнаешь. А зачем это знать?

Есть небольшая статистика по регионам.
Вот небольшой регион:
http://wowik.byethost7.com/routes/ru-yev/clusters.htm

Смотрим самый низ и видим, что все дороги вплоть до track включительно
6572 штук way
Общей длиной 7183.7 км

Смотрим повыше и видим, что Если track не включать, то
5039 штук way
Общей длиной 3840.1
и т.д.

Количество way это не совсем количество ребер, но что-то близкое.

  1. Если к way в середину приклеивается другой, то ребер три, а не два.
  2. Если два вея просто сцеплены друг с другом, без соединений с чем-либо, то это одно ребро. Например на них разная полосность или освещение.
    А может и два, если важно, что скорость на них разная.

Вы что под ребром понимаете?

Совсем грубо число osm-веев с междугородними дорогами можно прикинуть полистав валидатор дорог от Вовика:

http://wowik.byethost7.com/routes/ru-sve/1.htm

Еще какие-то циферки вот тут вверху: http://wowik.byethost7.com/routes/ru-sve/clusters.htm

Попробовал прогнать свой конвертер по файлу https://download.geofabrik.de/russia-latest.osm.pbf
Если включить все автодороги до уровня track (т.е. кроме пешеходных), то всего там ~5.2 млн. отдельных way. С учётом связности наибольший кусок связанного графа включает в себя ~5.1 млн. отдельных way. Но это именно osm-ные way, до разбивки по перекрёсткам. С разбивкой получается ~11 млн. рёбер ненаправленного связанного графа у наибольшего куска. Для направленного графа рёбер получается ещё вдвое больше, ~21 млн.

Объединения последовательных цепочек рёбер не выполнялось (например там где дорога без ветвлений проходит через мост или разбита по какой-либо другой причине).