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

Squarified Treemap Layout Algorithm Based on Depth-First Search
Author:
  • 摘要
  • | |
  • 访问统计
  • |
  • 参考文献 [15]
  • |
  • 相似文献
  • | | |
  • 文章评论
    摘要:

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

    Abstract:

    Squarified layout algorithm is widely used in the Treemap Visualization, but classic Squarified algorithm cannot achieve the best average aspect ratio. By analyzing implementation details of Squarified Treemap layout algorithm, especially each step of the rectangular block position selection process, the paper demonstrates the drawback of classic Squarified algorithm caused by using greedy algorithm. Combining with depth-first search technique, it also proposes Squarified Treemap layout algorithm based on depth-first search (DSS algorithm). Based on elaborating implementation process of DSS algorithm, combining empirical research, the advantage of the DSS algorithm in the aspect ratio, the improvement direction and the essential characteristics of the time performance are discussed.

    参考文献
    1 Bederson BB, Shneiderman B, Wattenberg M. Ordered and quantum treemaps:Making effective use of 2D space to display hierarchies. ACM Trans. on Graphics (TOG), 2002, 21(4):833-854.
    2 Chintalapani G, Plaisant C, Shneiderman B. Extending the utility of treemaps with flexible hierarchy. Proc. Eighth International Conference on Information Visualisation, 2004(IV 2004). IEEE. 2004. 335-344.
    3 Vliegen R, Van Wijk JJ. Visualizing business data with generalized treemaps. IEEE Trans. on Visualization and Computer Graphics, 2006, 12(5):789-796.
    4 Balzer M, Deussen O, Lewerentz C. Voronoi treemaps for the visualization of software metrics. Proc. of the 2005 ACM Symposium on Software Visualization. ACMF. 2005. 165-172.
    5 Tu Y, Shen HW. Visualizing changes of hierarchical data using treemaps. IEEE Trans. on Visualization and Computer Graphics, 2007, 13(6):1286-1293.
    6 陈谊,胡海云,李志龙.树图布局算法的比较与优化研究.计算机辅助设计与图形学学报,2013,25(11):1623-1634.
    7 张昕,袁晓如.树图可视化.计算机辅助设计与图形学学报, 2012,24(9):1113-1124.
    8 Bruls M, Huizing K, Van Wijk JJ. Squarified treemaps. Springer. 2000.
    9 谷建涛,周哲,曹建亮.基于正方化算法的树图生成方法研究. 计算机应用与软件,2008,25(7):74-76.
    10 Shneiderman B, Wattenberg M. Ordered treemap layouts. IEEE Symposium on Proc. of the Information Visualization. IEEE Computer Society. 2001. 73.
    11 Engdahl B. Ordered and unordered treemap algorithms and their applications on handheld devices[Master's Thesis]. Department of Numerical Analysis and Computer Science, Stockholm Royal Institute of Technology, 2005.
    12 周哲.双向正方化树图生成算法[硕士学位论文].长沙:湖南大学,2005.
    13 Russell SJ, Norvig P, Canny JF, et al. Artificial intelligence:A modern approach. Prentice hall Upper Saddle River, 2003.
    14 刘旭.ChromeV8引擎中的JavaScript数组实现分析与性能优化.计算机与现代化,2014,(10):66-70.
    15 Tamassia R. Handbook of graph drawing and visualization. CRC press, 2013.
    相似文献
    引证文献
    网友评论
    网友评论
    分享到微博
    发 布
引用本文

刘旭.基于深度优先搜索的正方化树图布局算法.计算机系统应用,2017,26(5):105-112

复制
分享
文章指标
  • 点击次数:2392
  • 下载次数: 3523
  • HTML阅读次数: 0
  • 引用次数: 0
历史
  • 收稿日期:2016-08-02
  • 最后修改日期:2016-09-27
  • 在线发布日期: 2017-05-13
文章二维码
您是第11230479位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京海淀区中关村南四街4号 中科院软件园区 7号楼305房间,邮政编码:100190
电话:010-62661041 传真: Email:csa (a) iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号