В идеале должно получиться примерно так же, как если бы рисовали руками - т.е. с простановкой oneway на одновейки + запреты поворотов/разворотов. Допустимость поворотов можно тестировать каким-нибудь упрощённым маршрутизатором, т.к. граф на перекрёстках минимальный - сгодится практически любой алгоритм поиска маршрута.
Да я уже понял что проблемы не тут. Я вот к примеру даже на бумажке слабо представляю себе как схлопнуть двухвейку с дублерами каждого направления. НАдо порисовать такое на бумажке и пообсуждать - тогда и алгоритм начнет более ли менее вытанцовываться.
Там просто могут возникнуть приколюхи типа: направо - только с дублера, налево только с основной, прямо - с обоих. Такую штуку в рамках текущих запретов по 3 точкам после схлапывания уже не описать.
Мне кажется, в рамках текущих запретов такое как раз очень хорошо описывается: запретов нет. Для генерализованной карты важно лишь то, можно ли повернуть с данной дороги хоть как-нибудь (из какой-то полосы, с дублёра, через развязку).
И еще вопрос который лежит вне алгоритма - на сколько мы готовы пожертвовать эквивалентностью преобразования? Т.е. если вот тут http://osm.org/go/2YpZH_Kd@– схлопнуть Малышева и выкинуть второстепенки (а именно сервис петельку под мостом) то стремясь сделать преобразование эквивалентными нужно перекресток со студенческой преоброзовать в обычный (где разрешены все маневры) - это правильно для роутинга но алгоритм усложняет на порядок.
- порубить карту на тайлы, так, чтобы в каждый тайл попадала одна развязка целиком
- найти пересечение всех дорог с границей тайла
- сгенерировать перекресток, состоящий из линий, сходящихся в центр масс всех дорог внутри тайла.
- расставить на сгенерированном перекрёстке запреты так, чтобы соединения, по которым запрещён проезд в исходном графе, нельзя было пройти в сгенерированном.
Не очень понял причем здесь сервис-петелька. Сервис вообще к транзиным дорогам не относятся, так что эта петелька никакой роли в рутинге не играет.
Эквивалентное преобразование в данном случае такое.
- Малышева становится одновейной.
- Перекресток Малышева и Студенческой становится точкой.
- На этом перекрестке ставятся следующие запреты - со Студенческой с обоих сторон на Малышева только направо, проезд прямо по студенческой закрыт. С Малышева на Студенческую левые повороты с обоих сторон запрещены.
И опять же, в обзорной карте residential и даже tertiary не нужен. Так что запретов должно стать не больше, а меньше.
Скажем так, до 50000 ребер в дорожном графе, причем ребро понимается как кусок дороги между перекрестками.
- Выбрать из базы дороги trunk-secondary и соответствующие им линки.
- Нарезать всю карту на гексагональные ячейки (например, километрового диаметра).
- Если по исходному графу можно попасть из данной ячейки в соседнюю, создать в обобщенном графе ребро, соединяющее центры этих ячеек.
- Выполнить п.3 для всех ячеек.
- Упростить форму получившегося графа дуглас-пойкером.
Ну вот сейчас я могу, проехавши под мостом развернуться на Малышева или проехать по Студенческой. Но это так - частный случай, и таким маневром хорошо если 5 машин в день воспользуется. Но в целом - понятно за эквивалентность убиваться не стоит.
А для обзорной карты нужна информация о том, из каких начальных веев она была получена?
Имхо, это скорее значит, что петля под мостом - не service.
Рискну показаться непонятым … но известен принцип - кому надо тот и делает. Пока Zkir сам не сделает, вряд ли он признает результаты генерализации приемлимыми 
Поясню.
Любая сложная задача это постоянный поиск компромисса. Генерализация одна из сложнейших задач и её принципиальная особенность - гибкие требования к генерализации. Поэтому генерализация карты это итеративный процесс и постоянная смена правил с целью поиска оптимального решения. Человек ставящий задачу не может создать полный комплекс правил по генерализации. Тогда как человек алгоритмизирующий генерализацию вынужден сам решать где и как проводить компромисс. В результате постановщик ТЗ в голове будет иметь одно а главный разработчик совсем другое
Так шта пока Zkir не напишет ОЧЕНЬ чёткое ТЗ на задачу он не получит приемлимого для себя результаты. И будет на всех форумах писать что нет у нас нормальных программистов
Это вы сейчас описали “водопадную” модель разработки, которая была признана некошерной ещё десятки лет назад. С тех пор много воды в этих “водопадах” утекло, так сейчас никто в здравом уме не делает. Последовательные итерации и обратная связь - вот ключ к успеху.
Так я говорю что в конечном счёте (с какой-то итерации) код допиливать придётся Zkir 
Ага, щазззз, видимо ПО для сегодняшнего “Фобос-Грунт” как раз по agile-модели писали - “не долетит - в следующей итерации ещё один запустим”…
Задача генерализации дорожного графа хорошо формализуется и описана в этой теме уже раза три-четыре.
Могу еще раз:
- Выбрать из базы дороги определенного уровня (по значению тега highway), и соответствующие им развязки (xxx_link) и запреты поворотов, остальные выкинуть. (это исходный граф). Например, взять secondary и выше, а tertiary и ниже - выкинуть.
- Двухвейки переделать в одновейки, развязки (xxx_link) стянуть в точки. Расставить запреты, для сохранения эквивалентности рутинга с исходным графом.
- Упростить геометрию получившихся дорог, сократив количество промежуточных точек, до требуемой величины. Точки перекрестков, при этом, естественно, не выкидываются. Это конечный граф.
- Вот, собственно, и все.
Задачу генерализации геометрии, или отрисовки обзорной карты вообще из данных осм описывать бесполезно, нужно посмотреть на мапник уровня z1-z8 и на традиционные бумажные карты соответствующих масштабов.
Если имеются ввиду ID объектов в осм, то нет.
Смысл agile-модели как раз в том и состоит, чтобы у заказчика и разработчика как можно быстрее появлялся общий предмет для обсуждения, а не в конце двухлетнего цикла кодирования. И что должен (должен был?) делать “фобос-грунт” как раз кристально понятно - долететь до фобоса, взять пробу грунта, и доставить ее обратно на землю. C генерализацией немного сложнее
Мне кажется это лишним, т. к. трудно представить себе маршрут из одного города в другой по одной дороге, а обратно по совершенно другой. И на любой развязке будут возможны все варианты направлений несмотря на возможные отклонения в радиусе пары км.
ЗЫ. Или тут имеется в виду не ограничения поворотов, а вообще все, включая скорость и максимальную нагрузку на ось?
Да нет, это как раз “водопад”, когда результат проверяют уже на продакшене.
ОК. Насколько я понимаю, генерализация должна быть ограничена размером какого-то выходного файла или каким-то ещё физическим параметром (число точек?)
Тогда вопрос - а все ли дороги равны? Требуется ли одно и тоже число точек для трассы Чита - Улан-Удэ или для трассы Москва - Владимир? Может точность карты Чита - Улан-Удэ не настолько важна так как содержит мало ответляющихся дорого?
Другой вопрос - генерализация должна сохранять форму трассы? Более-менее ровная трасса может состоять из отрезков в несколько километров тогда как петляющая дорога (горы, река) требует аппроксимации … Есть какие-либо требования по сохранению геометрии? Не получим ли мы фактическую кольцевую квадратной?
Двухвейность нужна? Скажем питерский КАД двухвейный - есть разделитель между встречными потоками. Двухвейность очевидно увеличивает размер файла на фактически даёт мало информации …
Развязки нужны? Если да, то на них генерализация должна быть минимальной, не одна точка в километр. А то можно получить редкостные пёрлы
Это просто несколько вопросов на вскидку. Я думаю у того кто будет писать программу возникнут ещё вопросы …
Конечно, должна!
Маста пересечений и примыканий дорог, участвующих в генерализации, вообще должны быть прибиты строго по месту, а точки между ними должны быть пофильтрованы таким образом, чтобы отклонение генерализованной дороги от исходной не превышало какого-то порога, например, 5 %. Вроде даже математический аппарат на эту тему довольно хорошо развит и алгоритмы существуют.