Digital maps are part of geographic
information systems. The basis of construction of digital maps are topographic
maps of the area. Digital maps are often used to move objects on the ground (or
in air, water space).
Objects displayed on digital maps
are, for example, ships and aircraft, road, and rail transport. All listed
objects refer to point features: objects whose position in space is given by a
single point [1]. On the map, such objects are displayed using conventional
symbols. A conventional symbol is a graphic representation of an object that
characterizes the displayed object in a certain way.
When displaying point objects on a
digital map, several characteristics of the object and the symbol are
considered. Each object has coordinates and a label - brief textual information
describing the main parameters of the object. The label has dimensions and is
tied to the coordinates of the object. Symbols of objects also have dimensions,
that is, the maximum width and height, and are also tied to the coordinates of
the objects.
To evaluate the mutual actions of
objects, it is necessary to display a set of objects on a digital map at once.
To identify a specific object on the map, along with the symbol of the object,
its label is displayed. In various situations, labels can overlap each other,
as well as cover part of the conventional signs. This situation leads to a
decrease in the readability of the map, complicates the location of a
particular object on the map, and makes it difficult to assess the interactions
of objects.
The main factors in the occurrence of
the object labels overlay:
•
small scale of digital
map;
•
the presence of
localization centers of objects in the area of the considered space.
At a small scale (the case of observing a large area
of a digital map), a greater number of objects fall into the region of space
reflected on the map compared to a large-scale map. As a result, the likelihood
of object labels overlapping each other increases. Simply zooming in on the map
to solve the problem of overlapping labels is not always effective. It may be
the task of analyzing the situation on a large section of the map.
When analyzing the display of point objects on the
map, it is possible to identify some features of their location in space. Such
a feature is the presence of areas, let's call them the centers of localization
of objects, where a significantly larger number of objects is observed in
comparison with the rest of the space. When displaying aircraft on the map,
airports, cities, etc. can be localization centers. Obviously, in such areas,
the overlap of object labels is possible even at sufficiently large scales of
the map.
In this paper, one of the methods for placing point
feature labels on a digital map is considered: an automatic method, when an
algorithm is used that calculates a certain location of labels in real time.
When placing object labels automatically, it is
necessary to ensure:
•
maximum readability of
labels;
•
the ability to
unambiguously match a label with its object;
•
sufficient speed when
solving the problem of placement.
The first two requirements are quite clear. However, the
criteria for «readability» and «unambiguous comparison» should be clearly
defined since these concepts are quite different for each individual person.
Providing the last requirement to allow using the results of solving the
placement problem for moving objects, that is, for objects that quickly change
their position on a digital map.
Currently, in many software tools that use digital
maps, the problem of automatic placement of labels is solved in the most
trivial way: the object label is displayed in one strictly fixed position
relative to the symbol of the object. When there are many objects, some of the
labels are not displayed at all, to avoid overlapping them. This approach can
be observed, for example, on sites with a digital map to display aircraft in
real time [2, 3]. Obviously, in this case it is impossible to uniquely identify
a particular object.
One of the approaches to solving the problem of
automatic placement of labels is the use of mathematical programming methods.
So, in general case, among the set of possible solutions (in our case, the
solution is a specific set of coordinates by which the labels are placed on the
map), the solution is chosen that can be qualified as optimal in one sense or
another according to some chosen criterion.
To apply the methods of mathematical programming, one
should set an optimization problem by choosing a quality indicator (a
functional, the extremum of which is sought using the optimization method) and
imposing restrictions on the variables of the optimization problem (a set of
label coordinates) [4].
We will analyze the initial data of the task and
determine the quality indicator based on the requirements for placing the
labels indicated above.
Initial data in the task are the coordinates of object
in the coordinate system of the map (a specific pixel on the
map). The map is made up of pixels, its width is
and its height is
pixels. The object itself is represented by a material
point, the dimensions of the symbols are not taken into account.
In this paper, we will consider a standard rectangular
label with a transparent base. For clarity, let the label display only the call
sign of the object (for example, the aircraft callsign):
Fig. 1
Object (indicated by a triangle) and its label.
When setting the optimization problem, we will
identify the label with a rectangle (marked in red in Figure 1). The object is
located at the point with coordinates (
). The anchor point of the label is the center of the
rectangle with coordinates (
. The letters
and
denote half the length and height of the label in map
pixels, respectively (the length of the entire label is
, the height is
). For a unit of length, «halves» of the dimensions of the
label are taken in order to avoid the appearance of unnecessary numerical
coefficients in the formulas in the future. When solving the optimization
problem, we will accept the constraint that for all objects the size of their
labels is the same and equals
in length and
in height.
Another very important constraint is related to the
numerical type of label coordinates. The label coordinates are integer (they
determine the position of a pixel on a digital map). However, when setting the
problem, it is permissible not to impose a restriction on the integer value of
the coordinates of the labels. Such a «relaxation» significantly expands the
set of approaches and methods that can be used to solve the problem. If any
method for solving the set non-integer problem will provide maximum performance
(in comparison with methods for solving integer problems), an error of ±0.5
pixels is quite acceptable. The obtained coordinates can be rounded up to
integers and placing the labels at these coordinates will not impair the
readability of the information from the labels.
Let's try to formulate the statement of the problem of
automatic placement of labels in general. It is necessary to obtain coordinates
of labels of objects
, by the given coordinates of n objects, the size of the
label and the size of the map. It is necessary that the location of the labels
at these coordinates ensures the maximum readability of information from them
for the unambiguous identification of a particular object on the map when
placing labels on a digital map.
To formalize the subjective requirements of
«readability» of information from labels and «unambiguous identification», we
formalize the concepts of imposing a label on an object and imposing labels on
each other.
Overlaying a label on an object means that the object
enters the label area (rectangle). In other words, the label overlaps the
object when the point with coordinates (
) falls within the region of the rectangle centered at the
point (
.
We will divide the options for overlaying labels on
top of each other into two groups: full overlays and partial overlays. Full
overlap will be considered the situation when the center of one label (with
coordinates (
) falls into the area of another label (rectangle). We will
consider such a situation unacceptable, and the information contained in the
labels unreadable.
We will designate the variant as partial overlap, when
the centers of the labels do not fall into each other's areas, but the overlap
area of the labels is not equal to 0. We will consider such a situation
acceptable.
As mentioned above, the optimization problem is the
problem of finding the extremum of the objective function (quality index) with
a set of restrictions on the optimization variables. When it comes to the
placement of labels, the optimization variables will be the coordinates of the
object labels. Now it is necessary to decide which function will act as an
indicator of the quality of placement of labels.
As an indicator of quality, you can consider the
overlap area of the labels. With this approach, there is a need to calculate
the area of overlap of one label on another. In the case when several labels
overlap each other, and the number of labels is quite large, such calculations
can greatly affect the performance (one of the requirements for automatic
placement of labels given in Section 2). Therefore, other options for the
quality indicator are proposed.
Let it be necessary to ensure the minimum overlap of
labels on each other. This means that the greater the mutual distance between
the labels, the higher the chance that the overlap will be minimal, and, as a
result, the readability of information from the labels will increase. In this
case, as a quality indicator, you can choose the total distance between the
labels and solve the optimization problem as a problem of maximizing the total
distance.
It is possible to formulate the problem with a different
quality indicator. Let it be necessary to ensure the possibility of unambiguous
identification of an object using its label. Then, the closer the label is to
its object, the higher the chance of accurately matching the label with its
object. As a quality indicator, we choose the total distance from objects to
their labels. Then it is possible to set the optimization problem as the
problem of minimizing the total distances.
Based on the above, we formulate the optimization
problem in two versions: to the maximum and to the minimum.
The
objective function for the distance maximization problem:
|
|
(1)
|
where
is the number of labels,
and
are the coordinates of the centers of
and
j labels.
Thus, we maximize the sum of squared distances between
labels.
Let's put restrictions:
1.
Restrictions on the
distance between the object and the label:
|
|
(2)
|
where
,
are the half-width and half-height of the label, respectively
.
The distance from the object to its
label should not exceed
squares of the label diagonal, where
is chosen empirically and then
is assumed.
2.
Restrictions on the
intersection of the label with the object:
|
for
|
(3)
|
3.
Restrictions on overlapping labels:
|
for
.
|
(4)
|
The coefficient
is set for each object. It defines the boundaries of the
area around the
-label, which is not allowed to fall into the anchor point of
the
-label. The minimum value of this coefficient is
1. The object, for which the coefficient is equal to one, has
the lowest priority, and the maximum partial overlap is allowed for it (anchor
point of the
-form (red) is on the border of the
-label (black), hit to the region of the
-label is limited):
Fig. 2 Partial overlay (
1)
For
, the anchor point of the
-label is not allowed to fall into a rectangular area of size
*
(yellow in Figure 3):
Fig. 3
Partial overlay (
The maximum value that the
coefficient
can take is 2. An object for which the coefficient is equal
to 2 has the highest priority, and partial overlap is not allowed for it (the
anchor point of the
-label (red) does not fall into a rectangular area of size 4
* 4
(yellow on figure 4)):
Fig. 4
No overlay (
4.
Restrictions on going
beyond the boundaries of the map:
|
for
|
(5)
|
Here
and
are the width and height of the map in pixels.
The total number of optimization
problem constraints is
.
Such
an objective function is proposed to minimize
the
distance
between labels and objects:
|
|
(6)
|
where
is the number of labels,
are
coordinates of the
-object,
are
coordinates of centers of
-label.
We minimize the sum of squared distances between
objects and their labels.
Restrictions:
1.
Restrictions on overlapping
labels:
|
for
|
(7)
|
2.
Restrictions on the intersection
of the label with the object:
|
for
|
(8)
|
3.
Restrictions on going
beyond the borders of the map:
|
for
|
(9)
|
The total number of optimization problem constraints
is
.
To
solve the set optimization problems, the authors developed an application
written in Python. The optimization of the objective function was carried out
using the interior point algorithm for high-dimensional non-linear programming
problems. This algorithm is implemented in the SciPy library for scientific
computing [5]. Figure 5 shows solutions to the problem of maximizing the
distance between labels and minimizing the distance between labels and objects,
respectively.
Fig. 5 Solutions of problems of
maximizing the distance between labels (top) and minimizing the distance
between labels and objects (bottom) for
L=1920,
H=1080,
l=90,
h=28,
K=2,
ki=2,
for
i=1,20
The obtained solutions satisfy the requirement of
«readability» of information from the labels, each object is uniquely
identified. However, it should be noted that the formulated optimization
problems do not exclude the intersection of extension lines (lines connecting
the object and its label) of labels, which can also affect the quality of
information perception. Refusal to display extension lines, of course, reduces
the image «entanglement», but this approach is acceptable only in a situation
where the objects are located relative to each other at a distance greater than
half the diagonal of the label. With a greater object accuracy, it becomes
impossible to unambiguously compare each of them with its own label.
In the obtained optimal solutions of the minimization
problem (1–5), there are significantly fewer intersections of extension lines
than in another optimization problem (6–9). Obviously, the total length of
extension lines is greater when solving the maximization problem (6–9), which
increases the probability of their mutual intersection (Fig. 5). Thus, it can
be argued that it is more expedient to solve the minimization problem in order
to ensure better «readability».
Separately, it should be noted that the solution of
the minimization problem requires less calculations. When comparing the
objective functions (1) and (6), it is clear that to calculate the second one,
it is required to perform fewer addition and exponentiation operations. Also,
there are fewer restrictions in the formulation of the minimization problem,
which also affects the performance. This assumption is confirmed
experimentally. On average, the minimization problem is solved faster by 4–6%
In the results shown (Fig. 5), the optimal solution to the
problem of maximizing the distance between labels was obtained in 6.53 s, and
the solution to the problem of minimizing the distance between labels and
objects was obtained in 6.19 s. So, solving the minimization problem is also
more profitable from the point of view of performance.
In general, the dependence of the time for solving
optimization problems on their dimension (the number of objects) has a
quadratic character. Modification of the proposed problem statements to exclude
the intersection of extension lines will inevitably lead to the complication of
the system of restrictions. The number of restrictions will increase by
, since it will be necessary to check all extension lines in
pairs for intersections. Based on the total number of restrictions in the
problems already presented, when trying to eliminate the intersections of
extension lines, one should expect an increase in the time to find the optimal
solution up to 30%.
To apply the approach given in this article to solve
the problem of automatic placement of labels in the practical implementation of
a GIS, it is recommended to divide the initial data (a set of point objects)
into subgroups that include a small number of objects (10–15 pieces). And
further optimization problems should be solved in parallel for each subgroup.
This approach can potentially provide the performance required in each system.
This
article describes an approach for solving the problem of automatic placement of
labels of point objects on a digital map using methods of nonlinear
mathematical programming. Two options for setting optimization problems are
proposed: with a quality index in the form of a total distance between labels
and with a quality index in the form of a total distance between objects and
their labels. When solving optimization problems, restrictions on labels
overlapping each other, restrictions on labels overlapping objects, as well as
restrictions on labels leaving the map are considered. The fundamental
possibility of solving the problems posed with the help of the interior points
algorithm is shown, and the obtained optimal solutions are given.
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.
