Алгоритм размещения надписей географических объектов на карте

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

Алгоритм размещения надписей географических объектов на карте

Соловьёв Павел Игоревич

Студент Тюменского Государственного Университета

E-mail: scrou@yandex.ru

Расположение надписей географических объектов на карте является важной задачей картографии, которая заключается в позиционировании текстовых элементов на карте таким образом, чтобы подписи разборчиво для читателя соотносились с пространственными объектами, не перекрывая друг друга и не закрывая важные элементы карты. В традиционной картографии эта задача занимает до 20% времени от всей подготовки печатной карты [1, с. 142].

Задача размещения надписей на карте разбивается на подзадачи в соответствии с размерностью подписываемых объектов: полигоны, линии и точки [2, с. 1].

Общая постановка задачи расположения текстовых элементов формулируется следующим образом. Имеется N географических объектов , которые требуется разместить в области ? пространства . Каждый геометрический объект является точкой или полигоном. Точечные объекты характеризуются координатами , , а полигональные объекты характеризуются набором точек где - точка контура полигона с координатами,.

Введём следующие обозначения:

- символ i-го объекта;

- подпись к i-му объекту;

- область возможного расположения i-й подписи.

Объекты моделируются прямоугольниками, задающимися характеристиками: - координаты левого верхнего угла, - ширина, - высота. Для точечного объекта область возможного расположения текста также моделируется прямоугольником.

Для каждого объекта даны следующие характеристики: . Неизвестные характеристики для точечного объекта вычисляются по формулам (1) - (6):

географический карта надпись текстовый

(1)

(2)

(3)

(4)

(5)

(6)

У полигональных объектов символ отсутствует, поэтому . Область возможного расположения надписи полигонального объекта будет являться расширением контура . Обозначим кратчайшее расстояние между границами геометрических объектов и . Область строится таким образом, чтобы подпись в любом своём положении полностью принадлежала расширенному полигону, касаясь при этом исходного многоугольника с внешней стороны:

(7)

Вектор определяет размещение всех текстовых элементов в области ?. Из всех допустимых размещений требуется найти такое , которое бы удовлетворяло системе ограничений (8):

(8)

Данную задачу можно отнести к классу NP-полных задач [3, с 281, 4, с.1]. В общем случае задачу можно решить лишь полным перебором всех возможных комбинаций расположений подписей. На практике перебор всех возможных вариантов потребует больших временных затрат, так как асимптотика данного алгоритма в худшем случае составляет операций, где p - количество рассматриваемых позиций для каждой подписи, N - количество подписей.

Для размещения текстовых элементов к пространственным объектам на всей области карты разработан «Площадной алгоритм расположения подписей»:

Шаг 1. Найти все не влияющие на взаимное расположение друг друга группы подписей.

Шаг 2. Расположить подписи в каждой группе без пересечений.

Шаг 3. Расположить подписи с правилами или предпочтениями пользователя.

На реальной карте надписи разнесены по территории и располагаются группами, поэтому в одну группу объединяются лишь те элементы, области возможного расположения которых пересекаются. Надписи, расположенные в разных группах, не влияют на взаимное расположение друг друга, то есть при любых своих возможных положениях не пересекутся. Таким образом, на первом этапе алгоритма необходимо найти все различные группы подписей.

Вторым этапом является расположение подписей без пересечений в каждой найденной группе. Для каждой надписи в группе выполнить алгоритм:

Шаг 1. Найти неконфликтную область. Неконфликтная область - это область, на которую претендует только рассматриваемая подпись, среди всех подписей расположенных за ней в группе. Для нахождения неконфликтной области необходимо из области возможного расположения надписи вычесть области возможного расположения подписей расположенных после рассматриваемой в группе.

Шаг 2. Найти положение, в котором данная подпись не будет пересекаться с символами других объектов и надписями, расположенными ранее. Для нахождения позиции текста необходимо просмотреть всю область возможного расположения с некоторым шагом (величина шага выбирается из того, сколько позиций расположения может иметь каждая отдельно рассматриваемая подпись). Если во всех своих возможных позициях подпись пересекается с символами других объектов, то сформировать сообщение для пользователя о невозможности расположения рассматриваемой подписи без пересечения с символами других объектов, так как не выполняется третье равенство системы ограничений (8). Если найдено несколько положений без пересечений, то выбрать такое положение, в котором рассматриваемая подпись занимает наибольшую неконфликтную область. При успешном выполнении поиска перейти к рассмотрению следующей подписи.

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

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

Шаг 5. Если не удалось расположить надписи на предыдущем шаге, то поместить их в те положения, в которых они были до начала рассмотрения данной подписи. Второе равенство системы ограничений (8) не выполняется, поэтому сформировать для пользователя сообщение о том, что данная надпись не может быть расположена без пересечений с другими подписями.

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

Алгоритм реализован и проходит тестирование. Планируется, что данный алгоритм ускорит процесс подготовки печатных карт.

Список использованной литературы

[1] «Сибирский федеральный университет». Геоинформационные системы и технологии [Электронный ресурс]: http://gistechnik.ru/book/000.pdf (2014)

[2] Alexander Wolf. Automated Label Placement in Theory and Practice . Берлин - 1999, стр 1.

[3] Formann, WAGNER. A packing problem with applications to lettering of maps. In Proc. 7th Annual Symposium on Computational Geometry (1991), стр. 281-288.

[4] K.G. Kakoulis, I.G. Tollis, On the complexity of the edge label placement problem, Computational Geometry 18 (2001), стр 1-17.

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