Squarified Treemap

Algorithm

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

Example

如图所示，数据为 [6, 6, 4, 3, 2, 2, 1] , sum = 24 = 6 * 4 所以 treemap 可用 $6×4$ 的矩形表示。

1. 放入 6，优先靠着短边放，比例为 4:1.5， 标记灰色(表示可更改)。
2. 放入 6，测试与原先放置的 6 堆叠，靠着短边放，所得 2 个 $2×3$ 的矩形，长边:短边=3:2 ，小于 4:1.5 的放置方式。可取，同时加入灰色标记。
3. 放入 4， 如 Step 3 所示，max(长边:短边) in step3 > max(长边:短边) in step 4 ，故采取 Step 4 的放置方式，同时把原先标记灰色的部分画出来，标记白色(表示不可更改)。灰色清空，新加入的 4 标记灰色。
4. 循环方式如前述，最后把剩余空间填满。

代码采用递归，判断思路如上。

Major function code of the Algorithm

function squarify(children, modifiable, w, h, sum, m_area) {
            //console.log("current in: ",children[0], modifiable);
            if(children.length === 0){
                console.log("quit");
                var to_right = modifiable[0].verti;
                draw(modifiable, to_right);// ..............
                return;
            }
            var c = children.shift();
            var _area = c, _wid, _hei, verti;
            if(modifiable.length === 0) {
                //console.log("case 0");
                m_area += c;
                if(w <= h) {// vertical set
                    _wid = w;
                    verti = true;
                    _hei = c / _wid;
                }
                else {// horizontal set
                    _hei = h;
                    _wid = c / _hei;
                    verti = false;
                }
                modifiable.push({_area,_wid,_hei,verti});
                squarify(children,modifiable,w,h,sum, m_area);
            }
            else {
                //case 1
                var leftover = sum - m_area;
                var neww, newh;
                if (w > h) {
                    neww = leftover / h;
                    newh = h;
                }
                else {
                    neww = w;
                    newh = leftover / w;
                }
                if (neww <= newh){// vertical set
                    _wid = neww;
                    _hei = c / _wid;
                    verti = true;
                }
                else{// horizontal set
                    _wid = c / newh;
                    _hei = newh;
                    verti= false;
                }
                //console.log("w,h",_wid,_hei);
                var temp1 = Math.max(_wid,_hei)/Math.min(_wid,_hei);// put in new area

                // case 2
                var temp_area = m_area + c;// else include in old area
                var w1, h1, temp2;
                if(w > h) {
                    w1 = temp_area / h;
                    h1 = h;
                }
                else {
                    w1 = w;
                    h1 = temp_area / w;
                }
                if(w1 <= h1){// stack up, width is the same
                    console.log("current 1", w1, h1);
                    temp2 = Math.max(w1,c/w1)/Math.min(w1,c/w1);// put in old area, w1/(c/w1), wid:hei
                    for(var i = 0; i < modifiable.length; i++)
                        temp2 = Math.max(temp2, Math.max(w1,modifiable[i]._area/w1)/Math.min(w1,modifiable[i]._area/w1));
                }
                else{//stack right, height is the same
                    console.log("current 2", w1, h1);
                    temp2 = Math.max(h1,c/h1)/Math.min(h1,c/h1);
                    for(var i = 0; i < modifiable.length; i++)
                        temp2 = Math.max(temp2, Math.max(modifiable[i]._area/h1,h1)/Math.min(modifiable[i]._area/h1,h1));
                }
                //console.log("t1,t2",temp1,temp2);
                
                // case 1
                if (temp1 <= temp2){// clear all modifiable, draw
                    //console.log("case 1");
                    var to_right = true;
                    if(w <= h)
                        to_right = false;
                    draw(modifiable, to_right);// ..............
                    
                    modifiable = [];//clear it
                    modifiable.push({_area,_wid,_hei,verti});
                    squarify(children,modifiable,neww,newh,sum-m_area,_area);
                }
                //case 2
                else{// put in modifiable
                    //console.log("case 2");
                    if(w > h){
                        for(var i = 0; i < modifiable.length; i++){
                            var cur_area = modifiable[i]._area;
                            var h_tem = cur_area / w1;
                            modifiable[i]._wid = w1;
                            modifiable[i]._hei = h_tem;
                            modifiable[i].verti = true;
                        }
                        _wid = w1;
                        _hei = c / _wid;
                        verti = true;
                    }
                    else{
                        for(var i = 0; i < modifiable.length; i++){
                            var cur_area = modifiable[i]._area;
                            var w_tem = cur_area / h1;
                            modifiable[i]._wid = w_tem;
                            modifiable[i]._hei = h1;
                            modifiable[i].verti = false;
                        }
                        _wid = c / h1;
                        _hei = h1;
                        verti = false;
                    }
                    modifiable.push({_area,_wid,_hei,verti});
                    m_area += c;
                    squarify(children,modifiable,w,h,sum,m_area);
                }
            }
        }

