Возможно, разработчики уже и сами пришли к похожим выводам, возможно это уже здесь обсуждалось. Даже если так, от разжеванного повтора хуже никому не будет.
Речь пойдет о правиле “в середине маршрута не дожно быть понижений класса участков дороги” или же “в маршруте меж двух участков дороги одного класса не должно быть участков более низкого класса”, а именно, его недостатке.
В качестве примера использую недавно пройденный мною маршрут по OsmAnd с, насколько я понимаю, реализацией построения маршрутов используя указанное правило. Скрины приведу ссылками, дабы не пугать их размерами. Верхушку osmarender зачем-то оттяпал, ну и шут с ней, там неразрывный транк проходит.
Итак, необходимо проехать из пункта А (левый нижний угол) в пункт В (правый верхний угол).
скрин 1
На скрине мы наблюдаем обрезанную сеть дорог из транков, секодари и тертиари (верхний правый угол). Праймари не попали, т.к. они либо перекрыты транками, либо бесполезны для данного маршрута, как врочем и многие не нужные для данного маршрута секодари, не говоря уже о тертиари.
Для данного маршрута наиболее оптимальны следующие 2 в порядке убывания релевантности (на скринах синенькие):
скрин 2
скрин 3
Как видно, эти маршруты проходят по 2-м, 3-м отдельным кускам транков. Вообще, для следования из А в В (или наоборот) как маршрут не строй, а на разделенный куски транков попадешь.
В следствии этого, придерживаясь упомянутого правила не разрывности, OsmAnd предлагает мне следующий маршрут (опять таки синенький):
скрин 4
Этот маршрут составляет 258 км, против 211 км со скрина 3 и 193 км от скрина 1, т.е. на 33% длиннее наикратчайшего и удобнейшего маршрута. А это 3 с четвертью часа езды вместо 2,5 часа.
Почему так происходит? Ведь, логика в этом правиле, вроде как, есть. Не спроста же классификация дорог основывается на правиле не разрывности дорожного графа и эту информацию, по логике, можно использовать и в построении маршрутов.
Возможно, что-то не так в классификации дорог приведенного примера? Нет, поверьте, я этим маршрутом 15 лет пользуюсь, указанные секондари на праймари никак не тянут и согласовываются с официальной классификацией, которые тоже не дураки составляли. Иный путей нет. От транков тоже никуда не дется. Имеем разницу в 2 класса. Да даже если транки понизить, опять имеем дыры, только уже не в транках, а в праймари.
Так что с этим правилом не так? А то, что в нем отсутсвует важное определение и связь неразрывности с этим определением. А именно, “область класса”.
Под “областью класса” понимается некая область и соответсвующий ей класс дорог, при транзитном маршруте через которую (область) по более чем одному учатску дороги данного класса, между ними на пути маршрута отсутсвуют участки дорог более низкого класса. Обратите внимание, на условие “отсутсвуют участки дорог более низкого класса”. Более высокий класс дорог вообще в определение не попадает, они могут прыгать как хотят. Главное, что бы не было ни одного кусочка более низкого класса. Более высокие классы в рамках транзита через данную область вообще можно приравнивать к классу области.
Примеры:
• Страна, в большенстве случаев, имеет класс транк, ибо он гарантирует, что попадании на транк можно спокойно по транку пересечь страну в нужном направлении.
• Населенный пункт, опять таки, в большенстве случаев, имеет класс тертиари.
Что касается иных классов дорог, они достаточно индивидуальны для каждой страны, впрочем, именно поэтому выше имеется приписка “в большенстве случаев”, т.к. не исключено, что в некоторых странах эти пункты также отличны.
Итого, правило неразрывности дорожной цепи для построения рутинга преобретает вид:
При сквозном проезде через область класса n и построении маршрута по участкам дороги соответсвующего (и выше) ей класса, на всем протяжении маршрута через эту область между каждым участком дороги данного класса отсутвуют участки дорог более низкого класса.
В этом определении появляется еще одно условие, “и построении маршрута по участкам дороги соответсвующего (и выше) ей класса”, оно здесь затем, что оптимальный маршрут может и не выходить на дороги этих классов, а пройти через эту область “бочком”. Однако, если выехали на такой участок, то на следующий участок дороги этих классов можно попасть только по дорогам этого и выше классов.
Стоит также заострить внимание на том, что данная неразрывность действительна только внутри конретной области. Проходя через несколько областей одного класса вполне справедлив маршрут с разрывами в классе между областями и отсутвием классовых дорог в маршруте через одну и более областей (укловое попадание в область/и).
Соответсвенно, для построения маршрута с учетом данного правила применяется следующий алгоритм:
Нахидятся области наибольшего класса n между пунктами А и В. Транзит через эти области стоится с учетом данного правила. За пределами этой области ишутся области класса n-1 и т.д.
Очевидно, что для реализации подобного в реальном рутинге нужны не просто адекватные простановки классов на карте но и четкое представление об областях классов для разных регионов карты. Что достаточно трудоемко. Да и алгоритм выходит не такой уж тривиальный, как представлялся ранее.
С учетом того, что в классификациях у нас порой бардак, а с определениями областей классов вообще глухо (в своей-то стране не понятно что к чему, что уж о соседних говорить…), забейте вы на эту неразрывность до лучших времен…
Хотя при всей казалось бы сложности, эти правила действительно могли бы хорошо ускорить рутинг, хотя, для лучшего эффекта нужно бы хранить генерализации графоф областей с выкидыванием рваных кусков дорог более низкого класса (оставляя смежные с другими областями) и для транзита через область использовать их.
Фух, теперь можете пинать…
