Просмотр карты с масштабированием и элементами навигации

Магомедов Абдулкарим Магомедович доктор физико-математических наук профессор , кафедра дискретной математики и информатики, Дагестанский государственный университет 367000, Россия, Республика Дагестан, Махачкала, ул. Гаджиева, д. 43-а Magomedov Abdulkarim Magomedovich Doctor of Physics and Mathematics Professor, Department of Discrete Mathematics and Computer Science, Dagestan State University 367000, Russia, Dagestan, Makhachkala, ul. Gadzhieva, d. 43-a magomedtagir1@yandex.ru

Введение

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

Формулировка задачи

Рис. 1. Фрагмент карты РД с градусной сеткой.	Рис. 2. Фрагмент «канонической» карты РД.

Пусть выбран некоторый растр карты Республики Дагестан (далее – РД) с размерами 5100*3400;координаты верхнего-левого и правого-нижнего углов(назовем их точками «Краснодар-Севан» и «Базардюзю-Губа») равны соответственно 45⁰с.ш. (как, у г. Краснодар), 45⁰ в.д. (как, у севернойчасти озера Севан) и 41'13⁰ с.ш. (как, у горы Базардюзю), 48'50⁰ в.д. (как, у г. Губа), см. рис. 3.

Такая карта была первоначально взята в качестве исходной для программы компьютерного просмотра. С помощью простой утилиты в полуавтоматическом режиме оцифрованы все важные объекты карты: населенные пункты (более 1600), границы муниципальных районов, основные транспортные магистрали, реки, возвышенности, перевалы и т.п.; все координаты вычислены относительно системы координат с началом в точке «Краснодар-Севан». Для определенности, данную карту будем называть «канонической». Например, из фрагмента файла оцифровки rgn_names_coord (рис. 4) видно, что координаты населенного пункта Гергебиль по канонической карте равны x=1946 и y=3340.

Рассматриваются задачи:

а) просмотра любого растра с изображением карты РД привнесением в программу минимальных изменений (без дополнительных действий по оцифровке),

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

	2215 2745 Ленинкент 2014 2931 Буйнакск 1946 3340 Гергебиль 2739 4823 Микрах 2785 4835 Каладжух 2828 4761 Каракюре 2439 4944 Фий 2335 4907 Гдым
Рис. 3. Долгота г. Губа приблизительно равна долготе самой правой точки (суши) РД.	Рис. 4. В строке данные разделены пробелом.

Подходы к решению

Под правильной картой РД будем понимать прямоугольную область со сторонами, «параллельными» меридианам и параллелям, с противоположными углами «Краснодар-Севан» и «Базардюзю-Губа» по диагонали и соотношением сторон, как у канонической карты (в нашем случае k=3/2). Понятно, что последнее условие избыточно, оно служит для целей контроля возможных искажений карт, подготовленных склеиванием в том или ином графическом редакторе из множества фрагментов.

Для решения первой задачи внесем в код программы значение высоты канонической карты в качестве константы и переменную ScaleKoef, устанавливаемую в значение, равное отношению высоты правильной карты, выбранной при очередном запуске программы, к упомянутой константе; рассмотрим функцию ScaleToCan (z: integer), возвращающую округленную до целого значение произведения аргумента на ScaleKoef. Остается заменить всюду перед использованием координаты населенных пунктовx и y на ScaleKoef(x) и ScaleKoef(y). Аналогичный пересчет координат («масштабирование») выполним и для всех других исходных данных, в частности, - для точек каждой автомагистрали РД.

Пусть масштабирование выполнено. Для решения второй задачи рассматривается «подготовительный граф» с вершинами двух видов: временных – в последовательных точках, отмеченных вдоль каждой магистрали, и постоянных – в точках пересечений автомагистралей; ребрами служат отрезки, соединяющие соседние точек вдоль каждой магистрали. По подготовительному графу строится граф дорог: вдоль каждой магистрали вычисляются расстояния между соседними по магистрали постоянными вершинами и запоминаются в качестве весов постоянных ребер, соединяющих эти вершины; постоянные вершины и постоянные ребра составляют граф дорог (при этом для каждого постоянного ребра (a,b) сохраняется массив временных вершин, промежуточных для вершин a и b). Остается применить один из известных алгоритмов нахождения кратчайших путей в графе (например, алгоритм Дейкстры ^[1]); запомненные массивы временных промежуточных вершин служат для целей визуализации найденных кратчайших путей.