Output

数据采用 javascript 的 Math.random() 随机生成，个数为 10 ，范围 1 到 100 。(可是这个函数生成的随机数不太随机……)

整体 Treemap 的长宽比固定为 3:2 ，其中一个生成效果图如下：

有点问题就是，如果随机生成的这些数十分接近的话，会变成堆叠的长矩形……

Source Code

<html>
    <meta charset="utf-8">
    <header>treemap</header>
    <body>
    <svg id="svgOne" viewBox="0 0 610 410" xmlns="http://www.w3.org/2000/svg"></svg>
    <script>
        var margin = {top: 10, right: 10, bottom: 10, left: 10},
          width = 600 - margin.left - margin.right,
          height = 400 - margin.top - margin.bottom;

        var last_vert = true, beginx = margin.left, beginy = margin.top;

        var colori = 0;
        var colorset = ['#ABDE9C','#5EAC39', '#688F30', '#256E4B', '#285D77', '#3A6CAD', '#489CC2',
        '#D4A77F', '#E1CBA6', '#EBECC6', '#E3F2D8', '#EDC9DB', '#CFB5E6', '#ADA8E2'];

        var randtimes = 10, maxrand = 100;
        var data = [];
        for(var i = 0; i < randtimes; i++)
            data.push(Math.floor((Math.random() * maxrand) + 1));

        //var data = [2, 4, 23, 33, 69, 90, 54, 22, 61, 34, 32];
        data.sort(function(a, b){return b - a});
        
        var sum = data.reduce(function(a, b){ return a + b; }, 0);
        console.log("data, sum", data, sum);
        //var tempsum = prime_factor(sum);
        //console.log("tempsum", tempsum);
        var tmpd = Math.sqrt(sum / 6);
        var ori_w = 3 * tmpd, ori_h = 2 * tmpd;
        console.log("original wid, hei: ", ori_w, ori_h);
        var svgns = "http://www.w3.org/2000/svg";

        squarify(data,[],ori_w,ori_h,sum,0);

        function drawRect(x1, y1, w, h, area){
            var rect = document.createElementNS(svgns, 'rect');
            rect.setAttributeNS(null, 'x', x1);
            rect.setAttributeNS(null, 'y', y1);
            rect.setAttributeNS(null, 'height', h - 1);
            rect.setAttributeNS(null, 'width', w - 1);
            rect.setAttributeNS(null, 'fill', colorset[colori]);
            document.getElementById('svgOne').appendChild(rect);

            colori++;
            colori%=colorset.length;

            var newText = document.createElementNS(svgns,"text");
            newText.setAttributeNS(null,"x",x1+w/2-1);     
            newText.setAttributeNS(null,"y",y1+h/2-1); 
            newText.setAttributeNS(null,"font-size","12");
            var textNode = document.createTextNode(area);
            newText.appendChild(textNode);
            document.getElementById('svgOne').appendChild(newText);
        }

        function draw(rectangle, to_right){
            console.log(rectangle);
            var orix = beginx, oriy = beginy;
            var ratio1, ratio2;
            var sameDir = rectangle[0].vert;
            if(sameDir == last_vert)
                sameDir = true;
            else
                sameDir = false;
            for(var i = 0; i < rectangle.length; i++){
                var _area = rectangle[i]._area;
                var vert = rectangle[i].verti;
                last_vert = vert;
                var w = rectangle[i]._wid, h = rectangle[i]._hei;
                console.log("area, width, height, vert?", _area, w, h, vert);
                ratio1 = w/ori_w*width, ratio2 = h/ori_h*height;
                drawRect(beginx, beginy, ratio1, ratio2, _area);
                if(vert == true){
                    beginy += ratio2;
                }
                else{
                    beginx += ratio1;
                }
            }
            
            if(to_right == false){// to below
                beginx = orix;
                beginy = oriy + ratio2;
            }
            else {//to right
                beginx = orix + ratio1;
                beginy = oriy;
            }
        }

        // assume w > h, put in h first
        function squarify(children, modifiable, w, h, sum, m_area) {
            //console.log("current in: ",children[0], modifiable);
            if(children.length === 0){
                console.log("quit");
                var to_right = modifiable[0].verti;
                draw(modifiable, to_right);// ..............
                return;
            }
            var c = children.shift();
            var _area = c, _wid, _hei, verti;
            if(modifiable.length === 0) {
                //console.log("case 0");
                m_area += c;
                if(w <= h) {// vertical set
                    _wid = w;
                    verti = true;
                    _hei = c / _wid;
                }
                else {// horizontal set
                    _hei = h;
                    _wid = c / _hei;
                    verti = false;
                }
                modifiable.push({_area,_wid,_hei,verti});
                squarify(children,modifiable,w,h,sum, m_area);
            }
            else {
                //case 1
                var leftover = sum - m_area;
                var neww, newh;
                if (w > h) {
                    neww = leftover / h;
                    newh = h;
                }
                else {
                    neww = w;
                    newh = leftover / w;
                }
                if (neww <= newh){// vertical set
                    _wid = neww;
                    _hei = c / _wid;
                    verti = true;
                }
                else{// horizontal set
                    _wid = c / newh;
                    _hei = newh;
                    verti= false;
                }
                //console.log("w,h",_wid,_hei);
                var temp1 = Math.max(_wid,_hei)/Math.min(_wid,_hei);// put in new area

                // case 2
                var temp_area = m_area + c;// else include in old area
                var w1, h1, temp2;
                if(w > h) {
                    w1 = temp_area / h;
                    h1 = h;
                }
                else {
                    w1 = w;
                    h1 = temp_area / w;
                }
                if(w1 <= h1){// stack up, width is the same
                    console.log("current 1", w1, h1);
                    temp2 = Math.max(w1,c/w1)/Math.min(w1,c/w1);// put in old area, w1/(c/w1), wid:hei
                    for(var i = 0; i < modifiable.length; i++)
                        temp2 = Math.max(temp2, Math.max(w1,modifiable[i]._area/w1)/Math.min(w1,modifiable[i]._area/w1));
                }
                else{//stack right, height is the same
                    console.log("current 2", w1, h1);
                    temp2 = Math.max(h1,c/h1)/Math.min(h1,c/h1);
                    for(var i = 0; i < modifiable.length; i++)
                        temp2 = Math.max(temp2, Math.max(modifiable[i]._area/h1,h1)/Math.min(modifiable[i]._area/h1,h1));
                }
                //console.log("t1,t2",temp1,temp2);
                
                // case 1
                if (temp1 <= temp2){// clear all modifiable, draw
                    //console.log("case 1");
                    var to_right = true;
                    if(w <= h)
                        to_right = false;
                    draw(modifiable, to_right);// ..............
                    
                    modifiable = [];//clear it
                    modifiable.push({_area,_wid,_hei,verti});
                    squarify(children,modifiable,neww,newh,sum-m_area,_area);
                }
                //case 2
                else{// put in modifiable
                    //console.log("case 2");
                    if(w > h){
                        for(var i = 0; i < modifiable.length; i++){
                            var cur_area = modifiable[i]._area;
                            var h_tem = cur_area / w1;
                            modifiable[i]._wid = w1;
                            modifiable[i]._hei = h_tem;
                            modifiable[i].verti = true;
                        }
                        _wid = w1;
                        _hei = c / _wid;
                        verti = true;
                    }
                    else{
                        for(var i = 0; i < modifiable.length; i++){
                            var cur_area = modifiable[i]._area;
                            var w_tem = cur_area / h1;
                            modifiable[i]._wid = w_tem;
                            modifiable[i]._hei = h1;
                            modifiable[i].verti = false;
                        }
                        _wid = c / h1;
                        _hei = h1;
                        verti = false;
                    }
                    modifiable.push({_area,_wid,_hei,verti});
                    m_area += c;
                    squarify(children,modifiable,w,h,sum,m_area);
                }
            }
        }
    </script>
    </body>
</html>