1. Введение

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

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

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

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

К основным факторам возникновения наложения формуляров объектов можно отнести:

• мелкий масштаб цифровой карты;

• наличие центров локализации объектов в области рассматриваемого пространства.

При мелком масштабе (случай наблюдения за большим участком цифровой карты) в область пространства, отражаемого на карте, попадает большее количество объектов по сравнению с картой крупного масштаба. Как следствие, увеличивается вероятность наложения формуляров объектов друга на друга. Простое увеличение масштаба карты как решение проблемы наложения формуляров возможно не всегда, так как может стоять задача анализа обстановки в целом на большом участке карты.

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

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

2. Автоматическое размещение формуляров объектов

При автоматическом размещении формуляров объектов необходимо обеспечить:

• максимальную читаемость формуляров;

• возможность однозначного сопоставления формуляра со своим объектом;

• достаточное быстродействие при решении задачи размещения.

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

В настоящее время в большом количестве программных средств, использующих цифровые карты, задача автоматического размещения формуляров решена самым тривиальным способом – формуляр объекта отображается в одном строго фиксированном положении относительно условного знака объекта. Когда объектов много, часть формуляров не отображается вовсе, с целью избежать наложения их друг на друга. Такой подход можно наблюдать, к примеру, на сайтах с цифровой картой для отображения воздушных судов в реальном времени [2, 3]. Очевидно, что в такой ситуации невозможно однозначно идентифицировать конкретный объект.

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

Для применения методов математического программирования следует поставить оптимизационную задачу, выбрав показатель качества (функционал, экстремум которого ищется с помощью метода оптимизации) и наложив ограничения на переменные задачи оптимизации (набор координат формуляров) [4].

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

3. Исходные данные и соглашения

Исходными данными в задаче являются координаты объекта в системе координат карты (конкретный пиксель на карте). Карта состоит из пикселей, ее широта составляет , а высота пикселей. Сам объект представляется материальной точкой, габариты условных знаков не учитываются.

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

 

Рисунок 1 - Объект (обозначен треугольником) и его формуляр

 

