Навигационные карты. Информация, обсуждение (кому какие нужны, больше нравятся)

[Vinil_37]

Так кто же рулит и педалит? Навител или Навилюкс?

В данном контексте Навител - производитель навигационной программы имеющей свой собсвенный формат карт, а Навилюкс (так же как и Аэроскан) - производитель карт, в формате не совместимом с вышеупомянутым Навителом.

 

[Luckyland]

а трудно догадаться что платформы разные???

Да, для неспециалиста вроде меня - весьма затруднительно.

В данном контексте Навител - производитель навигационной программы имеющей свой собсвенный формат карт, а Навилюкс (так же как и Аэроскан) - производитель карт, в формате не совместимом с вышеупомянутым Навителом.

Спасибо.

 

[Дмитрий Засядько]

А можно вопрос немножко не по теме:
Я знаю, что дороги на векторных картах представлены в виде графов. Вроде при поверхностном взгляде всё понятно: участки дорог представлены в виде рёбер, перекрёстки - вершинами.
Для поиска маршрутов есть алгоритм Дейкстры, Флойда-Уоршолла и др.
Но эти алгоритмы, насколько я знаю, никак не учитывают задержки на перекрёстках, особенности левых-правых поворотов, запрет поворотов и т.д. А это очень важно при прокладке маршрута.

А как в навигационных программах и картах моделируются перекрёстки и развязки?
Наверняка ведь не просто в виде вершины!
Наверное, каждое возможное направление движения на перекрёстке представляется в виде маленького ребра графа?

 

[login123]

В чистом виде алгоритмы Дейкстры и прочих классиков комбинаторики для прокладки маршрутов неприменимы (большая размерность реальной дорожной сети, отсюда нереальное время поиска маршрута). Реальные реализации чаще основаны на модификациях алгоритмов A* (A-star, если погуглить, можно найти).
Весовые коэффициенты участков дорог, используемые для расчета "стоимости" маршрута включают обычно длину участка, категорию дороги (с учетом ширины и покрытия), допустимую скорость.
Естественная структура данных для дорожного направленного графа - список. Записи списка -ребра графа (участки дорог), связи/ссылки между записями - маневры переезда с одного участка дороги на другой. Соответственно для учета задержек на поворотах не проблема приписать каждой связи/ссылке весовой коэффициент с учетом взаимного направления ребер (правый/левый поворот).
Т.е. теоретически вроде не проблема. Но практически какие коэффициенты ставить? Перекресток перекрестку рознь, с том числе в разное время суток.
Если не ошибаюсь, только директор ФБР Гувер радикально решил эту проблему. Ему маршруты всегда прокладывали так, чтобы не было ни одного левого поворота
На практике в Навител задержки на поворотах при прокладке маршрутов не учитываются. В СитиГид алгоритмы прокладки более продвинутые, прокладка и перепрокладка быстрее, задержки на поворотах учитываются, даже можно учитывать запреты проезда/поворотов, действующие по времени суток или дням недели. Кстати, в обновлении карты Киева для СитиГид от travelgps, которое вчера официально выложено на сайте СитиГид probki.net , уже работают некоторые запреты по времени.
Вообще, обеспечить в карте разумную прокладку маршрутов для разного ПО (разных алгоритмов прокладки) задача еще та. Иногда и для одной программы неудачное изменение приоритета одного участка второстепенной дороги порождает кучу кривых маршрутов между главными улицами.

 

[Дмитрий Засядько]

login123 Спасибо. Ушёл гуглить
Насчёт списков - когда я писал диплом и понадобилось сделать программку для него, я граф описывал в виде двумерного массива rebro(i,j). Это, конечно было дико нерационально, потому что большинство ячеек массива просто пустовали и зря жрали память, но по другому написать у меня мозгов не хватило . Ибо я не программер. А понятие списков я так и не освоил

 

[login123]

