刘旭

(SAP中国研究院 商务智能部,上海 201203)

基于深度优先搜索的正方化树图布局算法①

刘旭

(SAP中国研究院 商务智能部,上海 201203)

正方化布局算法在树图可视化形式中得到广泛使用,然而经典正方化树图布局算法无法获得平均长宽比最优的结果.通过分析经典正方化树图布局算法的实现细节,特别是每一步矩形块位置的选择过程,论证了经典正方化算法由于使用贪心算法原理导致的缺陷,结合深度优先搜索技术,提出了基于深度优先搜索的正方化树图布局算法(DSS算法).在详细阐述DSS算法实现过程的基础上,结合实证研究,对DSS算法在平均长宽比方面的优势,时间性能的改进方向和本质特点进行了深入探讨.

可视化;树图;正方化;深度优先;搜索

层次数据的常见可视化形式是树形图,然而树形图的连接线段之间存在大量空白无法利用,当数据量增加时,子结点会逐渐密集排列在一起,从而难以区分.Treemap(树图)使用具有一定面积的块来表示数据结点,而利用结点之间的位置关系来表示数据之间的层次关系[1].相对于树形图,Treemap的优点是充分利用了空间[2],可以通过结点的大小,颜色表示数据的各种属性[3],同时,Treemap的结点位置还可以表示数据的分布关系[4].

Treemap的基本形式是用一个矩形区域表示根结点,将根结点划分为多个矩形区域以表示子结点,这样递归地表示整个层次结构数据[5].图1描述了一个Treemap的生成步骤[6].基本布局算法是Treemap绘制过程中必须首……