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

leaf · 2011-05-20T11:46:07.000Z

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

Ezhick · 2011-05-20T11:47:22.000Z

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

dkiselev · 2011-05-20T11:54:10.000Z

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

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

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

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

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

Ezhick · 2011-05-20T11:56:17.000Z

dkiselev:

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

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

dkiselev · 2011-05-20T12:01:21.000Z

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

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

VikDD · 2011-05-20T12:06:24.000Z

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

Ezhick · 2011-05-20T12:08:58.000Z

VikDD:

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

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

leaf · 2011-05-20T12:10:15.000Z

dkiselev:

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

Заменили одновейную улицу 2хвейной (старую грохнули создали 2 новых) - естественно будет 2 новых объекта с новыми айдишниками никак не связанными с пердыдущими.

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

Ezhick:

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

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

dkiselev · 2011-05-20T12:32:06.000Z

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

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

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

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

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

Ezhick · 2011-05-20T12:53:13.000Z

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

Ilis · 2011-05-20T12:58:15.000Z

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

leaf · 2011-05-20T13:20:47.000Z

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

Hind · 2011-05-20T13:27:30.000Z

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

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

AkMeR · 2011-05-20T13:38:25.000Z

leaf:

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

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

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

siberiano · 2011-05-20T16:43:07.000Z

Я сделал себе скрипт, чтобы импортировать из 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 - это колоссальное облегчение участи программиста!

Aleks_Shmaleks · 2020-03-12T13:26:50.000Z

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

freeExec · 2020-03-12T15:54:25.000Z

Aleks_Shmaleks:

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

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

wowik · 2020-03-13T08:15:17.000Z

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

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

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

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

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

Mir76 · 2020-03-17T09:07:03.000Z

Aleks_Shmaleks:

А сколько всего “рёбер” в графе дорог России?

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

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

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

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

Sergey_Astakhov · 2020-03-19T18:52:08.000Z

Aleks_Shmaleks:

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

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

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