雙曲樹(英語: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 

外部連結

編輯