Information Technology Reference
In-Depth Information
Angular Treemaps algorithm
The basic concept for generating polygonal subdivision is to use the
weighted divide-and-conquer approach in the tessellation process. The
original divide-and-conquer is an important algorithm design paradigm
based on multi-branched recursion. It decomposes a problem into two or
more sub-problems of the same or related type, until the sub-problem
becomes simple enough to be solved directly. Similarly, we break down
the nodes into two groups according to the original sequence of their
orders, with similar weights for each group. In the partitioning process, our
algorithm divides the polygon into two sub-polygons, representing two
sub-groups of nodes. This procedure is executed recursively for all top
level nodes within the respective sub-polygons. The same process repeats
for each subgroup of nodes. When the recursion ends, a complete
partitioning is obtained.
In the polygon
P(v
i
), side
vertices
s
i,1,…,
s
i,i,…,
s
i,m
generate a number of
m
sides
L(s
i,1
,
s
i,1
),…, L(s
i,i
,
s
i,i+1
),…, L(s
i,m-1
,
s
i,m
), L(s
i,m
,
s
i,1
).
Among the
sides, the longest side is defined as
L
max
. The very first partitioning line
begins from the longest side
L
max
. The partitioning direction is against the
longest side
L
max
with selected angle
Į
and then the partitioning line
continues in a vertical direction against the created new line. In the
implementation,
Į
is restricted to 15º, 30º, 45º, 60º, 75º, and 90º for
demonstration purposes.
The angular partitioning applies until the leaf
nodes of this particular polygon are reached. As a result,
P(v
i
)
is
partitioned into sub-polygons for
{v
i,1
,…,v
i,i
,…,v
i,n
}
with corresponding
polygonal boundary
{P(v
i,1
),…, P(v
i,i
),…, P(v
i,n
)}
and with weight
{w(v
i,1
),…, w(v
i
,
i
), …, w(v
i,n
)}.
We use an example to demonstrate this approach with different
angles
Į
. For example, a dataset has a tree root at 0.0, which contains six child
nodes
{1.0, 1.1, 1.2, 1.3, 1.4, 1.5},
whose weights are
{8, 6, 1, 2, 4, 1}
respectively, according to the number of sub-nodes contained (see Fig.
5.2). Fig. 5.3(a) shows the partitioning at 90 degrees which is similar to
the traditional treemap algorithms, and Fig. 5.3(b) shows the partitioning
at 60 degrees. Fig. 5.4 shows more examples of layouts in rectangular
containers, generated by the algorithms using a large data set with
approximately 12,000 nodes.
Search WWH ::
Custom Search