г. Тюмень, 29-31 октября 2014 г.

Соловьёв П.И.  

Разработка алгоритма расположения подписей

Работа посвящена разработке алгоритма расположения подписей географических объектов на карте. В традиционной картографии данная задача занимает до 20% времени от всей подготовки печатной карты [1].
При расположении подписей на бумажной печатной карте учитывают четыре следующих правила:
• Подпись должна четко соответствовать элементу, к которому она относится;
• Пересечение подписей между собой должно быть минимально;
• Пересечение подписей с другими географическими объектами должно быть минимально;
• Подписи размещаются эстетически привлекательно.
Формально задачу можно сформулировать следующим образом. Задано множество географических объектов (точек и полигонов), которому соответствуют множество символов и множество подписей. Требуется расположить подписи так, чтобы исключить их пересечения между собой и с символами других объектов.
Рассматриваемую задачу можно отнести к классу NP-полных задач [2, 3]. В общем случае задачу можно решить лишь полным перебором всех возможных комбинаций расположений подписей. На практике перебор всех возможных вариантов потребует больших временных затрат, так как асимптотика данного алгоритма в худшем случае составляет PN операций, где P – количество рассматриваемых позиций для каждой подписи, N – количество подписей.
Для размещения текстовых элементов к пространственным объектам на всей области карты разработан «Площадной алгоритм расположения подписей». Суть алгоритма заключается в поиске групп подписей, не влияющих на взаимное расположение друг друга, после чего выполняется расположение подписей в каждой группе.
Для расположения надписей в группе был разработан алгоритм, основывающийся на поиске неконфликтной области. Неконфликтная область – область, на которую претендует только рассматриваемая подпись, среди всех подписей расположенных за ней в группе.
Предполагается, что в результате работы алгоритма будет создан косметический слой точечных объектов. Географические точки, содержащиеся в нём, будут являться фиктивными, и служить лишь для позиционирования подписей. Информация о каждой подписи (гарнитура шрифта, размер) будут храниться в атрибутивной таблице данного файла. Таким образом, сгенерированный файл можно будет добавить к исходным файлам в любой ГИС системе, оставив подписи к объектам лишь в сгенерированном файле, скрыв при этом отображение самих точек.
Алгоритм реализован и проходит тестирование. Планируется, что предлагаемый алгоритм ускорит процесс подготовки печатных карт.

Список литературы
1. «Сибирский федеральный университет». Геоинформационные системы и технологии [Электронный ресурс]: http://gistechnik.ru/book/000.pdf (2014)
2. Formann, WAGNER. A packing problem with applications to lettering of maps. In Proc. 7th Annual Symposium on Computational Geometry (1991), стр. 281–288.
3. K.G. Kakoulis, I.G. Tollis, On the complexity of the edge label placement problem, Computational Geometry 18 (2001), стр 1–17.

Тезисы доклада:abstracts_247334_ru.pdf
Файл с полным текстом: Соловьёв П.И..docx


К списку докладов

Комментарии

Имя:
Код подтверждения: