Information Technology Reference
In-Depth Information
r ˄
p t
r ( t,b,k )
r ˃
p s
p b
r ʲ
Fig. 3. The labeling problem for T [ t,b, ˄, ʲ, k ] is split into two independent subproblems
by fixing the label position of r ( t,b, k ). The dashed lines show the raster slots. The light
gray area indicates the slots from r ˄ to r ʲ . The dark gray area shows the sites between
p t and p b .
only the raster slots r ˄ ,...,r ʲ . The labels must lie completely inside the given
slots.
Let r ( t,b,k ) the k -th point from the left in the set {p t ,...,p b } . The length
of the shortest po -leader from the site p to its corresponding label beginning in
slot r ˃ is denoted by l ( p,˃ ). The entries of the table are computed using the
following decomposition (illustrated in Fig. 3):
l ( r ( t,b,k ) )+ T [ t, s, ˄, ˃
T [ t,b,˄,ʲ,k ]=
min
feasible ˃
1 ,k 1 ]
∈{
˄,...,ʲ
}
+ T [ s +1 ,b,˃ + h,ʲ,k 2 ]
In this formula p s is the lowest point that lies above the leader arm (the horizon-
tal part of the leader), when the label for r ( t,b,k ) is placed at slot r ˃ .Let h the
height of this label. The number of sites from
lying left of r ( t,b,k )
and above resp. below the leader arm is denoted by k 1 resp. k 2 .
A position for the label is feasible, if both partial solutions (above and below
the leader arm) are feasible, that is, there are enough slots to label the contained
sites.
Clearly, T [1 ,n, 1 ,m,n ] is the optimal labeling of the whole instance. With this
algorithm we can compute an optimal solution in O ( n 4 m 3 ) time with O ( n 3 m 2 )
space, where n is the number of sites to be labeled and m is the number of slots
in the raster on the page.
{
p t ,...,p b }
Avoid overlappings with text lines. The algorithm described above does not take
the position of the text lines of the document into account. Thus it can happen
that a line gets striked out by the horizontal segment of a leader. We modified
the algorithm to move the port up or down by a small offset to avoid such
overlappings and place the leader into the gap between the lines.
It is quite hard to determine the positions of the lines in Tex because they
are not fixed until the document is written to the output file. But in Luatex we
can modify the linebreaking algorithm such that it inserts special nodes into the
data structures of Tex that write the position of every line into a text file when
 
Search WWH ::




Custom Search