Information Technology Reference
In-Depth Information
Algorithm 1. Placing labels using east anchors
Input:
p
1
,...,p
n
are the sites in the text
Output:y-coordinate
y
1
,...,y
n
of the top edge of each label
1
P ₐ{p
1
,...,p
n
}
2
L ₐ
[]
// list contains labels in the order in which they are
placed
3
lastY ₐ
0
4
while
P
=
∅
do
5
H ₐ{height
(
p
j
)
| j
=1
,...,n}
//
H
is in ascending order
foreach
h ∈ H
do
6
place a label of height
h
directly below the last label
7
emit a ray from the port of the newly placed label
8
i ₐ
index of first point in
P
that is hit by the ray (rotated clockwise)
9
if
height
(
p
i
)
≤ h
then
10
break
11
y
i
ₐ lastY −
(
h − height
(
p
i
))
/
2
12
L
.add(
p
i
)
13
P ₐ P −{p
i
}
14
lastY ₐ y
i
− height
(
p
i
)
// Postprocessing: try to shrink gaps
15
foreach
l ∈ L
do
16
if there is a gap above
l
then
17
move
l
up as far as possible without creating any new intersection
between leaders
18
right. The second control point is always placed in the center between the first
control point and the site.
In the first iteration of the algorithm, the control points are placed on the
endpoints of the leader, that is, it starts as a straight line. Later, the first control
point of each curve is moved by applying forces to it. We use a force that pulls
the control point to its optimal point, which is computed beforehand and usually
yields a good-looking curve. Other forces try to increase the distance between
curves. In every iteration the forces on every point are limited by the distance
to the nearest curve to inhibit new intersections between leaders. Therefore, the
algorithm guarantees crossing-free Bézier curves when starting with straight-line
leaders without intersections.
The runtime of this algorithm is dominated by the calculation of the distances
between each pair of curves. This calculation is done by an approximation of the
curves. We need the distances to update the forces in every iteration.
3.3
opo
-Leaders and
os
-Leaders
Positioning the labels for crossing-free
opo
-leaders is simple as Bekos et al. [5]
show: we place the labels in the order given by the y-coordinates of their sites.
