分块排序的正方化树图布局算法

A Squarified Treemap Layout Algorithm using Block-based Sorting

针对正方化树图布局算法中乱序和稳定性差的问题,提出分块排序的正方化算法Squarified-SP.首先根据待绘制矩形区域的长宽比和用户允许乱序的矩形个数将原始数据集划分为多个子集;再根据各数据元素的权值,采用权值均分的原则按顺序依次将其归并到相应的子集,形成对应的多个矩形子块;最后,在子块内采用正方化自适应的算法排列各元素.与原始正方化算法进行比较分析的实验结果表明,该算法在维持长宽比的基础上,保持了块间元素的顺序且提高了树图布局的稳定性,适用于对含有顺序信息的大规模层次数据的可视化.

This paper presents a new squarified treemap layout algorithm that addresses the challenging problems of disordering and instability of traditional solutions by employing a novel block-based sorting scheme. The input dataset is first divided into several subsets according to the aspect ratio of the drawing area and the number of allowed disordered rectangles. Then, each data element is sequentially assigned to its corresponding subset by considering the weights of individual elements, by which the drawing area is partitioned accordingly. Finally, each element within each part is positioned using the squarified self-adaption algorithm. Experimental results indicate that our approach can maintain the order of input data elements and improve the layout stability while maintaining better aspect ratio compared with conventional squarified algorithm, and can be applied to ordered large-scale hierarchical datasets.