Рус Eng Cn Перевести страницу на:  
Please select your language to translate the article


You can just close the window to don't translate
Библиотека
ваш профиль

Вернуться к содержанию

Кибернетика и программирование
Правильная ссылка на статью:

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

Магомедов Абдулкарим Магомедович

доктор физико-математических наук

профессор , кафедра дискретной математики и информатики, Дагестанский государственный университет

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

DOI:

10.7256/2306-4196.2013.5.9696

Дата направления статьи в редакцию:

17-09-2013


Дата публикации:

1-10-2013


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


Ключевые слова:

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

Abstract: This article gives a schematic view of a map of the region, customizable for various scale images selected from the list of maps of the region. The article discusses two problems: the map zooming and computation of shortest paths. The author considers the following problems: viewing of any raster image maps with minimal changes to existing software and finding the shortest path between two inhabited localities specified interactively. To solve the first problem the coordinates are recalculated ("zoom"). To solve the second problem the article considers "preparatory graph" with the vertices of two types: temporary - in sequential points along each selected highway, and permanent - in the points of intersection of highways. Edges of the graph are formed by the segments that connect adjacent points along each highway. At the end of one of the known algorithms for finding the shortest path in the graph is used. Stored arrays of temporary intermediate vertices are used for visualization of the found the shortest path.


Keywords:

map of the region, scaling, shortcut, coordinates, canonical map, preparatory graph, Dijkstra's algorithm, temporary vertices, permanent vertices, graph of roads

Введение

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

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

1 2

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

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

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

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

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

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

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

3

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]); запомненные массивы временных промежуточных вершин служат для целей визуализации найденных кратчайших путей.

Библиография
1. Ахо, А. Построение и анализ вычислительных алгоритмов. Перевод с англ. / А.Ахо, Дж. Хопкрофт, Дж. Ульман. – М.: Мир, 1979. – 536 с
2. Негольс А.В., Пискова А.В. Системы определения местонахождения // NB: Кибернетика и программирование.-2013.-4.-C. 46-50. URL: http://www.e-notabene.ru/kp/article_9357.html
3. Боровский А.С. Модели оценки защищенности потенциально – опасных объектов от угроз с использованием экспертной информации в нечеткой форме // NB: Кибернетика и программирование.-2013.-4.-C. 14-45. URL: http://www.e-notabene.ru/kp/article_9593.html
References
1. Akho, A. Postroenie i analiz vychislitel'nykh algoritmov. Perevod s angl. / A.Akho, Dzh. Khopkroft, Dzh. Ul'man. – M.: Mir, 1979. – 536 s
2. Negol's A.V., Piskova A.V. Sistemy opredeleniya mestonakhozhdeniya // NB: Kibernetika i programmirovanie.-2013.-4.-C. 46-50. URL: http://www.e-notabene.ru/kp/article_9357.html
3. Borovskii A.S. Modeli otsenki zashchishchennosti potentsial'no – opasnykh ob''ektov ot ugroz s ispol'zovaniem ekspertnoi informatsii v nechetkoi forme // NB: Kibernetika i programmirovanie.-2013.-4.-C. 14-45. URL: http://www.e-notabene.ru/kp/article_9593.html