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

Размещено на http://www.allbest.ru/

3

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

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

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

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

Аннотация

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

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

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

координаты кратчайший путь масштабирование карта

Введение

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

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

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

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

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

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

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

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

Под правильной картой РД будем понимать прямоугольную область со сторонами, «параллельными» меридианам и параллелям, с противоположными углами «Краснодар-Севан» и «Базардюзю-Губа» по диагонали и соотношением сторон, как у канонической карты (в нашем случае 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 (transliterated)

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

Размещено на Allbest.ru