При постановке задачи оптимизации будем отождествлять формуляр с прямоугольником (на рисунке 1 обозначен красным). Объект располагается в точке с координатами ( ). Точка привязки формуляра – центр прямоугольника с координатами ( . Буквы и обозначают половину длины и высоты формуляра в пикселях карты соответственно (длина всего формуляра – , высота ). За единицу длины взяты «половинки» размеров формуляра с целью избежать в дальнейшем появления в формулах излишних числовых коэффициентов. При решении задачи оптимизации примем ограничение, что для всех объектов размер их формуляров одинаков и равен по длине и по высоте.

Еще одно очень важное ограничение связано с численным типом координат формуляров. Координаты формуляров – целочисленные (определяют положение пикселя на цифровой карте). Однако при постановке задачи ограничение на целочисленность координат формуляров допустимо не налагать. Такое «послабление» значительно расширяет множество подходов и методов, которые могут использоваться при решении поставленной задачи. В случае, если какой-либо метод решения поставленной нецелочисленной задачи позволит обеспечить максимальное быстродействие (в сравнении с методами решения целочисленных задач), погрешность в ±0.5 пикселя вполне допустима. Полученные координаты могут быть округлены до целых, а размещение формуляров по этим координатам не ухудшит читаемость информации с формуляров.

Сформулируем постановку задачи автоматического размещения формуляров «в целом». Так, по заданным координатам объектов, размеру формуляра и размеру карты необходимо получить такие координаты формуляров объектов , чтобы при расположении формуляров на цифровой карте была обеспечена максимальная читаемость информации с них для однозначной идентификации конкретного объекта на карте.

Для того чтобы формализовать субъективные требования «читаемости» информации с формуляров и «однозначной идентификации» формализуем понятия наложения формуляра на объект и наложения формуляров друг на друга.

Наложение формуляра на объект (или иначе перекрытие объекта формуляром) – попадание объекта в область формуляра (прямоугольник). Другими словами, формуляр перекрывает объект, когда точка с координатами ( ) попадает в область прямоугольника с центром в точке ( .

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

Частичным наложением будем обозначать вариант, когда центры формуляров не попадают в области друг друга, но площадь наложения формуляров не равна 0. Такую ситуацию будем считать допустимой.

4. Постановка задач оптимизации

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

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

Пусть следует обеспечить минимальное наложение формуляров друг на друга. Это значит, что чем больше взаимное расстояние между формулярами, тем выше шанс, что наложение будет минимальным, и, как следствие, возрастет читаемость информации с формуляров. Тогда в качестве показателя качества можно выбрать суммарное расстояние между формулярами и решать задачу оптимизации как задачу максимизации суммарного расстояния.

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

Исходя из вышеописанного, поставим задачу оптимизации в двух вариантах: на максимум и на минимум.

5. Максимизация расстояния между формулярами

Целевая функция для задачи максимизации расстояния:

(1)

где – количество формуляров, и – координаты центров -го и -го формуляров соответственно.

Таким образом, максимизируем сумму квадратов расстояний между формулярами.

Поставим следующие ограничения:

1. Ограничения на расстояние от объекта до формуляра:

(2)

где , – полуширина и полувысота формуляра соответственно

Расстояние от объекта до его формуляра не должно превышать квадратов диагонали формуляра, где выбирается эмпирически и далее принято .

2. Ограничения на наложение формуляра на объект:

при

(3)

3. Ограничения на наложение формуляров:

.

(4)

Коэффициент задан для каждого объекта. Он определяет границы области вокруг -го формуляра, в которую недопустимо попадать точке привязки -го формуляра. Минимальное значение этого коэффициента равно 1. Объект, для которого коэффициент равен единице, имеет наименьший приоритет, и для него допустимо максимальное частичное наложение (точка привязки -го формуляра (красный) находится на границе -го формуляра (черный), попадание в область -го формуляра ограничено):

 

Рисунок 2 – Частичное наложение ( 1)

 

При точке привязки -го формуляра недопустимо попадать в прямоугольную область размером * (на рисунке 3 желтая):

 

Рисунок 3 – Частичное наложение (

 

Максимальное значение, которое может принимать коэффициент 2. Объект, для которого коэффициент равен 2, имеет наивысший приоритет, и для него недопустимо частичное наложение (точка привязки -го формуляра (красный) не попадает в прямоугольную область размером 4 * 4 (на рисунке 4 желтая)):

 

Рисунок 4 - Наложение отсутствует (

 

4. Ограничения на выход за границы карты:

(5)

Здесь и – ширина и высота карты в пикселях.

Общее количество ограничений задачи оптимизации равно .

6. Минимизация расстояния до объектов

Для минимизации расстояния формуляров до объектов предлагается следующая целевая функция:

(6)

где – количество формуляров, – координаты -го объекта, – координаты центров -го формуляра.

Таким образом, минимизируем сумму квадратов расстояний от объектов до их формуляров.

Ограничения:

1. Ограничения на наложение формуляров:

(7)

2. Ограничения на наложение формуляра на объект:

при

(8)

3. Ограничения на выход за границы карты:

(9)

Общее количество ограничений задачи оптимизации равно .

7. Решение задач оптимизации

Авторами для решения поставленных задач оптимизации было разработано приложение на языке Python. Оптимизация целевой функции производилась с помощью алгоритма внутренней точки для задач нелинейного программирования большой размерности. Данный алгоритм реализован в библиотеке для научных вычислений SciPy [5]. На рисунке 5 приведены решения задачи максимизации расстояния между формулярами и минимизации расстояния до объектов соответственно.

 

Рисунок 5 – Решения задач максимизации расстояния между формулярами (сверху) и минимизации расстояния до объектов (снизу) при L=1920, H=1080, l=90, h=28, K=2, k_i=2, при i=1,20

 

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

В получаемых решениях задачи минимизации (1–5) пересечений выносных линей существенно меньше, чем в другой задаче оптимизации (6–9). Очевидно, что при решении задачи максимизации (6–9) суммарная протяженность выносных линий больше, что повышает вероятность их взаимного пересечения (рис. 5). Таким образом, можно утверждать, что целесообразнее решать именно задачу минимизации для обеспечения лучшей «читаемости».

Отдельно стоит отметить, что решение задачи минимизации требует меньше вычислений. При сравнении целевых функций (1) и (6) видно, что для вычисления второй требуется производить меньше операций сложения и возведения в степень. Также в постановке задачи минимизации меньше и ограничений, что тоже сказывается на быстродействии. Это предположение подтверждается экспериментально. В среднем, задача минимизации решается быстрее на 4–6% В приведенных результатах (рис. 5) оптимальное решение задачи максимизации расстояния между формулярами получено за 6.53 с., а решение задачи минимизации расстояния до объектов – за 6.19 с. Так, решать задачу минимизации более выгодно и с точки зрения быстродействия.

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

Для применения приведенного в данной статье подхода для решения задачи автоматического размещения формуляров при практической реализации ГИС рекомендуется разбивать исходные данные (набор точечных объектов) на подгруппы, включающие небольшое количество объектов (10–15 штук). И решать задачи оптимизации параллельно для каждой подгруппы. Такой подход потенциально может обеспечить требуемое в каждой конкретной системе быстродействие.

8. Заключение

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

Список литературы

1. Абламейко С.В., Крючков А.Н. Информационные технологии создания и обновления цифровых и электронных карт местности // Информатика. 2004. №2. С. 86-93.

2. Flightradar24 live air trafic [Электронный ресурс] // flightradar24.com URL: https://www.flightradar24.com/ (дата обращения: 03.01.22).

3. AirNav RadarBox [Электронный ресурс] // radarbox.com URL: https://www.radarbox.com/ (дата обращения: 03.01.22).

4. Хедли Дж. Нелинейное и динамическое программирование: пер. с англ. / Дж. Хедли. М.: Мир, 1967. – 534 с.

5. Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. 1999. An interior point algorithm for large-scale nonlinear programming. SIAM Journal on Optimization 9.4: 877-900.

---

Automating Placement of Point Feature Labels on a Digital Map using Non-linear Mathematical Programming

Authors: M. Y. Zarubin^1,A,B, I. G. Pristupa^2,B, S. V. Ktitrov^3,A

^A National Research Nuclear University MEPhI, Moscow, Russia

^B JSC «Concern «Sozvezdie», Voronezh, Russia

¹ ORCID: 0000-0003-0104-6871, Zarubin.Misha@gmail.com

² ORCID: 0000-0002-8985-8358, inna.g.pristupa@yandex.ru

³ ORCID: 0000-0002-7963-9151, svktitrov@mephi.ru

 

Abstract

A paper considers one of the approaches to solving the problem of automating placement of point feature labels on a digital map. The causes of label overlaps are analyzed, and requirements for label placement are formulated. Two different statements of optimization problems are proposed for finding the optimal locations of labels of point feature labels on a digital map. One of them is based on the idea that as the distance between labels increases, the chance of labels overlay decreases, and as a result, it becomes possible to identify each point feature on a digital map and read information about it presented on the label. In another statement, it is proposed to minimize the distances from objects to their labels in order to quickly and efficiently identify a particular object on the map. The article presents the results of solving optimization problems, which show the fundamental possibility of obtaining optimal label locations and demonstrates the quality of label placement using the considered approaches.

 

Keywords: digital map, label, optimization methods, optimization problem, labels overlay.

 

References

1. Ablamejko S.V., Kryuchkov A.N. Informacionnye tekhnologii sozdaniya i obnovleniya cifrovyh i elektronnyh kart mestnosti [Information technologies for creating and updating digital and electronic maps of the area] // Informatics. 2004. №2. p. 86-93 [in Russian].

2. Flightradar24 live air trafic URL: https://www.flightradar24.com.

3. AirNav RadarBox URL: https://www.radarbox.com.

4. G. Hadley. Nonlinear and dynamic programming. A ddison-Wesley Publishing Company Inc., 1964.

5. Byrd, Richard H., Mary E. Hribar, and Jorge Nocedal. 1999. An interior point algorithm for large-scale nonlinear programming. SIAM Journal on Optimization 9.4: 877-900.