Как интересно. Посмотреть подробно смогу в выходные)
Это надо в осм поправить)
Кстати, реквестирую валидатор, который показывает hw=*_link длиной, скажем, более полукилометра.
Есть вполне нормальные эстакады длиной около 2 км.
А вообще могу прикрутить в мою прогу выгружалку линков длиной более X км. Для Дуглас-Пеккера и сохранения в .mp всё равно ищутся связанные цепочки отрезков одного класса.
Я бы сервисы по длине контролировал.
Уже пару лет как за этим наблюдаю и пришел к выводу, что пятикилометровый service - скорее всего ошибочно замапленный unclassified, а уж десятикилометровый - точно баг.
Хотя по гаражам можно постараться накрутить змейкой 
Ну и по карьерам и промыслам.
Честно говоря, уже не первый раз читаю о применении Дугласа-Пекера к задаче генерализации дорожного графа.
Может кто-нибудь объяснить, зачем он в принципе там нужен?
- Генерализация графа предполагает упрощение сложной геометрии до простой
При объединении 2-х веек в одну линий, сохраняется каждая точка исходных 2-х веек.
В итоге, например, прямой Панфиловский проспект в Зеленограде длиной 3км (самый длинный сегмент между развязками) получается из 60 отрезков. Нафига они нам нужны в дорожном графе на всю страну? Если дорога прямая как линия, её можно задать двумя точками, т.е. 1 отрезком. - Алгоритм схлопывания развязок использует последние отрезки дорог, подходящие к развязке, для вычисления координат точки, куда схлопнуть развязку. Если отрезков будет много и они будут короткие, точность вычисления упадёт, т.к. короткий отрезок не всегда совпадает по направлению с общим направлением дороги.
- Чем меньше отрезков, тем быстрее работают алгоритмы, которым нужно перебирать все отрезки.
Сейчас Дуглас-Пекер у меня применяется 3 раза, все 3 раза эпсилон = 5 метров, т.е. оптимизируются только очень прямые фрагменты.
Вообще говоря, если даже дорога извилистая как кишечник парнокопытного, то с точки зрения дорожного графа ее следует также представлять двумя точками: начальной и конечной, а также длиной (в теории графов называемой весом ), которая, понятное дело, для извилистой дороги не будет совпадать с расстоянием между этими точками.
Вполне допускаю, что алгоритм преобразования графа может требовать азимутальных углов вхождения дорог в развязку. Естественно, это временная информация, которая впоследствии должна быть удалена, т.к. для построения маршрута она не нужна.
Ну так это понятно.
Проблема-то в том, что все точки, которые не являются узловыми, могут (и должны!) быть полностью удалены безо всяких Дугласов, а узловые - и Дугласам удалять не позволительно.
Или я чего-то не понимаю?
Зачем нам между узлами еще какие-то точки?
- Я уже писал выше.
- Я не вижу в mp формате веса, который не равен длине ребра графа. Соотв. есть подозрение, что роутинг в mp файле считается по длине, а значит для "кишечник"ов роутинг будет считаться неправильно.
Если будет не нужно повторение геометрии исходных дорог, в последнем Дуглас-Пекере поставите эпсилон = 1e8 и он вам всё упростит по самые узловые
Или при сохранении в .mp можно выбросить блок, который пишет промежуточные координаты.
Вот-вот, по промыслам или вдоль газопроводов может и больше накрутиться, однако ж это сервис.
На Самотлоре и в Татарии сервисы на месторождения на мой взгляд все короче 10 км.
А газопроводы - это “экзотика” . Можно выучить в лицо.
А сколько сервисов в деревни ведут? Ужос! Должны ведь unclassified!
Отнюдь.
Это все узловые точки, которые не подлежат удалению ни Дугласом-Пекером, ни чем-либо другим.
Они должны сохраниться в графе даже если лежат на идеальной прямой. Иначе до этих НП нельзя будет проложить маршрут в принципе.
Я тоже не вижу.
Это говорит лишь о том, что МР не подходит в качестве промежуточного формата.
Значит, надо менять формат.
Всего навсего.
Кстати, полностью отказываться от исходных данных все равно нельзя: после того, как маршрут построен, вступает в действие другая часть программы - которая ведет по маршруту.
И вот здесь реальные изгибы дороги просто необходимы.
Другое дело, что эта часть не должна ни фигурировать при прокладке маршрута, ни вообще присутствовать в оперативке в каких-либо существенных количествах - она подчитывается по необходимости из древовидной структуры на диске (или во внешней памати), но не занимает заметного места в ОП.
А дорожный граф для обеспечения приемлемых временных затрат должен размещаться в памяти полностью.
А зачем делать лишнюю работу?
Алгоритм хоть и имеет сложность O(n*log(n)) (а в худшем, кстати, O(n^2)), но содержит большое количество вычислений с плавающей точкой и не поддающихся предсказанию условных переходов.
ИМХО, узловые точки - это к которым подходит 1 или 3+ отрезков. В случае отсутствия secondary это условие не выполняется на всей дороге.
Никакие точки дорог в населённых пунктах никак не выделены, поэтому не могут быть определены алгоритмом как специальные, необходимые для сохранения.
За этим не ко мне, а к Zkir-у, он постановщик задачи.
Сохранение в .mp вычислений с плавающей не содержит 
P.S. В алгоритме был исправлен баг, актуальная генерализация страны теперь по новой ссылке.
При таком раскладе не могу не согласиться - категорически не подходит.
Есть вообще какие-то причины использовать промежуточный mp в конвертерах кроме исторических?
В данной задаче - польский формат входной и выходной. Промежуточный может быть каким угодно.
Эмн. Ну если на выходе mp, значит инфа о “весе” ребёр графа, отличная от длины, не будет сохранена.
Кроме длины есть ещё тип, который тоже часть веса.
Давайте попытаемся как-то связать принятую у нас (в ОСМ) терминологию с терминологией принятой в теории графов.
В графе есть вершины, соединяемые ребрами.
Задача стоит - найти кратчайший (либо близкий к кратчайшему - в зависимости от постановки) путь из одной вершины в другую. Т.е. путь, сумма весов ребер которого минимальна.
При этом если некоторая “точка” не является вершиной, то задача о нахождении “маршрута” до нее в принципе некорректна.
Количество ребер, приходящих в вершину, никакой роли не играет. Вершина - это то, что может являться началом, концом или промежуточной точкой маршрута.
Никаких других условий на вершину не накладывается.
Отсюда непосредственно следует, что должно являться вершиной, а что - нет.
см. выше.
Если требуется, чтобы в эту точку мог быть проложен маршрут, она должна быть вершиной графа.
Как их выделять - тема отдельного разговора, но они обязательно должны быть выделены.
Вероятно, начинать нужно как раз с точек, где расположены НП, дополняя их вершинами, получающимися в местах разветвления и пересечения магистралей.
Следует только помнить главное:
От правильного выбора вершин графа в значительной степени зависит результат работы.
Поэтому недооценивать этот этап не следует.
Насколько я понял, он тоже не постановщик (по крайней мере, не инициатор последнего “разбирательства”), хотя в его “задачах” это фигурировало.
Вероятно, задача в какой-то степени “модельная”, т.е. в данный момент служит для того, чтобы с чего-то начать и сформулировать более точное ТЗ на последующую работу.
На таком этапе вполне логично использовать именно стандартный формат (пока точно неизвестно, каким требованиям должен удовлетворять формат, который еще только предстоит разработать).
Кстати, на этом этапе можно также использовать “костыли” в виде дополнительного файла, привязанного к конкретному МР, который и содержит необходимую дополнительную информацию.
А когда будет достигнуто понимание, какую именно информацию следует хранить, можно ставить вопрос и о разработке подходящего формата (если возникнет такая потребность).
Естественно.
Я просто решил не раздувать сообщение многочисленными уточнениями.
Реально там должна быть информация достаточная для вычисления веса ребра, возможно, с учетом сезона, времени суток, типа объекта, для которого требуется проложить маршрут, наличия пробок и т.п.
Но это отдельная задача, до которой тоже рано или поздно должны дойти руки.
Хвататься же за все сразу, значит, ничего не довести до конца.
Давайте. При загрузке mp файла моей программой все node-ы из OSM становятся вершинами, а все сегменты way-ев (от n node до n+1 node) - рёбрами. При сохранении же цепочки ребёр от узла до узла (узел - вершина с 1 или 3+ ребёр) одного класса дорог и класса скорости сохраняются в одну ломаную линию. Дуглас-Пекер упрощает такие цепочки, чтобы в них было не очень много вершин, но и геометрия не сильно отличалась от исходной.
Точки НП не лежат на дорогах.
Я решаю задачу #8, как её сформулировал Zkir (про НП там ни слова нет). Сформулируйте вашу задачу от начала и до конца и тогда можно будет посмотреть, можно ли её решить заодно или её нужно решать совершенно иначе.
У нас несколько разные подходы.
Вы исходите из того, что у Вас есть определенные данные, и Вам нужно с ними что-то сделать. Что получится.
ЯЫ пытаюсь сначала понять, что должно быть в результата, и только потом обдумывать, какие для этого нужны данные.
А какова роль исходной геометрии в дорожном графе? Зачем ее нужно хотя бы приблизительно сохранять?
У нас есть задача - построить маршрут. Она не предусматривает, что должна быть вообще какая-то геометрия.
А это правильно?
Это соответствует той модели, по которой нам нужно строить маршрут?
Мне кажется - нет.
Значит, должны лежать.
Я сейчас обдумываю задачу построения маршрута в условиях максимально приближенным к “боевым”. Т.е. как должна работать программа, чтобы было не хуже тех, что сейчас используются в навигаторах.
Естественно, полной ясности нет. Есть только определенные идеи, как к этому подходить. Но, естественно, все это нужно проверять. Ну и просто обменяться мнениями.