WhatRoute Help

Aspect Layout

The Aspect treemap layout algorithm is a simplification of the squarify algorithm described at http://www.win.tue.nl/~vanwijk/stm.pdf

The algorithm is as follows (my Swift implementation is also shown)

1. Given a list (sorted) of items to be displayed and the rectangle into which they will be rendered.
2. If the list is empty then return to the caller.
3. If the list contains a single item, then render it in the bounds of the input rectangle.
4. Add items to a list (L1) until the aspect ratio[i] of the rectangle that encloses this list is less than or equal to the aspect ratio of the remaining unoccupied area. Unlike the squarify algorithm, there is no requirement to descend into L1 to discover the 'worst' aspect ratio.
5. If the aspect ratio of the occupied rectangle is always greater then the unoccupied rectangle (i.e. all input items are now in L1), then replace L1 by a list containing just the first item from the input list.
6. The items not in L1 are stored in a second list L2.
7. Calculate the rectangles required to display L1 and L2.
8. Apply the aspect algorithm recursively to each of L1 and L2 from step 1.

[i] The aspect ratio for a rectangle r is

    max(r.width/r.height, r.height/r.width)

Swift Implementation

    func aspectLayout(_ items: TreemapItemList<T>, _ rect: NSRect)
    {
        func aspect_ratio(_ r: NSRect) -> Double
        {
            let ratio = max(r.width / r.height, r.height / r.width)
            return Double(ratio)
        }

        func splitRect(_ rect: NSRect, _ scale: Double, _ r1: inout NSRect, _ r2: inout NSRect)
        {
            r1 = rect
            r2 = rect

            if rect.width >= rect.height {
                r1.size.width *= CGFloat(scale)

                r2.origin.x += r1.width
                r2.size.width = rect.width - r1.width
            } else {
                r1.size.height *= CGFloat(scale)

                r2.origin.y += r1.height
                r2.size.height = rect.height - r1.height
            }
        }

        if isLastItem(items, rect, aspectLayout) {
            return
        }

        let totalWeight =  items.weight
        var split = 0

        for i in 0 ..< items.count - 2 {
            let l1 = items.sublist(first: 0, last: i)

            var r1 = rect
            var r2 = rect

            let scale = l1.weight / totalWeight
            splitRect(rect, scale, &r1, &r2)

            let a1 = aspect_ratio(r1)
            let a2 = aspect_ratio(r2)

            if a1 <= a2 {
                split = i
                break
            }
        }

        var r1 = rect
        var r2 = rect
        let l1 = items.sublist(first: 0, last: split)
        let l2 = items.sublist(first: split + 1, last: items.count - 1)
        let scale = l1.weight / totalWeight

        splitRect(rect, scale, &r1, &r2)

        aspectLayout(l1, r1)
        aspectLayout(l2, r2)
    }