四叉樹
![本頁使用了標題或全文手工轉換](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
四叉樹 | |||||
---|---|---|---|---|---|
類型 | 樹 | ||||
發明時間 | 1974年 | ||||
發明者 | 拉斐爾·芬克爾、喬恩·本特利 | ||||
用大O符號表示的時間複雜度 | |||||
|
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/8/8b/Point_quadtree.svg/300px-Point_quadtree.svg.png)
四元樹(英語:Quadtree)是一種樹狀資料結構,在每一個節點上會有四個子區塊。四元樹常應用於二維空間資料的分析與分類。 它將資料區分成為四個象限。資料範圍可以是方形或矩形或其他任意形狀。這種資料結構是由 拉斐爾·芬克爾與喬恩·本特利在1974年發展出來。類似的資料分割方法也稱為 Q-tree。所有的四元樹法有共同之特點:
- 可分解成為各自的區塊
- 每個區塊都有節點容量。當節點達到最大容量時,節點分裂
- 樹狀資料結構依造四元樹法加以區分
形態
四元樹可以用他們資料形態的表示法來作分類,資料形態的項目有:區域、點、直線及曲線。四元樹也可以進行分類,不管樹的形態是否獨立於已處理過的排秩資料。一些四元樹的形態如下所示:
四元樹區塊
四元樹區塊表示為空間的分割,即在二維上分割區塊為四組相同的象限、次象限等,且每個葉節點包含有關特殊次區塊的資料。樹里的每個節點不是正好有4個子節點,就是沒有子節點(為一個樹葉節點)。四元樹區塊不是嚴格的一顆'樹' - 且位置的次分割與資料無關。他們是比較精確一些稱為'單詞查找樹'.
在一個深度為n的四元樹區塊中可以用來表示一個影像包含有2n × 2n的畫素,每個畫素的值為0或1。根節點表示全部影像區塊。假如畫素在任何區塊不是全部為0或1,那就可以進行畫分。在這個應用中,每個葉節點代表一個段落的畫素、段落畫素裡面包含全部為零或全部為一的組合。
四元樹區塊也可以用為一種資料區塊上不同變化解析的表達法。比如,溫度在一個區塊中可以儲存為一個四元樹,而樹葉節點儲存著平均溫度涵蓋到它所擁有的次區塊。
假如四元樹區塊被用來表達一組點資料(諸如一組城市的經緯度),區塊就進行次分割直到每個葉節點包含最多一個單點。
點四元樹
點四元樹修改自二叉樹用來表示二維的點資料。點四元樹與四元樹都有共同的特點,不過於次分割的中心總是在一點時、點四元樹視為一真樹(true tree)。樹的形態根據編過序的資料而定。在比較二維規律資料點上是相當有效率的,經常運作在O(log n)的時間複雜度內。
點四元樹的節點結構
點四元樹的節點類似於二叉樹的節點,它們之間的主要差別在於點四元樹有4個指標(每一個象限一個指標)、而一般二叉樹只有2個指標(左指標及右指標)。點四元樹的鍵值也是經常被分解為兩部分,如在直角坐標上的 x 及 y 值。因此,一個節點包含下列資訊:
- 4個指標(Pointer):quad[『NW』](西北)、quad[『NE』](東北)、quad[『SW』](西南)、及quad[『SE』](東南)。
- 點;含有如下項目:
- 鍵值;通常以直角座標(x, y)值來表示。
- 值;比如是"名字"。
邊四元樹
邊四元樹是專門用來儲存直線而不是點。曲線能分割每格到很接近精細的解析度。如此能產生極度的不平衡樹,而此不平衡樹可能推翻索引的使用目的。
一些四元樹的常用法
- 圖像表示法
- 空間索引(Spatial index)。
- 在二維的有效率之碰撞偵測(collision detection)。
- 地形資料的隱藏面決定(Hidden surface determination)。
- 儲存分散資料,諸如試算表(spreadsheet)、或著一些矩陣計算的格式化資訊。
- 多維場的解法。(計算流體力學, 電磁學)
- 生命遊戲模擬程式。[1]
- 毒瘤資料結構
四元樹為八叉樹的二維類比。
區辨說明
假如幾何次分割不能減縮每個四元樹的項目數時,(例如,在資料重疊時)則四元樹的次分割失敗,為了使演算法能夠繼續進行其容量必須突破限制。比如,一個四元樹最大的容量為8,而且有9個點在(0, 0),次分割將會造成3個空的四元樹,且每個空四元樹會包含最初的9個點,再次分割依此類推。因為樹必須允許在這樣的象限內超過8點,如此四元樹對帶有任意幾何(比如:地圖或圖形)的資料集才能夠達到O(N)的時間複雜度。
註釋
- ^ Tomas G. Rokicki. An Algorithm for Compressing Space and Time. 2006-04-01 [2009-05-20]. (原始內容存檔於2012-10-02).
參考資料
- Raphael Finkel and J.L. Bentley. Quad Trees: A Data Structure for Retrieval on Composite Keys. Acta Informatica. 1974, 4 (1): 1–9. doi:10.1007/BF00288933.
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf. Computational Geometry 2nd revised edition. Springer-Verlag. 2000. ISBN 3-540-65620-0. Chapter 14: Quadtrees: pp.291–306.
參看
- 八叉樹
- 二叉空間分割(Binary space partitioning)
- k-d樹(Kd-tree)
- R樹(R-tree)
- UB樹(UB-tree)
- 空間索引(Spatial index)
- 空間資料庫(Spatial database)
外部連結
- A discussion of the Quadtree and an application(頁面存檔備份,存於網際網路檔案館) (英文)
- Considerable discussion and demonstrations of Spatial Indexing (英文)
|