Squarified Treemap
A treemap is a visualization technique based on containment that partitions the space recursively according to
the size of the subtrees. It is space-filling, where leaf nodes are clearly visualized.
The Squarified Algorithm
- Squarified Treemaps, Mark Bruls, Kees Huizing, and Jarke J. van Wijk, 2000
- It generates rectangles with a nice aspect ratio
-
The optimal aspect ratio of a rectangle is achieved for a square;
in this case \(\frac{width}{height}=\frac{height}{width}=1\)
- Computation of the optimal partition is NP-hard
- The squarified algorithm is a greedy approach that generates solutions with good quality
Advantages
- space is used more efficiently (ratio between perimeter and surface is optimal for a square)
- square items are easier to detect that long and thin rectangles
- comparison of sizes is better
The Algorithm
Given a rectangle with height \(h\) and large enough, the squarified algorithm draws \(n\) areas
\(a_1, \dots, a_n\) within the rectangle representing the leaves of the tree. These areas should be as
square as possible and have the same width. Therefore, it follows:
\[
\begin{align}
h_1 \times w &= a_1\\
...& \\
h_n \times w &= a_n
\end{align}
\]
where \(w\) is the width of the inserted triangles. Tthe following relations for the height and the width of
the inserted rectangles apply:
\[
(h_1 + \dots + h_n)\times w = (a_1 + \dots + a_n) = a \quad
\implies w = \frac{a}{h}, \quad \text{width} \; h = h_1 + \dots h_n
\]
The height of an inserted rectangle is given by \(h_i = \frac{a_i}{a} h\). The aspect ratio, height over
width, of the \(ith\)-rectangle is:
\[
\frac{h_i}{w} = \frac{a_i}{w^2} = \frac{a_i h^2}{a^2}
\]
If the aspect ratio is computed as width over height, one gets \(\frac{a^2}{a_i h^2}\).
Main Loop
if a node has children nodes, layout the children nodes (siblings) with the squarified method
recursively process each of the children nodes
Layout of Sibling Nodes
Note: the algorithm refers to rows, even if the drawing area is split vertically.
- Input: array of sibling nodes, row, rectable (drawing area)
- sort the children nodes in descending order
- if the function is called for an empty array of sibling nodes, layout the row
- otherwise
- get first child node from array
- if the row is empty, add the child node to the row, and call squarified with the remaining siblings
- otherwise
- if aspect ratio becomes not worse by inserting node, add to row and call squarified with remaining sibling nodes
- otherwise layout the row, call squarified with remaining sibling nodes and an empty row
Remarks
-
The main loop over the children nodes is called recursively.
The function is called with the children nodes.
-
The layout of the sibling nodes is called recursively.
The function is called with the remaining sibling nodes.
- The rectangular drawing area is split along the longest side
The JavaScript Code