Information Technology Reference
In-Depth Information
Algorithm 2. Clustering labels
Input:
p
1
,...,p
n
are the sites in the text ordered by their y-coordinate from
top to bottom
Output: list of clusters
S
1
S ₐ
[
{p
1
}, {p
2
},...,{p
n
}
]
2
i ₐ
1
3
while
i ≤
#
S −
1 do
4
if clustersIntersect(
S
[
i
],
S
[
i
+1]) then
S
[
i
]
ₐ S
[
i
]
∪ S
[
i
+1]
5
S
.delete(
i
+1)
// as the size of stack
i
has increased we check again for
intersection with the previous stack in next iteration
6
i ₐ
max
{
1
,i−
1
}
7
else
8
i ₐ i
+1
9
return
S
10
typesetting the page. In a second Tex run we can read the line positions from
this file and use them for our algorithm.
4
Improvements
In this section we discuss some general improvements implemented in our pack-
age that can be used by every algorithm described in the previous section.
Label clustering.
Most of the algorithms described in the previous sections place
labels in a single stack (that is, without gaps between them) beginning at the
upper margin of the page. This can produce unnecessarily long leaders, for ex-
ample when the text contains a single site near the end of the page. We split the
labels into separate clusters and place each of them near the corresponding sites
in the text. An algorithm for clustered labeling is also described by Nöllenburg
et al. [13]. Our approach is simpler but slower.
To group the labels into clusters we use Algorithm 2. It repeatedly joins
adjacent clusters as long as they intersect each other. To test if two clusters
intersect we place the contained labels as a stack each beneath the arithmetic
mean of the sites in the cluster. The clusters intersect if their corresponding
stacks overlap.
The positioning algorithm is executed independently for each of the identified
clusters. The intended position is passed to the algorithm as a parameter.
Two-sided label placement.
On some page layouts there is enough space to place
labels in the margins on the left
and
the right side of the text. We have to decide
for each label on which side of the text it should be placed. Our approach is to
split the sites by a vertical line through the text. The sites which are left of this
