title: 四叉樹算法
date: 2016-1-11 15:10
categories: IOS

tags: 算法

小小程序猿
我的博客：http://daycoding.com

轉載：http://blog.csdn.net/zhanxinhang/article/details/6706217

高德iOS聚合實例

高德Android聚合實例

四叉樹或四元樹也被稱為Q樹（Q-Tree）。四叉樹廣泛應用于圖像處理、空間數據索引、2D中的快速碰撞檢測、存儲稀疏數據等，而八叉樹（Octree）主要應用于3D圖形處理。對游戲編程，這會很有用。本文著重于對四叉樹與八叉樹的原理與結構的介紹，幫助您在腦海中建立四叉樹與八叉樹的基本思想。本文并不對這兩種數據結構同時進行詳解，而只對四叉樹進行詳解，因為八叉樹的建立可由四叉樹的建立推得。

四叉樹與八叉樹的結構與原理
四叉樹（Q-Tree）是一種樹形數據結構。四叉樹的定義是：它的每個節點下至多可以有四個子節點，通常把一部分二維空間細分為四個象限或區域并把該區域里的相關信息存入到四叉樹節點中。這個區域可以是正方形、矩形或是任意形狀。以下為四叉樹的二維空間結構(左)和存儲結構(右)示意圖（注意節點顏色與網格邊框顏色）：

四叉樹的每一個節點代表一個矩形區域（如上圖黑色的根節點代表最外圍黑色邊框的矩形區域），每一個矩形區域又可劃分為四個小矩形區域，這四個小矩形區域作為四個子節點所代表的矩形區域。
較之四叉樹，八叉樹將場景從二維空間延伸到了三維空間。八叉樹（Octree）的定義是：若不為空樹的話，樹中任一節點的子節點恰好只會有八個，或零個，也就是子節點不會有0與8以外的數目。那么，這要用來做什么？想象一個立方體，我們最少可以切成多少個相同等分的小立方體？答案就是8個。如下八叉樹的結構示意圖所示：

/* 一個矩形區域的象限劃分：:UL(1)   |    UR(0)----------|-----------LL(2)   |    LR(3)
以下對該象限類型的枚舉
*/
typedef enum
{UR = 0,UL = 1,LL = 2,LR = 3
}QuadrantEnum;/* 矩形結構 */
typedef struct quadrect_t
{    double  left, top, right, bottom;
}quadrect_t;/* 四叉樹節點類型結構 */
typedef struct quadnode_t
{quadrect_t    rect;          //節點所代表的矩形區域list_t        *lst_object;   //節點數據, 節點類型一般為鏈表，可存儲多個對象struct  quadnode_t  *sub[4]; //指向節點的四個孩子 
}quadnode_t;/* 四叉樹類型結構 */
typedef struct quadtree_t
{quadnode_t  *root;int         depth;           // 四叉樹的深度                    
}quadtree_t;

四叉樹的建立

利用四叉樹分網格，如本文的第一張圖<四層完全四叉樹結構示意圖>，根據左圖的網格圖形建立如右圖所示的完全四叉樹。

偽碼：

Funtion QuadTreeBuild ( depth, rect ){
QuadTree->depth = depth;/*創建分支，root樹的根，depth深度，rect根節點代表的矩形區域*/
QuadCreateBranch (  root, depth, rect );}Funtion QuadCreateBranch ( n, depth,rect ){
if ( depth!=0 ){
n = new node;    //開辟新節點
n ->rect = rect; //將該節點所代表的矩形區域存儲到該節點中
將rect劃成四份 rect[UR], rect[UL], rect[LL], rect[LR];/*創建各孩子分支*/
QuadCreateBranch ( n->sub[UR], depth-1, rect [UR] );
QuadCreateBranch ( n->sub[UL], depth-1, rect [UL] );
QuadCreateBranch ( n->sub[LL], depth-1, rect [LL] );
QuadCreateBranch ( n->sub[LR], depth-1, rect [LR] );}}

假設在一個矩形區域里有N個對象，如下左圖一個黑點代表一個對象，每個對象的坐標位置都是已知的，用四叉樹的一個節點存儲一個對象，構建成如下右圖所示的四叉樹。

方法也是采用遞歸的方法對該矩形進行劃分分區塊，分完后再往里分，直到每一個子矩形區域里只包含一個對象為止。
偽碼：

Funtion QuadtreeBuild(){Quadtree = {empty}；For (i = 1;i<n;i++)      //遍歷所有對象
{QuadInsert(i, root)；//將i對象插入四叉樹
}          剔除多余的節點；       //執行完上面循環后，四叉樹中可能有數據為空的葉子節點需要剔除}    Funtion QuadInsert(i,n)      //該函數插入后四叉樹中的每個節點所存儲的對象數量不是1就是0{  if（節點n有孩子）{      通過劃分區域判斷i應該放置于n節點的哪一個孩子節點c；       QuadInsert(i,c)；}else if（節點n存儲了一個對象）{為n節點創建四個孩子；將n節點中的對象移到它應該放置的孩子節點中；通過劃分區域判斷i應該放置于n節點的哪一個孩子節點c；QuadInsert(i,c)；}else if（n節點數據為空）    {將i存儲到節點n中；}} 

用四叉樹查找某一對象

1、采用盲目搜索，與二叉樹的遞歸遍歷類似，可采用后序遍歷或前序遍歷或中序遍歷對其進行搜索某一對象，時間復雜度為O（n）。

2、根據對象在區域里的位置來搜索，采用分而治之思想，時間復雜度只與四叉樹的深度有關。比起盲目搜索，這種搜索在區域里的對象越多時效果越明顯

Funtion find ( n, pos, ){If (n節點所存的對象位置為 pos所指的位置 )Return n;If ( pos位于第一象限 )temp = find ( n->sub[UR], pos );else if ( pos位于第二象限)temp = find ( n->sub[UL], pos );else if ( pos位于第三象限 )temp = find ( n->sub[LL], pos );else  //pos 位于第四象限temp = find ( n->sub[LR], pos );return temp;   }