Карта-навигационный проект, Как дорожные данные обычно хранятся / представляются?

Question

Навигационные системы, такие как Garmin и TomTom, всегда очаровывали меня. Я хотел реализовать небольшие картографические / навигационные приложения, чтобы опробовать различные алгоритмы маршрутизации и расширить свои знания о них.

Это вопрос из двух частей:

1.) Как хранятся данные карты? - Как обычно хранятся эти данные при наличии сети дорог? Какие части данных сохраняются для того, чтобы потом воспроизвести карту? Хранится ли каждая дорога в виде ряда точек, где она меняет направление? В каких форматах файлов хранятся эти данные? Существуют ли общедоступные библиотеки для простого анализа этих файлов? Кто-нибудь знает, как хранятся / отображаются данные карты / дороги, это было бы очень полезно.

2.) Навигация / Разметка - Правильно ли мое предположение о том, что при базовом прохождении по этим картографическим данным (а-ля Garmin) оно преобразуется в ориентированный граф? Является ли каждое пересечение дороги вершиной с краем, взвешивающим расстояние между вершинами? Это то, о чем я думал, поэтому я мог попробовать некоторые основные хорошо известные алгоритмы маршрутизации и посмотреть, что я получу.

Я видел эти общедоступные картографические данные по США, но я не уверен, как они представлены и достаточно ли они подробны для меня, чтобы я мог построить из них ориентированный граф .

Если у кого-то есть какая-либо информация, я был бы признателен. Чем детальнее знание, тем лучше.

Answer 1

Все предыдущие ответы относятся к системам ГИС. Это не то, как работают PND (портативные навигационные устройства). Они слишком просты для запуска ГИС-программ на уровне рабочего стола / рабочего места.

Вместо этого PND хранят информацию в значительной степени, как предполагал Симукал. Дороги разбиты на отрезки. Это делает модель намного проще. Внутри сегмента атрибуты, такие как максимальная скорость, не меняются.

Для целей планирования участки дороги выступают в качестве ребер на графике. Для каждого узла сохраняются оба входящих и исходящих узла. Затем планирование выполняется с использованием модифицированного алгоритма A *. Весовые коэффициенты, как правило, представляют собой не расстояния, а расчетное время в пути (или в случае TomTom с, фактическое измеренное время).

Дорожные сети, как правило, высокотехнологичны, и нормальный A * - медленный стартер. Путешествуя из одного города в другой, A * будет тратить слишком много времени на обход стартового города. Тем не менее, мы, люди, знаем, что лучше использовать автомагистрали при поездках на большие расстояния Вот для чего они созданы. ПНД также предпочитают шоссе. А поскольку автомагистрали намного реже, это экономит много памяти.

Еще одна оптимизация - поиск вперед и назад; Вы планируете с обеих сторон к некоторой средней точке. Большим преимуществом этого является то, что если вы делаете неправильный поворот, вы можете искать снова с новой начальной точки. Дерево поиска в обратном направлении не изменилось, поскольку пункт назначения не двигался.

Answer 2

Я не знаю подробностей о единицах навигационной системы, но в стандартном мире ГИС данные карты хранятся в основном как набор многоугольников, линий и точек, каждый из которых описывается своими координатами (а также используемой проекцией и некоторыми другими параметрами ). Например, один из наиболее распространенных форматов, шейп-файлы, описан здесь , , а стандарт формата базы данных - здесь .

Я успешно использовал эту модель хранения для отображения дорог и расчета маршрута, используя PostgreSQL , PostGIS и PGRouting . Расчеты выполняются с использованием обычных графовых алгоритмов, а данные, хранящиеся в общем формате, сохраняются также в виде графика, чтобы обеспечить их применение. Я не могу экстраполировать этот опыт на встроенное устройство, поскольку они, вероятно, делают это совсем по-другому, учитывая их ограниченную вычислительную мощность. Скорее всего, они рассчитывают много вещей.

Для несколько иного подхода к хранению, проверьте OpenStreetMap

Answer 3

Если вы хотите, чтобы какой-то код смотрел, чтобы получить представление о том, как работают приложения маршрутизации, попробуйте взглянуть на некоторые приложения маршрутизации, связанные с openstreetmap.org wiki . Navit и Gosmore имеют открытый исходный код и, в частности, довольно просты в настройке.

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

Если вы хотите взглянуть на Gosmore в действии, это серверная часть yournavigation.org веб-сайта маршрутизации, основанного на данных openstreetmap.

Answer 4

Точный способ хранения зависит от формата; Есть куча разных форматов ГИС. GDAL - отличная бесплатная библиотека для чтения (почти) всех из них.

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

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

Быстрое решение - это компромисс между предварительным вычислением и объемом памяти (встроенное устройство может потребовать другого выбора здесь для ПК). Для этого есть несколько очень интересных алгоритмов.

Answer 5

Мохаммед: Хорошо, я не стал вдаваться в подробности, потому что первоначальный вопрос казался довольно удобным в этом аспекте. Если вы не знакомы с теорией графов, возможно, стоит почитать ее сейчас - Википедия отлично подходит для ознакомления.

Как правило, в данных ГИС дороги хранятся в виде полилиний с прикрепленными метаданными. Это хорошо для отображения их на экране и т. Д., Но чтобы иметь возможность перемещаться по ним, вам нужно знать, какие из них связаны друг с другом. Таким образом, в метаданных обычно есть идентификатор узла для каждого конца дороги, так что вы можете сказать: «Это сегмент дороги 457, он идет от узла 332 к узлу 667». Поэтому, когда вы читаете данные ГИС, вы строите представление их в виде набора узлов, соединенных дугами (т. Е. Графика).

Если эти метаданные недоступны, вы можете сделать вывод, по каким дорогам одинаковые координаты начала / конца (это имеет место с некоторыми не столь замечательными данными ГИС). «Направленный» бит означает, что дороги имеют направление - некоторые из них можно перемещать в любом направлении, а другие только в одну сторону.

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

Надеюсь, это поможет ...

Answer 6

Для повышения скорости рисования за счет увеличения объема памяти и ограниченного разрешения многие приложения будут использовать растровый формат с географической привязкой, такой как GeoTiff .

Учитывая довольно настойчивый комментарий Зича ниже, что

"Данные представлены в векторе во всех навигационных системах без исключения!"

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

На самом простом уровне карта и компас - это навигационная система. Замените карту небольшим экраном, масштабируемой растровой картой и GPS, и у вас все еще есть навигационная система. Большинство морских и навигационных систем низкого и среднего уровня по-прежнему работают таким образом, с картами, представляющими береговую линию и морское дно, и GPS, чтобы определить ваше местоположение, и эхолотами для глубины.

На более продвинутом конце спектра автономные роботизированные навигационные системы, такие как Mars Rover , генерируют модели DTM на лету в качестве основы для навигации на короткие расстояния, а спутниковые матрицы высот собирают для большей дальности навигация.

Предполагать, что все навигационные системы работают как потребительские устройства Garmin или Tom Tom, - довольно наивное предположение. Кстати, многие современные устройства Garmin также включают растровые данные ЦМР , где низкое значение высоты GPS может быть крайне неточным.