Databases Reference
In-Depth Information
Figure 17: A final
result by the
intersection-first
method
Figure 15: A final
result by the cost-
first method
Figure 16:
Computed
candidate places
by the
intersection-first
method
Figure 14: Com-
puted candidate
places by the cost-
first method
Next, the cost is determined by the following strategy: The closer a candidate
place is to the middle point of the edge, the smaller its cost is set. Also, positions in
the upper side of the edge is set to have less cost. See Fig.13.
We then apply a greedy approach which maintains a set of candidate places as
processing edges one by one in some fixed order. In processing an edge, this set
may be made smaller by deleting candidates in the following two manners:
Cost-first greedy approach
In processing an edge
e,
for any intersecting pair of a candidate
place for
e
and a candidate place for some other
e',
the place having the higher cost
among two is removed from the set. Fig.14 is an example output. After processing all
edges, we select the lowest cost candidate place among remaining candidate places for
each edge. The result for Fig.14 is Fig.15.
Intersection-first greedy approach
In this approach, each candidate place is associated further
with the number, called the intersection number, of other candidate places, in the current
set, intersecting with it. Then, the algorithm proceeds in a similar way by removing the
candidate place having higher intersection number. Fig.16 is an example output, for
the same data set in Fig.14. As in the case of the cost-first greedy approach, at the end,
we select the least cost candidate place among remaining candidates for each edge. For
Fig.16, a result becomes as in Fig.17.
Comparing Fig.14 and Fig.16, the final candidate set in Fig.14 is of size 16, while
18 in Fig.16. Concerning the final results, the intersection-first method is superior
in this case. Also, it gives a well-balanced placement.
The above method can be extended to place a label to a polygonal line. A
subway line may be represented by a polygonal line whose nodes are stations and
edges are subway lines connecting adjacent stations. In such cases, just one
placement of a subway line label suffices in the subway map. The above method
can be extended to this case.
Fig.18 and Fig.19 are results for the Tokyo metropolitan subway map by the
cost-first and intersection-first greedy algorithms, respectively. In this case, many
lines
