跳转到内容

双曲树

维基百科,自由的百科全书

双曲树(英语:hyperbolic tree)是一种信息可视化和图形绘制方法,其灵感来自双曲几何

一个基本的双曲树。聚焦的节点被放置在中心,并给予更多的空间,而非聚焦的节点则被压缩在边界附近。
聚焦其他的节点会把它和它的子节点带到圆盘的中心,而树上不关注的部分则被压缩。

将分层数据显示为一棵,由于每层的节点数量会呈指数级增长,因此会出现视觉上的混乱。对于一棵简单的二叉树来说,第 n 层的最大节点数是 2n,而分支较多的树的节点数增长得更快。因此,把树画成一个节点-链接图需要指数级的空间来显示。

解决上述问题的其中一种方法是使用双曲树,首先由Lamping等人提出。[1] 双曲树采用双曲空间,其本质上比欧氏空间的“空间更大”。例如,在欧几里得空间中线性增加一个圆的半径,其周长会线性增加,而在双曲空间中同样的圆,其周长会呈指数级增加。利用这一特性,可以在双曲空间中以整洁的方式给树布局:把一个节点放在离其父节点足够远的地方,可以让该节点几乎拥有与其父节点相同的空间来布局自己的子节点。

通常利用双曲几何的庞加莱圆盘模型来展示双曲树,尽管也可以使用凯莱-克莱因模型。两者都是在一个单位圆盘中显示整个双曲平面,使整个树一次性可见。单位圆盘提供了一个平面的鱼眼透镜视图,更加强调焦点内的节点,而在靠近圆盘边界处可以显示更加远离焦点的节点。遍历双曲树需要对空间进行莫比乌斯变换,使新的节点成为焦点,并将层次结构的更高层次移出视野。

双曲树于1996年由施乐公司在美国申请了专利,但该专利已经过期。[2]

参见

[编辑]

参考文献

[编辑]
  1. ^ Lamping, John Ogden; Rao, Ramana; Pirolli, Peter. A focus+context technique based on hyperbolic geometry for visualizing large hierarchies. Proceedings of the ACM Conference on Human Factors in Computing Systems (CHI 1995): 401–408. May 1995 [2021-04-13]. doi:10.1145/223904.223956. (原始内容存档于2017-05-10). 
  2. ^ US patent 5590250,Lamping; John O. & Rao; Ramana B.,“Layout of node-link structures in space with negative curvature”,指定于Xerox Corporation 

外部链接

[编辑]