Map-Navigation Project, Как обычно хранятся/представлены данные о дорогах?

Question

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

Это две части вопроса:

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

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

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

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

Answer 1

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

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

В несколько иной подход к хранению, проверить OpenStreetMap

Answer 2

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

Учитывая довольно настойчив замечание Zich ниже этого

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

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

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

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

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

Answer 3

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

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

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

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

Answer 4

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

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

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

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

Надежда, что помогает ...

Answer 5

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

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

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

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

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

Answer 6

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

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

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