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

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

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

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

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

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

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

Ответ 1

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

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

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

Дорожные сети, как правило, являются высокоинтеллектуальными, и обычный A * является медленным стартером. Когда вы путешествуете из одного города в другой, A * будет тратить чрезмерное количество времени, ползая по старому городу. Тем не менее, мы, люди, лучше всего используем автомобильные дороги, путешествуя на большие расстояния. Это то, для чего они созданы. PND также предпочитают автострады. И поскольку шоссе намного реже, это экономит много памяти.

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

Ответ 2

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

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

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

Ответ 3

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

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

Ответ 6

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

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

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

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

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

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

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