fbpx
维基百科

双曲树

五月 23, 2024

双曲树（英語：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 

外部链接 编辑

 
维基共享资源上的相关多媒体资源：双曲树
  • d3-hypertree （页面存档备份，存于互联网档案馆） – HTML5 Hyperbolic tree implementation, MIT licensed
  • Hyperbolic Tree of life （页面存档备份，存于互联网档案馆） – Open source tree of life visualisation using Open Tree of Life data set
  • The Green Tree of Life （页面存档备份，存于互联网档案馆） – Tree of life – University of California at Berkeley and Jepson Herbaria
  • Similar to the above, but with pictures
  • RougeViz （页面存档备份，存于互联网档案馆） supports hyperbolic trees.

五月 23, 2024
双曲树, 英語, hyperbolic, tree, 是一种信息可视化和图形绘制方法, 其灵感来自双曲几何, 一个基本的, 聚焦的节点被放置在中心, 并给予更多的空间, 而非聚焦的节点则被压缩在边界附近, 聚焦其他的节点会把它和它的子节点带到圆盘的中心, 而树上不关注的部分则被压缩, 将分层数据显示为一棵树, 由于每层的节点数量会呈指数级增长, 因此会出现视觉上的混乱, 对于一棵简单的二叉树来说, 层的最大节点数是, 而分支较多的树的节点数增长得更快, 因此, 把树画成一个节点, 链接图需要指数级的空间来显示, 解. 双曲树 英語 hyperbolic tree 是一种信息可视化和图形绘制方法 其灵感来自双曲几何 一个基本的双曲树 聚焦的节点被放置在中心 并给予更多的空间 而非聚焦的节点则被压缩在边界附近 聚焦其他的节点会把它和它的子节点带到圆盘的中心 而树上不关注的部分则被压缩 将分层数据显示为一棵树 由于每层的节点数量会呈指数级增长 因此会出现视觉上的混乱 对于一棵简单的二叉树来说 第 n 层的最大节点数是 2n 而分支较多的树的节点数增长得更快 因此 把树画成一个节点 链接图需要指数级的空间来显示 解决上述问题的其中一种方法是使用双曲树 首先由Lamping等人提出 1 双曲树采用双曲空间 其本质上比欧氏空间的 空间更大 例如 在欧几里得空间中线性增加一个圆的半径 其周长会线性增加 而在双曲空间中同样的圆 其周长会呈指数级增加 利用这一特性 可以在双曲空间中以整洁的方式给树布局 把一个节点放在离其父节点足够远的地方 可以让该节点几乎拥有与其父节点相同的空间来布局自己的子节点 通常利用双曲几何的庞加莱圆盘模型来展示双曲树 尽管也可以使用凯莱 克莱因模型 两者都是在一个单位圆盘中显示整个双曲平面 使整个树一次性可见 单位圆盘提供了一个平面的鱼眼透镜视图 更加强调焦点内的节点 而在靠近圆盘边界处可以显示更加远离焦点的节点 遍历双曲树需要对空间进行莫比乌斯变换 使新的节点成为焦点 并将层次结构的更高层次移出视野 双曲树于1996年由施乐公司在美国申请了专利 但该专利已经过期 2 参见 编辑双曲几何 信息可视化 放射状树 英语 Radial tree 同样是圆形的 但使用线性几何 树 数据结构 树 图论 参考文献 编辑 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 US patent 5590250 Lamping John O amp Rao Ramana B Layout of node link structures in space with negative curvature 指定于Xerox Corporation 外部链接 编辑 nbsp 维基共享资源上的相关多媒体资源 双曲树 d3 hypertree 页面存档备份 存于互联网档案馆 HTML5 Hyperbolic tree implementation MIT licensed Hyperbolic Tree of life 页面存档备份 存于互联网档案馆 Open source tree of life visualisation using Open Tree of Life data set The Green Tree of Life 页面存档备份 存于互联网档案馆 Tree of life University of California at Berkeley and Jepson Herbaria Tree of life Similar to the above but with pictures RougeViz 页面存档备份 存于互联网档案馆 supports hyperbolic trees 取自 https zh wikipedia org w index php title 双曲树 amp oldid 71072180, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。