Статья 'Просмотр карты с масштабированием и элементами навигации' - журнал 'Кибернетика и программирование' - NotaBene.ru
по
Journal Menu
> Issues > Rubrics > About journal > Authors > About the Journal > Requirements for publication > Council of Editors > Peer-review process > Policy of publication. Aims & Scope. > Article retraction > Ethics > Online First Pre-Publication > Copyright & Licensing Policy > Digital archiving policy > Open Access Policy > Article Processing Charge > Article Identification Policy > Plagiarism check policy
Journals in science databases
About the Journal

MAIN PAGE > Back to contents
Cybernetics and programming
Reference:

Viewing a map with zoom and navigation elements

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

Received:

17-09-2013


Published:

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

This article written in Russian. You can find original text of the article here .

Введение

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

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

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

References
1.
2.
3.
Link to this article

You can simply select and copy link from below text field.


Other our sites:
Official Website of NOTA BENE / Aurora Group s.r.o.