Подсунул коду (развязки пока не стягивает, только геометрию цепочек срубает).
Если без residental-ов, то узла не делает. 
Дуйте через Птицеград, говорит.
Спасибо за тест-вектор
Медитирую над Таганской площадью http://osm.org/go/0t2wPOcvO– и Шарлем де Голля http://osm.org/go/0BPIBrF~A–
Ну во, от задачи №8 уже есть первая польза - стоило ввести в код контроль односторонности и направления, как оптимизатор не упростил мне вот этот сегмент полосы с остальным проспектом, полез проверять, а оно не одностороннее, хотя остальная полоса проспекта односторонняя 
ой
Какой-нибудь из имеющихся валидаторов умеет детектировать такую потенциальную ошибку однонаправленности?
Если на узле:
UPD: Исчо одна бага была, исправил
Zkir,
Первый вариант стягивания развязок в точку, на том же наборе входных данных.
Сначала оптимизировано Дугласом-Пеккером с е=0.005 градуса, а потом стянуты развязки (все link-и + все сегменты короче l=0.003 градуса). Класс дорог учтён, двухвейки в одновейки не склеены, дублирующие рёбра не склеены, скорость не усреднена. Роутинг работает, хоть и не идентично исходному .mp.
Похоже на движение в правильном направлении?
Ничего себе! Очень похоже!
Мне кажется теперь нужно
Удалить “белые” ноды, объединяя где надо веи. (белые ноды - это перекрестки из одной дороги, они не нужны).
Стянуть близкие желтые ноды.
Например, ноды 71701 и 72160, между ними расстояние 125 метров. Это уцелевшая развязка. В обзорной карте она не нужна.
Наверно, это и будет решение задачи 
А дуглас-пойкер мне кажется не нужен, или его делать на финальном этапе. Он как-то влияет на стягивание развязок?
- Удалить “белые” ноды, объединяя где надо веи. (белые ноды - это перекрестки из одной дороги, они не нужны).
В этом случае существенно портится геометрия. Например primary Выдропужск-Спирово-Калашниково-Лихославль-(Медное) схлопывается до Выдропужск-Медное - почти хордой к М10. Ну может быть когда в данных будут secondary, этого схлопывания не будет, но будут другие
- Стянуть близкие желтые ноды.
Например, ноды 71701 и 72160, между ними расстояние 125 метров. Это уцелевшая развязка. В обзорной карте она не нужна.
Да, близкие будут стягиваться. В том числе при склейке двухвеек в одновейки, это ещё не делал.
- Удалить дубликаты, понимая под дубликатами участки дорог, проходящие между двумя соседними нодами, пусть и с разной геометрией.
Обязательно.
А дуглас-пойкер мне кажется не нужен, или его делать на финальном этапе. Он как-то влияет на стягивание развязок?
Дуглас-Пеккер как раз убивает тысячи промежуточных (“белых”) нодов на дорогах между развязками. Кроме того, он спрямляет дороги непосредственно у развязки, что помогает точнее найти центральную точку развязки - сейчас ищется точка, минимально удалённая от всех линий, входящих в развязку со всех сторон. По не спрямлённым отрезкам (например, дороги расходятся до подключения к разворотному кругу) центральную точку искать сложнее.
Но ещё поэкспериментирую.
Нет-нет-нет.
Польский файл, в отличие от осм, состоит из геометрии и топологии отдельно. Геометрия представлена полем Data0=, а топология списком нод Nod1, Nod2, Nod3, … NodN. При этом у длинного вея (например) могут быть сотни вершин (с координатами) в Data, а рутинговых нод всего три (начало, конец, и некое место в средине, где этот вей пересекается с другой дорогой). В пункте 1 я имел ввиду чисто топологическую оптимизацию - объединение сегментов и удаление лишних р-нод. Геометрию этот пункт затрагивать не должен.
Например, вот кусок M8, к северо-востоку от первой бетонки.
Сейчас он состоит из множества отрезков веев, каждый из которых состоит из двух геометрических вершин, и двух рутинговых нод.
Напрашивается объединить эти отрезки, и сделать два вея, каждый будет состоять из тех же самых вершин (каждый, судя по рисунку, из 5-7) и двух р-нод, на них указывают стрелочки.
После этого станет ясно, что коль скоро два вея имеют начало и конец в одних и тех же р-нодах, они дубликаты и есть.
Тут я не берусь ничего советовать, просто прошу обратить внимание, что тысячи “белых” нодов на дорогах между развязками можно (и нужно) убить чисто топологически.
Вот кстати данные с секондари:
http://peirce.gis-lab.ru/misc/RU-OVRV/RU-OVRV.zip
Нет-нет-нет.
Польский файл, в отличие от осм, состоит из геометрии и топологии отдельно.
В пункте 1 я имел ввиду чисто топологическую оптимизацию - объединение сегментов и удаление лишних р-нод. Геометрию этот пункт затрагивать не должен.
тысячи “белых” нодов на дорогах между развязками можно (и нужно) убить чисто топологически.
А, такое объединение сделаем, конечно, но в самом конце.
Вот кстати данные с секондари:
Спасибо, будет главным тест-вектором
Проход более продвинутого алгоритма по Москве: http://ge.tt/22bdQ3P?c
Внутри 121030exp.gen.rar:
Наблюдается схлопывание в точку:
Поскольку в каждом случае всё это связано плотным клубком link-ов, разделить алгоритмические на отдельные перекрёстки не представляется возможным.
Либо нужно соглашаться на такое схлопывание в точку, либо отказываться от того, что каждый link должен стягиваться в точку. Во втором случае нужен не алгоритм анализа геометрии (две параллельные ломаные, короткие циклы), а типа гравитационного, чтобы близкие узлы и отрезки притягивались друг к другу, слипаясь в ломанные.
P.S. С “бородой” в районе м. Аэропорт и подобным ещё буду бороться.
OverQuantum, ничего себе)
Двухвейки объединились. Но хотелось бы увидеть и Россию. Москва, как известно, это еще не вся Россия
Или типа кластерного. Найти места скопления вершин, а потом их объединить.
Наверно, в постановке задачи, где говориться про стягивание линков, это нормально.
А так ли уж обязательно именно стягивать в точку, а, скажем, не выбирать между стягиванием в точку и удалением?
Ну что значит удалением?) Если что-то удалить за просто так, поломается рутинг.
Возможно, правило должно быть таким: если две рутинговые вершины соседствуют сразу в линке и в “нормальной” дороге, то линк стягивать не надо, а нужно удалить.
В общем случае - если при удалении линка не будет нарушена связность. Хотя формулировка критерия связности - отдельная задача.
Алгоритм пока в отладке и поэтому не шибко оптимизирован. Россия будет считаться долго.
По плану - довести функционально до нужной генерализации и потом уже выжимать скорость.
Ладно, доделаю алгоритм анализа геометрии а потом будут экспериментировать с гравитационным.
Есть подозрение, что гравитационный лучше будет распараллеливаться.
Можно чуть подробнее пояснить? Если речь идёт о петле, которая возвращается к той же основной дороге с той же стороны от перекрёстков, то мой алгоритм её фактически удалит. Сейчас все конструкции из линков рассматриваются только в точках их подключения к основным дорогам. Они стягиваются как пружинные конструкции (точки подключения “скользят” вдоль дорог друг к другу) чтобы найти какие из основных дорог друг к другу подключены и отметить фрагменты этих дорог внутри развязки.
Их есть у нас! Версия вторая
Считалось 40 минут в дебаг-интерпретаторе, но я уже вижу как в 2-х местах резко ускорить
Зелик-Нижний прокладывает как по оригинальной mp (не по объездной Владимира, почему-то).
Зелик-Владивосток прокладывает заметно быстрее, чем по оригинальной mp (маршруты не сравнивал).
Инфа о багах и явных некорректных схлопываниях - привествуется.
UPD: Рассчёт ускорен до 3.5 минут в дебаг-интерпретаторе.
UPD2: автозимник “Арктика”, М56 - Сасыр и автозимник “Арктика”, Сасыр - Зырянка схлопнулись в одну развязку, которая оказалась хрен знает где, ибо оба автозимника - highway=primary_link 
UPD3: Ссылка заменена на 2ю версию, ибо исправлен баг при сохранении односторонних дорог в .mp, 110 односторонних дорог были записаны не с тем направлением. Например, Большая Ордынка вела в центр.
Как интересно. Посмотреть подробно смогу в выходные)
Это надо в осм поправить)
Кстати, реквестирую валидатор, который показывает hw=*_link длиной, скажем, более полукилометра.
