CD-ROM используется для хранения картографической и дорожной информации с целью сравнения конфигураций дорог и пройденного пути, поиска оптимального маршрута, вывода карты местности на дисплей. Значительная емкость CD (до 600 Мб) позволяет это делать.
Картографическая информация или электронные карты существуют в двух основных форматах: матричном и векторном.
В матричном формате каждому элементу карты (пикселю) соответствуют свои значения декартовых координат X—Y. Матричные карты требуют много места в памяти компьютера или на носителе информации и неудобны для математических операций при прокладке и слежении за маршрутом.
В векторном формате дороги, улицы представляются последовательностями отрезков прямых, описанных аналитически, пересечения — узлами (рис. 5.21). Узлы идентифицируют координатами — долготой и широтой. Если дорога (улица) не прямая, в точке излома также помещается узел. Таким образом, дороги (улицы) любой конфигурации аппроксимируются набором векторов и узлов.
Рис. 5.21. Улицы и узлы на векторной карте
Имеющиеся карты или изображения местности, полученные с самолетов и спутников, сканируются. Затем специальное программное обеспечение трансформирует изображение сначала в матричный, а затем в векторный формат.
Электронная карта несет такую информацию, как номера дорог, названия улиц, номера домов между перекрестками, одностороннее или двухстороннее движение на улице, названия отелей, ресторанов и т.д.
Ориентирование на карте местности по конфигурации пройденного пути
Этот метод позволяет определить или уточнить текущие координаты автомобиля сравнением конфигурации пройденного пути (его участка), полученного навигационным счислением с конфигурацией дороги, по которой движется автомобиль. На рис. 5.22 показано, как сравниваются и корректируются пути, полученные навигационным счислением с картой.
Рис. 5.22. Корректировка пути
Сначала навигационная система определяет, какие из близлежащих дорог могут соответствовать координатам автомобиля, определенным навигационным счислением. Затем делается сравнение, как показано на рис. 5.22. Выбирается наиболее подходящая дорога и корректируются координаты автомобиля по карте. Когда автомобиль достигает перекрестка, выбор дороги определяется направлением движения (рис. 5.23). Если дороги на перекрестке выглядят примерно одинаково, как на рис. 5.23, навигационный компьютер прослеживает их по карте вперед и определяет коэффициент корреляции для каждой из дорог по отношению к требуемому маршруту. Выбирается дорога с наибольшим коэффициентом корреляции.
Рис. 5.23. Выбор пути на пересечении дорог
Выбор оптимального маршрута
Кроме определения текущих координат автомобиля, навигационная система также может выдавать информацию, облегчающую выбор оптимального пути следования к месту назначения. Для этого навигационный компьютер рассматривает дорожную сеть между исходным пунктом и пунктом назначения и выбирает кратчайший маршрут. Примером метода определения кратчайшего пути по карте является алгоритм Дейкстра (Dijkstra algorithm).
В алгоритме Дейкстра производится определение всех пересечений дорог от стартовой точки и вычисляются кратчайшие пути до каждой точки пересечения. Например, если имеется дорожная сеть, как на рис. 5.24, а, поиск пересечений начнется от начальной точки А, как показано на рис. 5.24, б. Сначала будут рассмотрены пересечения В и С. Расстояния от точки А до каждого из пересечений указаны внутри кружочков. Затем рассматриваются пересечения Е и F, соединяющиеся с точкой С, для этих пересечений указано расстояние от стартовой точки А (рис. 5.24, б (2)). В-третьих, рассматриваются пересечения D и Е, соединенные с точкой В, на рис. 5.24, б (3) указаны расстояния от стартовой точки А до D и Е. При этом расстояние до точки Е указано через точку С, т. к. оно меньше, чем через D (было бы 8). Точка D связана с точкой Е, и маршрут через Е оказывается короче, это отражено на рис. 5.24, б (4). Кратчайшим путем до D оказывается маршрут A-C-E-D. Таким образом для дорожной сети можно определить кратчайший маршрут до любого из пересечений (жирные линии на рис. 5.24, б (6)).
Рис. 5.24. Алгоритм Дейкстра
Использование этого алгоритма позволяет определить кратчайший маршрут к месту назначения. Располагая современной навигационной системой, водитель может не опасаться сбиться с пути.
Навигационная информация сообщается водителю различными способами: от указания символом положения на карте местности до команд голосом через синтезатор речи о необходимости повернуть налево или направо.