四元樹 是一種樹狀資料結構 ，在每一個節點上會有四個子區塊。四元樹常應用於二維空間資料的分析與分類。 它將資料區分成為四個象限 。資料範圍可以是方形或矩形或其他任意形狀。這種資料結構是由 拉斐爾·芬科爾(Raphael Finkel) 與 J. L. Bentley 在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
參看 八叉树 二叉空間分割 (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（页面存档备份，存于互联网档案馆 ） （英文） （英文）
四叉树, 四元樹是一種樹狀資料結構, 在每一個節點上會有四個子區塊, 四元樹常應用於二維空間資料的分析與分類, 它將資料區分成為四個象限, 資料範圍可以是方形或矩形或其他任意形狀, 這種資料結構是由, 拉斐爾, 芬科爾, raphael, finkel, bentley, 在1974年發展出來, 類似的資料分割方法也稱為, tree, 所有的四元樹法有共同之特點, 可分解成為各自的區塊, 每个区块都有节点容量, 当节点达到最大容量时, 节点分裂, 樹狀資料結構依造四元樹法加以區分四元樹區塊的點資料分布圖, 目录, . 四元樹是一種樹狀資料結構 在每一個節點上會有四個子區塊 四元樹常應用於二維空間資料的分析與分類 它將資料區分成為四個象限 資料範圍可以是方形或矩形或其他任意形狀 這種資料結構是由 拉斐爾 芬科爾 Raphael Finkel 與 J L Bentley 在1974年發展出來 類似的資料分割方法也稱為 Q tree 所有的四元樹法有共同之特點 可分解成為各自的區塊 每个区块都有节点容量 当节点达到最大容量时 节点分裂 樹狀資料結構依造四元樹法加以區分四元樹區塊的點資料分布圖 目录 1 形態 1 1 四元樹區塊 1 2 點四元樹 1 2 1 點四元樹的節點結構 1 3 邊四元樹 2 一些四元樹的常用法 3 區辨說明 4 註釋 5 參考資料 6 參看 7 外部連結形態 编辑四元樹可以用他們資料形態的表示法來作分類 資料形態的項目有 區域 點 直線及曲線 四元樹也可以進行分類 不管樹的形態是否獨立於已處理過的排秩資料 一些四元樹的形態如下所示 四元樹區塊 编辑 四元樹區塊表示為空間的分割 即在二維上分割區塊為四組相同的象限 次象限等 且每個葉節點包含有關特殊次區塊的資料 樹里的每個節點不是正好有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 引文格式1维护 冗余文本 link 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 英文 取自 https zh wikipedia org w index php title 四叉树 amp oldid 74822581, 维基百科，wiki ，书籍，书籍，图书馆，
文章 ，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。