四叉树和八叉树
前序
四叉樹(shù)或四元樹(shù)也被稱為Q樹(shù)（Q-Tree）。四叉樹(shù)廣泛應(yīng)用于圖像處理、空間數(shù)據(jù)索引、2D中的快速碰撞檢測(cè)、存儲(chǔ)稀疏數(shù)據(jù)等，而八叉樹(shù)（Octree）主要應(yīng)用于3D圖形處理。對(duì)游戲編程，這會(huì)很有用。本文著重于對(duì)四叉樹(shù)與八叉樹(shù)的原理與結(jié)構(gòu)的介紹，幫助您在腦海中建立四叉樹(shù)與八叉樹(shù)的基本思想。本文并不對(duì)這兩種數(shù)據(jù)結(jié)構(gòu)同時(shí)進(jìn)行詳解，而只對(duì)四叉樹(shù)進(jìn)行詳解，因?yàn)榘瞬鏄?shù)的建立可由四叉樹(shù)的建立推得。若有不足之處，望能不吝指出，以改進(jìn)之。^_^ ?歡迎Email：zhanxinhang@gmail.com
四叉樹(shù)與八叉樹(shù)的結(jié)構(gòu)與原理
四叉樹(shù)（Q-Tree）是一種樹(shù)形數(shù)據(jù)結(jié)構(gòu)。四叉樹(shù)的定義是：它的每個(gè)節(jié)點(diǎn)下至多可以有四個(gè)子節(jié)點(diǎn)，通常把一部分二維空間細(xì)分為四個(gè)象限或區(qū)域并把該區(qū)域里的相關(guān)信息存入到四叉樹(shù)節(jié)點(diǎn)中。這個(gè)區(qū)域可以是正方形、矩形或是任意形狀。以下為四叉樹(shù)的二維空間結(jié)構(gòu)(左)和存儲(chǔ)結(jié)構(gòu)(右)示意圖（注意節(jié)點(diǎn)顏色與網(wǎng)格邊框顏色）：
?
四叉樹(shù)的每一個(gè)節(jié)點(diǎn)代表一個(gè)矩形區(qū)域（如上圖黑色的根節(jié)點(diǎn)代表最外圍黑色邊框的矩形區(qū)域），每一個(gè)矩形區(qū)域又可劃分為四個(gè)小矩形區(qū)域，這四個(gè)小矩形區(qū)域作為四個(gè)子節(jié)點(diǎn)所代表的矩形區(qū)域。
較之四叉樹(shù)，八叉樹(shù)將場(chǎng)景從二維空間延伸到了三維空間。八叉樹(shù)（Octree）的定義是：若不為空樹(shù)的話，樹(shù)中任一節(jié)點(diǎn)的子節(jié)點(diǎn)恰好只會(huì)有八個(gè)，或零個(gè)，也就是子節(jié)點(diǎn)不會(huì)有0與8以外的數(shù)目。那么，這要用來(lái)做什么？想象一個(gè)立方體，我們最少可以切成多少個(gè)相同等分的小立方體？答案就是8個(gè)。如下八叉樹(shù)的結(jié)構(gòu)示意圖所示：
?
?
四叉樹(shù)存儲(chǔ)結(jié)構(gòu)的c語(yǔ)言描述：
[cpp]?view plaincopy
四叉樹(shù)的建立
1、利用四叉樹(shù)分網(wǎng)格，如本文的第一張圖<四層完全四叉樹(shù)結(jié)構(gòu)示意圖>，根據(jù)左圖的網(wǎng)格圖形建立如右圖所示的完全四叉樹(shù)。
偽碼：
Funtion QuadTreeBuild ( depth, rect )
? ?{
QuadTree->depth = depth;
/*創(chuàng)建分支，root樹(shù)的根，depth深度，rect根節(jié)點(diǎn)代表的矩形區(qū)域*/
QuadCreateBranch ( ?root, depth, rect );
? ?}
Funtion QuadCreateBranch ( n, depth,rect )
? ?{
if ( depth!=0 )
? ?{
n = new node; ? ?//開(kāi)辟新節(jié)點(diǎn)
n ->rect = rect; //將該節(jié)點(diǎn)所代表的矩形區(qū)域存儲(chǔ)到該節(jié)點(diǎn)中
將rect劃成四份 rect[UR], rect[UL], rect[LL], rect[LR];
/*創(chuàng)建各孩子分支*/
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] );
? ?}
? ?}
2、假設(shè)在一個(gè)矩形區(qū)域里有N個(gè)對(duì)象，如下左圖一個(gè)黑點(diǎn)代表一個(gè)對(duì)象，每個(gè)對(duì)象的坐標(biāo)位置都是已知的，用四叉樹(shù)的一個(gè)節(jié)點(diǎn)存儲(chǔ)一個(gè)對(duì)象，構(gòu)建成如下右圖所示的四叉樹(shù)。
方法也是采用遞歸的方法對(duì)該矩形進(jìn)行劃分分區(qū)塊，分完后再往里分，直到每一個(gè)子矩形區(qū)域里只包含一個(gè)對(duì)象為止。
偽碼：
Funtion QuadtreeBuild()
? {
???? Quadtree = {empty}；
? ? ?For (i = 1;i<n;i++) ? ? ?//遍歷所有對(duì)象
{
? ?QuadInsert(i, root)；//將i對(duì)象插入四叉樹(shù)
}? ? ? ? ??
? ? ? ? ?剔除多余的節(jié)點(diǎn)； ? ? ? //執(zhí)行完上面循環(huán)后，四叉樹(shù)中可能有數(shù)據(jù)為空的葉子節(jié)點(diǎn)需要剔除
? }????
Funtion QuadInsert(i,n) ? ? ?//該函數(shù)插入后四叉樹(shù)中的每個(gè)節(jié)點(diǎn)所存儲(chǔ)的對(duì)象數(shù)量不是1就是0
? {??
?????if（節(jié)點(diǎn)n有孩子）
?{??????
? ? 通過(guò)劃分區(qū)域判斷i應(yīng)該放置于n節(jié)點(diǎn)的哪一個(gè)孩子節(jié)點(diǎn)c；???????
? ? QuadInsert(i,c)；
?}
???? else if（節(jié)點(diǎn)n存儲(chǔ)了一個(gè)對(duì)象）
?{
? ? 為n節(jié)點(diǎn)創(chuàng)建四個(gè)孩子；
? ? 將n節(jié)點(diǎn)中的對(duì)象移到它應(yīng)該放置的孩子節(jié)點(diǎn)中；
? ? 通過(guò)劃分區(qū)域判斷i應(yīng)該放置于n節(jié)點(diǎn)的哪一個(gè)孩子節(jié)點(diǎn)c；
? ? QuadInsert(i,c)；
?}
???? else if（n節(jié)點(diǎn)數(shù)據(jù)為空） ? ?
?{
? ? 將i存儲(chǔ)到節(jié)點(diǎn)n中；
?}
? }?
（以上兩種建立方法作為舉一反三之用）
用四叉樹(shù)查找某一對(duì)象
1、采用盲目搜索，與二叉樹(shù)的遞歸遍歷類似，可采用后序遍歷或前序遍歷或中序遍歷對(duì)其進(jìn)行搜索某一對(duì)象，時(shí)間復(fù)雜度為O（n）。
?
2、根據(jù)對(duì)象在區(qū)域里的位置來(lái)搜索，采用分而治之思想，時(shí)間復(fù)雜度只與四叉樹(shù)的深度有關(guān)。比起盲目搜索，這種搜索在區(qū)域里的對(duì)象越多時(shí)效果越明顯
偽碼：
Funtion?find ( n, pos, )
? {
? ? ? If (n節(jié)點(diǎn)所存的對(duì)象位置為 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;???
? }?
結(jié)語(yǔ)：
熟話說(shuō)：結(jié)構(gòu)之法，算法之道。多一種數(shù)據(jù)結(jié)構(gòu)就多一種解決問(wèn)題的方法，多一種方法就多一種思維模式。祝君學(xué)習(xí)愉快！^_^
?==============================================
聲明：版權(quán)所有，轉(zhuǎn)載請(qǐng)注明出處：?http://blog.csdn.net/zhanxinhang/article/details/6706217
參考：維基百科、百度百科
參考：CS267: Lecture 24, Apr 11 1996?Fast Hierarchical Methods for the N-body Problem, Part 1
總結(jié)