Дмитрий, конечно с матрицей смежности проще работать, но по использованию памяти она эфффективна, если заполнена хотя бы на четверть.
По алгоритмам маршрутов, если интересно, вот ссылка на Andrew V. Goldberg

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Он достаточно серьезно занимался исследованием и улучшением алгоритмов A-star

 

[Дмитрий Засядько]

Насчёт алгоритмов А* нашёл очень доходчивое описание

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Надеюсь, оно правильное
Ну, суть я вроде понял. Очень похоже на метод потенциалов. Только в отличие от него, к потенциалу каждой вершины прибавлена эвристическая оценка расстояния от вершин графа до конечной точки. И ещё метод потенциалов вроде бы предполагает обязательное прохождение всего графа, а не просто добраться до целевой точки и успокоиться.

Ну ладно, в принципе для моей задачи сойдёт и так. Там город представлен укрупнённо.
А вот с перекрёстками ещё надо разобраться...



Насколько я понял, перекрёсток можно представить не в виде вершины графа, а как совокупность вершин. А возможные манёвры на перекрёстке показать рёбрами. Если манёвр запрещён - просто вырезаем соответствующее ребро. Если манёвр затруднён - ребро прибавляет в весе.

Вот и получится, что если рёбрам, которые представляют левые повороты, добавить веса, то маршрут будет прокладываться более правильно.

 

[dorya]

Пример за вчера,с пр.Правды 10А(Якитория),на 17Партсьезда проложил как и обычно через Одесскую
То бишь Сумская,Рымарская,далее круг Гагарина,Гагарина,Сталинграда и т.д.

Естесно я повернул налево с Правды на Сумскую и поехал до Веснина,далее через Киевскую,на Ак.Павлова и с него на Московский проспект
И ближе и удобней

на счет удобнее, ну может быть.
Но зачем ехать на Веснина с Якитории, если тебе надо на ХТЗ? явно не ближе будет и навигатор не нужен

кстати, а то, что по Сумской вниз от Оперного уже давно можно ехать, это таки да, Навител об этом не знает и ведет по Рымарской

 

[АНАРХИСТ]

на счет удобнее, ну может быть.
Но зачем ехать на Веснина с Якитории, если тебе надо на ХТЗ? явно не ближе будет и навигатор не нужен

Ну расскажи как бы ты ехал с пр.Правды на ХТЗ?
Внимательно жду

 

[dorya]

ну как минимум в сторону Горбатого моста ехать, а там по обстановке

 

[АНАРХИСТ]

ну как минимум в сторону Горбатого моста ехать, а там по обстановке

Можно спросить,а зачем?
Дружище,ты абы по...ть зашел или правда маршрутами интересуешся?
Что значит по обстановке?
Ты проложи полный маршрут до ХТЗ,если не ехать по Веснина

 

[dorya]

Можно спросить,а зачем?
Дружище,ты абы по...ть зашел или правда маршрутами интересуешся?
Что значит по обстановке?
Ты проложи полный маршрут до ХТЗ,если не ехать по Веснина

я не интересуюсь, я по ним езжу, при этом не кричу по форуму, что лучше всех знаю Харьков.
По обстановке имелось ввиду, что нужно учитывать день недели и время суток.
Ты же спрашиваешь почему Навител ведет через Одесскую, а сам едешь с Якитиории на Веснина, где логика?
Если ты работаешь в такси, ты должен знать с кокого района центра ближе ехать через Веснина, а с какого ближе через Горбатый мост, или Исторический.
И вообще данный спор здесь оффтоп

 

[АНАРХИСТ]

я не интересуюсь, я по ним езжу, при этом не кричу по форуму, что лучше всех знаю Харьков.
По обстановке имелось ввиду, что нужно учитывать день недели и время суток.
Ты же спрашиваешь почему Навител ведет через Одесскую, а сам едешь с Якитиории на Веснина, где логика?
Если ты работаешь в такси, ты должен знать с кокого района центра ближе ехать через Веснина, а с какого ближе через Горбатый мост, или Исторический.
И вообще данный спор здесь оффтоп

