Information Technology Reference
In-Depth Information
one below the other on the boundary while avoiding gaps between them. They
differ in the position of the ports, that is, the position on the label boundary
to which the leader is attached. A pleasant position for the port would be the
center of the right side of the label. Unfortunately, we don't have an algorithm
that can place the labels without gaps using this port position. We don't even
know whether every instance of site positions and label heights is feasible w.r.t.
these criteria; see Section 6.
We don't give algorithms that minimize the total leader length here, but
concentrate on drawings without crossings. The clustering approach described
in Section 4 can decrease the leader length as labels are placed closer to their
corresponding sites.
NorthEast. We use an algorithm of Bekos et al. [5] for fixed labels, which can
easily be adopted to our problem with labels of non-uniform heights: The
upper right corner of each label is used as its port. The labels are placed
consecutively from the top of the page to the bottom. In each step, we emit
a ray from the port of the next label vertically to the top and rotate it
clockwise until the first unlabeled site is hit. Obviously, by connecting this
site to a label at the current position, we don't hide any other sites and can
label the remaining sites without crossings.
NorthEastBelow. This algorithm is based on the preceding one. The difference
is that we lower the port from the corner by a constant offset. In our opinion
the result looks better when the leader is not attached directly at the corner.
A good value for this offset is half of the height of the smallest label. As we
know the position for each port while placing the label, we can still use
the ray construction of the preceding algorithm to place the labels without
spaces between them.
East. In this algorithm the port of every label is located at the center of its
right side. When we try to find the next unlabeled site to be labeled, we
do not know the port position as it depends on the height of the label.
Therefore, we cannot use the ray construction from the previous algorithms.
Algorithm 1 is a heuristic that guarantees crossing-free leaders while trying
to avoid gaps between the labels. It can usually handle real-world inputs
without additional gaps.
An instance that is not handled optimally by the heuristic is depicted in
Fig. 2. The sites can be labeled without gaps when placing the labels in the
order2,1,3.Asmentionedaboveitisanopenquestionifthisispossible
for all instances.
3.2 BézierCurvesasLeaders
We base our Bézier curves on
s
-leaders using a force-directed algorithm described
by Fink et al. [7]. We use cubic Bézier curves that are required to enter the port
at the label horizontally. This means that the first control point has to stay on
the same horizontal line as the port and can only be moved to the left or the
