Вот чего не требуется, так как раз этого
Все известные науке практические рутеры умеют опускать перпендикуляр на рутинговое ребро.
Какая-то лажа в районе Расторгуевского шоссе.
http://www.openstreetmap.org/?lat=55.5504&lon=37.6101&zoom=13&layers=M
Всё верно, именно это происходит в момент компиляции карты. А промежуточный формат - полиш - может оставаться любой извилистости.
Я не писал все эти “известные науке роутеры”, но предполагаю, что что задача построения маршрута разбивается ими на ряд подзадач (для простоты - только для “дальних” маршрутов, где, собственно, только и нужен генерализованный граф):
- Нахождение ближайших вершин генерализованного роутингового графа к начальной и конечной точкам.
- Нахождение пути между найденными вершинами.
- Нахождение точки, в которой граница локального (полного) подграфа пересекается с найденным маршрутом.
- Нахождение кратчайшего пути по локальному (полному) подграфу между начальной/конечной точкой и точкой, найденной в п.3.
Таким образом, мы сейчас рассматриваем этап 2, в котором “опускание перпендикуляра” не предусмотрено.
А нахождение ближайшей точки локального роутингово подграфа - это часть этапа 4, который производится не по генерализованному, а по полному графу ограниченного фрагмента местности (который содержит все дороги).
Здесь есть еще один интересный момент: генерализованный граф находится в ОП постоянно (и не изменяется), а локальные полные графы - подгружаются по мере необходимости (в частности, в процессе ведения по маршруту), поэтому внесение изменения в локальный граф - включение в него “стартовой” точки, вероятно, с разбиением одного ребра на два (куда опускается перпендикуляр) и добавлением дополнительного ребра (тот самый перпендикуляр) не нарушает целостности данных. Т.к. эти данные при следующем использовании все равно будут переподгружены с диска.
Поэтому этапы 2 и 4 могут быть осуществлены одним и тем же алгоритмом - поиском пути исключительно между вершинами.
Всё по исходным данным RU-OVRV.mp, которые от 3 октября.
- 30094742 до 4 октября было tertiary и в выгрузку не вошло.
- Расторгуевское шоссе до 5 ноября было primary_link и схлопнуто.
**OverQuantum, **
Хорошо, я понял)
Я посмотрел те места которые знаю, получилось очень прилично. Даже не знаю к чему еще придраться. 
Есть белые вершины (которые в конечной карте не нужны), но это похоже опять к исходным данным.
Принципиальный вопрос. Можно сделать, чтобы алгоритм оставлял номера трасс [Е95], [M8]?
Чтобы результат работы алгоритма мог быть использован вместо RU-OVRV.mp для обзорной карты РФ, номера трасс крайне желательны.
Либо тип дорог разный с разных сторон белых вершин, либо скоростной класс разный.
Можно, в том числе весь Label сохранять.
Основной вопрос - что делать, если объединяются дороги с разными названиями?
Вот на скриншотах - Проектируемый проезд N 552 переходит в Новобутовскую улицу.
Не объединять - не здорово, есть подозрение, что много чего не объединится из-за мелких различий в написании, даже если только номера трасс.
Например, около Нижнего есть отрезки “E22,M7,М7”, а есть “E22,M7” и “E22”.
Выбирать название мажоритарно по количеству отрезков - пойдёт?
Окей)
Супер. Названия улиц попали в Label скорее по недосмотру, они в обзорной карте не нужны. А вот номера дорог, ака ref=* нужны)
Хотелось бы увидеть два варианта - а) мажоритарный выбор б) суммирование. “E22,M7,М7”+ “E22,M7” + “E22” = “E22,M7,М7”.
Этот разговор для меня слишком абстрактный)
Скажу только, что обычно путь ищется не между вершинами*), а между точками лежащими на ребрах, причем в произвольных местах.
*) Под “вершиной графа” обычно понимается перекресток, тупик, или соединение двух дорог – на скриншотах выше вершины отмечены разноцветными квадратиками.
Насколько мне известно, путь ищется только между вершинами. А если обязательно нужно найти путь до чего-то еще, то это что-то превращается в вершину.
Просто потому, что никаких точек в графе нет вообще, поэтому и лежать на ребрах они никак не могут. Вес ребра - это лишь “цена” перехода из одной вершины в другую, для которой, а само название “ребро” - не совсем точная геометрическая интерпретация сущности, которую нельзя разделить на части.
Например, нельзя купить 2/3 билет в кино. Точно так же нельзя и отложить 2/3 длины ребра. Но можно одно ребро разбить на два, вставив между ними дополнительную вершину.
Мажоритарный вариант всю МКАД превращает в Е22
Комбинаторный вариант всю МКАД превращает в E30,E105,E22
Сиё вызвано тем, что двухвейка схлопывается в одновейку вся целиком за один раз (да, вся МКАД за 1 раз) и скоростной класс и название считается 1 раз по всем исходным отрезкам и выставляется всем отрезкам итоговой одновейки.
Можно попробовать схлопывать по-отрезочно, но как раз циклические дороги представляют порядочную проблему для по-отрезочного анализа.
UPD: Файлы удалены в пользу след. поста.
Zkir,
Сделал схлопывание с более корректным сохранением названия.
Мажоритарный вариант, комбинаторный вариант.
Разница мизерная, в комбинаторном нашёл только сегмент “Р108,P107”. Я бы оставил комбинаторный.
Если устраивает, то у меня вопросы по финализации задачи
-
Небольшая часть процедур работает в lat/lon координатах и их переклинит на границе lon=180/-180 и у полюсов.
(рассчёт центроида развязки, перебор точек по bbox-у, проэцирование точки на линию и т.п.)
Насколько я вижу, сейчас объекты 180/-180 не пересекают, так что особой надобности сделать весь алгоритм устойчивым к границе 180/-180 не требуется.
Большая же часть работает через расстояние по сфере WGS84 и проблем испытывать не будет. -
Устроит ли лицензия GPL v3?
-
Устроит ли реализация на C или C++?
Perl я почти не умею, Java сильно не люблю.
Сейчас всё на скрипте. На C/C++ могу переписать сам. Уточните только - лучше чистый C или можно наворачивать объектные конструкты С++.
Да, комбинаторный вариант мне нравится больше. К чему придраться я не знаю, так что устраивает
- Наверно это не важно. На крайняк можно будет отрезать)
- Да, вполне.
- А что за скрипт? Он под виндой работает?
И вот еще что. Совсем об этом забыл, но оно важно. Можно сделать описание алгоритма на человеческом языке?
VB6 
Атлична работает под виндой, особенно если собрать в exe-шник. Из исходников - только в интерпретаторе.
Объёмом до 1 страницы - могу написать. Детальнее - нужно будет расписывать подробности алгоритмической реализации, не вижу особого смысла делать это в отдельном тексте, т.к. в исходниках будут довольно подробные комментарии на функции (но на английском).
…
Хорошо вовремя спросил. Если VB6 (не VBScript) то и переписывать никуда (особливо на С++) не надо.
Приму как есть)
Годится.
Супер.
VB6, не VBScript.
Э… ладно.
Просто код несколько наколеночный, экспериментальный - для проверки идей и работоспособности алгоритмов. Данные лежат в глобальных массивах, goto местами насыпано и т.п.
Ещё я посмотрю, можно ли на код VB6 вешать GPL v3.
Жаль.
Ваш бы код да в виде плугина к osmosis…
Я готов отдать весь приз за эту задачу тому кто перепишет код на Java
Добрый ты - “Данные лежат в глобальных массивах, goto местами насыпано и т.п.”