Мдя,все с тобой в принципе ясно,досвидания как гритсо,пешите исчо
Подождем ответа более компетентного чилавега

 

[dorya]

Ну "до свидания" в этой ветке, не тебе мне говорить, молодой человек, это раз, во-вторых, я не хочу, чтобы ТС потерял к этой теме интерес, т.к. результат своих постов я вижу у себя в навигаторе, в то время, когда ты говорил, что "жипиресы" тебе не нужны и круче бумажной карты ничего нет. А так же вижу то, что любая тема, где ты появляешся, превращается во флудильню. У тебя есть автоветка, где, когда-то на тебя внимание обращали, там и пиши, а здесь или по делу, или наблюдай со стороны.
Еще раз извенения у ТС.

 

[login123]

Дмитрий, с моделью перекрестков вроде так, но выглядит сложновато. Если хотите задачу максимально свести к какой-то классике на взвешенном ориентированном графе, можно нарисовать более прозрачную модель. Обычно полезно становиться с ног на голову, т.е. пробовать вывернуть первичную модель наизнанку. Если хотите через матрицу смежности, просто нарисуйте не матрицу смежности перекрестков, а матрицу смежности участков дорог. Думаю понятно, о чем я. Вобщем то, что вы и пытаетесь рисовать, но будет более прозрачно. Размерность естественно взбухнет, но матрица будет слабозаполненная. Можно использовать очевидные способы ее редуцирования. Например, транзитивное замыкание для цепочек без ветвлений. Я имею в виду, что в реальном дорожном графе есть немало цепочек из десятков и сотен сегментов (ребер) без ответвлений. Такие цепочки можно заменить одним ребром с суммарным весом. Характерный пример - бетонка Р-51, на которой всего нескольно развязок, и нет никаких других пересечений.
----
Господа водители, ответы на вопросы по прокладке маршрутов, обозначенные вами здесь, смотрите в профильной теме https://www.kharkovforum.com/showthread.php?t=1008671&page=5
----------
VF

 

[Дмитрий Засядько]

VF
Спасибо. Буду думать дальше.
Я ведь не профи-программер. Мне было удобно представить в Паскале граф как двумерный массив rebro(i,j) из чисел, равных весу ребра, если это ребро существует, или бесконечности, если ребра нет.



Вчера посмотрел карту Украины от Аэроскан (от 27.10.2010).
Покрытие вроде больше, чему Люксены (по крайней мере, размер файла больше )
Но расцветка в дневном варианте осталась ужасной. Названия POI "замазаны" чёрным. В ночном варианте нормально.
По Харькову старые ошибки до сих пор не исправили. По крайней мере, "дорога" от Верхнегиевской на Залютино присутствует (в реальности там овраг и трубы теплотрассы)

 

[bambinka]

подскажите кто-нибудь! где можно скачать карту Соединенных штатов,чтобы загнать ее в навигатор ТомТом?

 

[Дмитрий Засядько]

Дык, у томтома и скачайте! Всего 49,95 евро

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

Ещё можете почитать про карты ТомТом на форуме

⚠ Тільки зареєстровані користувачі бачать весь контент та не бачать рекламу.

(придётся зарегистрироваться. Бесплатно)

 

[bambinka]

Дык, у томтома и скачайте! Всего 49,95 евро

Ещё можете почитать про карты ТомТом на форуме
(придётся зарегистрироваться. Бесплатно)

за 50 евро не хочеться хочеться бесплатно
спасибо за ссылку,поищу еще там может



люди добрые а есть может кто-то кто может закинуть карту соед.штатов в навигатор ТомТом?и сколько это будет стоить?

 

[Дмитрий Засядько]

А какая модель ТомТома?
Вообще-то у нас томтомы не прижились. Ибо карты Украины у них плохие.