How to calculate optimal sizes of rectangles for this type of array visualization?

Question

Given array of positive numbers, I would like to draw this diagram and be able to put descriptions inside:

There should be no empty space left, consider that these numbers represent % of total.

Do you know name or description of such algorithm or library with implementation of it ?

Also I want this algorithm to work for nested numbers - when a rectangle has components inside with proper optimization of sizes and locations of outer and inner rectangles.

Visualization is considered optimal if descriptions are easily readable and areas are easily comparable between each other and also with enclosing rectangle. I believe these goals are achieved when these rectangles are closer to squares.

Does this algorithm needs to be iterative or it's possible to have a target formula for position and size of each rectangle ?

Answer 1

The algoritm you are looking for is called Squarified Treemap Algorithm.

---

Its description and discussion of related issues can be found in this paper by Mark Bruls, Kees Huizing, and Jarke J. van Wijk. The proposed algorithm is recursive in nature.

Key portion of the paper goes like this:

... Following the example, we present our algorithm for the layout of the children in one rectangle as a recursive procedure squarify. This procedure lays out the rectangles in horizontal and vertical rows. When a rectangle is processed, a decision is made between two alternatives. Either the rectangle is added to the current row, or the current row is fixed and a new row is started in the remaining subrectangle. This decision depends only on whether adding a rectangle to the row will improve the layout of the current row or not.

We assume a datatype Rectangle that contains the layout during the computation and is global to the procedure squarify. It supports a function width() that gives the length of the shortest side of the remaining subrectangle in which the current row is placed and a function layoutrow() that adds a new row of children to the rectangle. To keep the description simple, we use some list notation: ++ is concatenation of lists, [x] is the list containing element x, and [] is the empty list. The input of squarify() is basically a list of real numbers, representing the areas of the children to be laid out. The list row contains the rectangles that is currently being laid out. The functionworst() gives the highest aspect ratio of a list of rectangles, given the length of the side along which they are to be laid out. This function is further discussed below:

procedure squarify(list of real children, list of real row, real w)
begin
  real c = head(children);
  if worst(row, w)  worst(row++[c], w) then
    squarify(tail(children), row++[c], w)
  else
    layoutrow(row);
    squarify(children, [], width());
  fi
end

---

There is also this relevant question on SO:

https://stackoverflow.com/questions/9880635/implementing-a-squarified-treemap-in-javascript

Also, implementation in TypeScript is here. Its demo is here. Screenshot of the demo:

There is also an open source utility for disk space visualization called WinDirStat. It contains C++ implementation of the algorithm above. Its screenshot: