矩形树图实践

一. 什么是矩形树图？

矩形树图由马里兰大学教授Ben Shneiderman于上个世纪90年代提出，适合展示具有层级关系的数据，能够直观的体现同级之间的比较。从根节点开始，屏幕空间根据子节点数目被分为多个矩形，矩形面积对应节点的权重。每个矩形又按照相应节点的子节点递归进行分割，直到叶节点为止。

树到树图映射过程e.png

本次采用的是基于D3的treemap，采用了Squarified算法，最终效果如下：

矩形树图.png

数据结构是一个二层的tree，一个根节点和多个子节点。

Squarified算法

Squarified算法使得矩形尽量接近正方形，拥有更好的平均长宽比，从而避免Slice-and-dice算法的缺点。其思想是：

• 将子节点从大到小进行排列；(按照自定义的权重)
• 从权值最大的节点开始，按照沿最短边优先开始，紧靠左边或者上边的原则，分别从左到右或者从上到下开始填充。
• 当填充第i个子节点时，分别计算同行同列插入和新建一行/列这两种方式，对比第1到i-1个已填充矩形的平均长宽比，选择平均长宽比低（靠近1）的填充结果作为第i个子节点的填充方式。

以数据集{3，2，6，4，1，2，6}为例，绘制过程如下图所示。（论文中图例采用从下往上填充）

Squarified.png

采用了分治算法，基于递归完成。核心流程如下

    /**
     * 计算矩形数图布局。前提：items已按权重降序排列
     * @param items    待绘制树图节点数组
     * @param start    起始位置
     * @param end      终止位置
     * @param bounds   待填充矩形区域
     */
    public void layout(Mappable[] items, int start, int end, Rect bounds)
    {
        if (start>end) {
            return;
        }
        if(start == end) {
            items[start].setBounds(bounds);
        }

        this.mid = start;
        while (mid < end) {
            if (highestAspect(items, start, mid, bounds) > highestAspect(items, start, mid+1, bounds) ) {
                //同行同列继续
                mid++;
            } else {
                //布局[start,mid]元素。返回剩余区域
                Rect newBounds = layoutRow(items, start, mid, bounds);
                //继续递归计算布局
                layout(items, mid+1, end, newBounds);
            }
        }
    }

    /**
     * 计算矩形区域的最大宽高比
     * @param items
     * @param start
     * @param end
     * @param bounds
     * @return
     */
    public double highestAspect(Mappable[] items, int start, int end, Rect bounds) {
        layoutRow(items, start, end, bounds);
        double max = Double.MIN_VALUE;
        for (int i = start; i <= end; i++) {
            if (items[i].getBounds().aspectRatio() > max) {
                max = items[i].getBounds().aspectRatio();
            }
        }
        return max;
    }

    public Rect layoutRow(Mappable[] items, int start, int end, Rect bounds) {
        boolean isHorizontal = bounds.w > bounds.h;
        double total = totalSize(items, start, items.length-1); //bounds.w * bounds.h; //
        double rowSize = totalSize(items, start, end);
        double rowRatio = rowSize / total;
        double offset=0;

        for (int i = start; i <= end; i++) {
            Rect r=new Rect();
            double ratio=items[i].getSize() / rowSize;

            if (isHorizontal) {
                r.x = bounds.x;
                r.w = bounds.w * rowRatio;
                r.y = bounds.y + bounds.h * offset;
                r.h = bounds.h * ratio;
            } else {
                r.x = bounds.x + bounds.w * offset;
                r.w = bounds.w * ratio;
                r.y = bounds.y;
                r.h = bounds.h * rowRatio;
            }
            items[i].setBounds(r);
            offset+=ratio;
        }
        if (isHorizontal) {
            return new Rect(bounds.x + bounds.w * rowRatio, bounds.y, bounds.w - bounds.w * rowRatio, bounds.h);
        } else {
            return new Rect(bounds.x, bounds.y + bounds.h * rowRatio, bounds.w, bounds.h - bounds.h * rowRatio);
        }
    }


    public static double totalSize(Mappable[] items) {
        return totalSize(items, 0, items.length - 1);
    }

    public static double totalSize(Mappable[] items, int start, int end) {
        double sum = 0;
        for (int i = start; i <= end; i++)
            sum += items[i].getSize();
        return sum;
    }

参考文档：
从零“可视化”一个矩形树图
D3矩形树图布局算法研究
squarified算法
https://github.com/peterdmv/treemap/blob/master/src/main/java/pd/treemap/TreemapLayout.java
https://github.com/rmtheis/android-treemap