Information Technology Reference
In-Depth Information
(a) Input
(b) Tree Construction
(c) Force-directed Adjustment
(d) EdgeAugmentation
(e) Adding Auxiliary Points
(f) Computing Map Regions
Fig. 5. Algorithmic pipeline of MapSets
4
MapSets
Here we describe MapSets, starting with a high-level overview; see Fig.5.Weassume
that the input is a set of rectangular shapes (bounding boxes of labels) embedded in
the plane along with a clustering. In the first step, we compute spanning mutually non-
crossing trees interconnecting centers of rectangles corresponding to the same cluster,
while minimizing the total ink needed to draw the trees. In the second step, we modify
the trees by adding buffers of free space around the segments of the trees, using a force-
directed heuristic. In the third step, we try to optimize the convexity of the resulting
regions based on the vertex visibility measure, by adding edges between vertices in the
same cluster, while ensuring that edges of different clusters do not cross. In the fourth
step, we use the modified trees and the added edges to build contiguous non-overlapping
boundaries for all clusters.
Tree Construction. In order to construct the trees, we employ the approximation al-
gorithm described in Section 3.2. For each cluster, we first compute a minimumtree
spanning the set of rectangle centers, ignoring other clusters. The clusters are then
sorted in non-decreasing order by the length of the computed trees and processed in
this order. At each step we consider all the precomputed trees as obstacles that should
be avoided when constructing the current tree. The rectangles are also treated as obsta-
cles. We compute a sparse visibility graph on the set of obstacles, where the vertices
are all the centers and corners of the rectangles, and there is an edge between two ver-
tices if one can draw a straight-line segment without crossing the obstacles. The sparse
visibility graph (unlike the full visibility graph) has a linear number of edges and can
be constructed efficiently [8]. We then compute shortest paths (of the visibility graph)
between every pair of rectangles of the current cluster. From these shortest paths, we
compute a minimum spanning tree for the current cluster.Weaddthetreetothesetof
obstacles and proceed with the next cluster.
Search WWH ::




Custom Search