A squariifed treemap is a treemap that tries to minimize the aspect ratio of its rectangles, i.e. tries to make things as square as possible.

It’s perhaps most commonly used in a heatmap, like so:

Squarified Treemap

Finding the optimal (as square as possible) squarified treemap is an NP-hard problem, it would appear, but there’s a sinmple, greedy heuristic described in this paper that appears to achieve good results. An implementation in Elm follows.

Partition

Given a list of areas and a rectangle to fill, we want to partition the rectangle according to the list of areas (or “cells”). For convenience, the input cells are represented with the extensible record type alias HasArea a = { a | area : Float }, which just requires area to be in the record.

The paper uses the simple abstraction of a row to group cells together, where row can be subdivided either vertically or horizontally.

partition can be written as a fold over the input areas, where the below implementation has some additional code to work with List.Nonempty, imported as NE.

partition : Dimensions -> NE.Nonempty (HasArea a) -> NE.Nonempty (Row a)
partition dims areas =
    NE.tail areas
        |> List.foldl partitionHelper ( dims, NE.fromElement (NE.head areas), [] )
        |> (\( _, row, rows ) ->
                NE.Nonempty row rows
                    |> NE.map NE.reverse
                    |> NE.reverse
           )

The fold function implements the paper’s pseudocode almost directly (note that the paper contains a typo in the direction of the comparison operator of the if clause, which the authors know about). The main idea is to greedily add another cell to the current row, so long as the row’s worst aspect ratio does not worsen.


type alias PartitionAcc a =
    ( Dimensions, Row a, List (Row a) )


partitionHelper : HasArea a -> PartitionAcc a -> PartitionAcc a
partitionHelper area ( dims, row, rows ) =
    let
        w =
            Tuple.first <| sizeOrdered dims
    in
    if worst row w >= worst (NE.cons area row) w then
        ( dims, NE.cons area row, rows )

    else
        ( updateDims dims row, NE.fromElement area, row :: rows )

There is some housekeeping required to update the working dimensions as new rows are added. (See implementations of updateDims and worstt in the full code).

We can test partition with the example from the paper:

> import DataGrid.Internal.SquarifiedTreemap as ST
> import List.Nonempty as NE
>
> areas = NE.Nonempty 6 [6, 4, 3, 2, 2, 1] |> NE.map (\a -> { area = a })
>
> ST.partition { x = 6, y = 4 } areas
Nonempty
    ( Nonempty { area = 6 } [{ area = 6 }] )
    [ Nonempty { area = 4 } [{ area = 3 }]
    , Nonempty { area = 2 } []
    , Nonempty { area = 2 } []
    , Nonempty { area = 1 } []
    ]
    : NE.Nonempty (ST.Row {})

Because the algorithm always follows the shorter lenght of the remaining subrectangle, the above minimal representation of the partition result is all that’s needed to render the treemap.

Squarified Treemap

Given partition results, generating renderable cells (containing subrectangle x, y, width, and height information) is a matter of another fold, or, in the below, using mapAccumlL from Haskell to preserve the non-emptiness.


type alias SquarifiedTreemap a =
    NE.Nonempty (Cell a)


type alias Cell a =
    { x : Float
    , y : Float
    , w : Float
    , h : Float
    , cell : HasArea a
    }


type alias Origin =
    { x : Float
    , y : Float
    }


makeTreemap : Dimensions -> NE.Nonempty (HasArea a) -> SquarifiedTreemap a
makeTreemap dims areas =
    partition dims areas
        |> Utils.neMapAccumL rowToCells ( { x = 0, y = 0 }, dims )
        |> Tuple.first
        |> NE.concat

Since we now need the x and y for each cell, we need to track the current origin in addition to the current remaining subrectangle dimensions. The origin is shifted each time a row is completed (note that unlike the example in the paper, the origin is always increasing in this implementation).

updateOriginAndDims : Origin -> Dimensions -> Row a -> ( Origin, Dimensions )
updateOriginAndDims origin dims row =
    let
        dims_ =
            updateDims dims row

        origin_ =
            { x = origin.x + dims.x - dims_.x
            , y = origin.y + dims.y - dims_.y
            }
    in
    ( origin_, dims_ )

The rowToCells function is another fold that threads the origin and dimensions through the current row to draw each cell.

rowToCells : Row a -> ( Origin, Dimensions ) -> ( NE.Nonempty (Cell a), ( Origin, Dimensions ) )
rowToCells row ( origin, dims ) =
    let
        ( origin_, dims_ ) =
            updateOriginAndDims origin dims row

        delta =
            { x = dims.x - dims_.x
            , y = dims.y - dims_.y
            }

        cells =
            Utils.neMapAccumL rowToCellsHelper ( origin, delta ) row |> Tuple.first
    in
    ( cells, ( origin_, dims_ ) )

Running makeTreemap on the same input as above, we get a list of cells that are ready to render:

> ST.makeTreemap { x = 4, y = 6 } areas
Nonempty 
    { cell = { area = 6 }, h = 3, w = 2, x = 0, y = 0 }
    [ { cell = { area = 6 }, h = 3, w = 2, x = 2, y = 0 }
    , { cell = { area = 4 }, h = 1.7142857142857142, w = 2.3333333333333335, x = 0, y = 3 }
    , { cell = { area = 3 }, h = 1.2857142857142856, w = 2.3333333333333335, x = 0, y = 4.714285714285714 }
    , { cell = { area = 2 }, h = 1.2000000000000002, w = 1.6666666666666665, x = 2.3333333333333335, y = 3 }
    , { cell = { area = 2 }, h = 1.2000000000000002, w = 1.6666666666666665, x = 2.3333333333333335, y = 4.2 }
    , { cell = { area = 1 }, h = 0.5999999999999996, w = 1.6666666666666676, x = 2.3333333333333335, y = 5.4 }]
    : ST.SquarifiedTreemap {}