I recently had a requirement to deal with displaying groups of dynamic data in Silverlight. The data will come in a variable number of groups, with a variable number of items in each group. In order to display all items correctly, groups that have more items in require more screen real estate than those with less items. Whilst thinking through how I might spilt up the available screen space in that manner, it occurred to me that what I was essentially trying to create was a Treemap. Generally speaking, a treemap is a type of graph - filling a given area with rectangles that vary in size to represent their relative value.
Whilst doing some research into how treemaps are constructed I came across an old article on Code Project from 2004 where a chap had taken a somewhat obscure mathematical paper on a Squarified Treemap Algorithm from a Dutch University and created a C# implementation to run on Longhorn (this was 2004). Now I’m sure Jonathan Hodgson (who wrote the Code Project article) won’t mind me saying his code was largely a prototype and logically not very close to the original algorithm.
I decided to revert back to the original mathematical algorithm and try and come up with something that closely resembled it in C#. Whilst the algorithm in the paper deals with calculating how many rectangles each row should contain and their size, it does not address plotting the results – so I also wanted to deal with this side of the puzzle (the call to LayoutRow).
I was keen that the core algorithm be fairly independent of UI largely because I wasn’t going to use the output to actually draw a treemap (just designate areas of the screen in which to place other items) but also to make it portable to other platforms. There’s nothing in the core algorithm I’ve written that couldn’t be ported to WPF or ASP.Net, or any other .Net environment very easily. The output is a collection of Rect objects – which the consumer can use as they wish – be it to actually draw a Treemap or not. The input is simply a list of values you want to plot and the dimensions of the area you want the Treemap to fill.
I’m not going to step through all the gory details of the code (you can download the source below and do that yourself) – but after a fair bit of reading, thinking and a few pages of pseudo code I think I’ve come up with something pretty close to the original, or at least not bad for a first attempt. (If you’re reading the source code along side the maths paper – I’ve renamed the function Worse to CalculateAspectRatio – otherwise the naming is pretty much the same).
You can play with the result below and download the source code beneath that: