Treemap::Squarified - Make a Treemap, using the squarified treemap algorithm.

See METHODS section of Treemap.

First, we sort the list of nodes at our current depth based on their area (or size), in descending order.

We then take the first node and find the aspect ratio for it's required area, then compare that to the aspect ratio of the first and second node added together, and so on, until the aspect ratio become non-ideal (when it exceeds one).

e.g.

The aspect ratio, W/H, in this case is < 1, so we would like to maximize our width 'X' to 'W' for area 'A', and then expand the height 'Y', until our area 'A' has the aspect ratio closest to 1.

     <---- W ---->     Calculating the Aspect ratio:

 ^   +-----------+     We know the value of A, and W
 |   |+---------+|     We also know that X = W
 |   ||         ||     
 |   ||    A    Y|     Therefore:  
 |   ||         ||           A = XY
 H   |+----X----+|           A = WY
 |   |           |           Y = A/W
 |   |           |
 |   |           |      Aspect = Width / Height
 V   +-----------+      Aspect = W / ( A / W )        
                        Aspect = W^2 / A

We would calculate the 'Aspect Ratio' of Node1 with area A1, and compare it to the 'Aspect Ratio' of Node 1 and Node 2, with area (A1+A2). Further nodes are added, until the aspect ratio becomes non-ideal.

If we were to plot the 'Aspect Ratio' as 'Y' was increased, we would get:

 Aspect
   |        ./
 1 |      ./ 
   |    ./  
   |  ./   
   |./    
   +---------- Y
 0        

If instead we take the inverse of the 'Aspect Ratio' when it is greater than one, we would get:

 Aspect
 1 |    
   |   /\     
   |  /  \  
   | /    \
   |/      \
   +---------- Y
 0        

This makes it easier to compare two aspect ratios when they span the perfect aspect ratio of 1.

None by default.

Treemap

The aspect ratios don't come out ideal when there is a large difference in size between objects at the same level. It might perform better if there was a 'look ahead' to see if the item currently being tested would fit better in the space being tested, or in the space that's left over.

Simon P. Ditner <simon@uc.org>, and Eric Maki <eric@uc.org>

Original Treemap Concept: Ben Shneiderman <ben@cs.umd.edu>, http://www.cs.umd.edu/hcil/treemap-history/index.shtml

Squarified Treemap Concept: Visualization Group of the Technische Universiteit Eindhoven

(c)2003