四叉树算法.docx

前序四叉树或四元树也被称为Q树（Q-Tree）四叉树广泛应用于图像处理、空间数据索引、 2D中的快速碰撞检测、存储稀疏数据等，而八叉树（Octree）主要应用于3D图形处理 对游戏编程，这会很有用本文着重于对四叉树与八叉树的原理与结构的介绍，帮助您在脑 海中建立四叉树与八叉树的基本思想本文并不对这两种数据结构同时进行详解，而只对四 叉树进行详解，因为八叉树的建立可由四叉树的建立推得四叉树与八叉树的结构与原理四叉树（Q-Tree）是一种树形数据结构四叉树的定义是：它的每个节点下至多可以有四 个子节点，通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四 叉树节点中这个区域可以是正方形、矩形或是任意形状以下为四叉树的二维空间结构（左） 和存储结构（右）示意图（注意节点颜色与网格边框颜色）：四叉树的每一个节点代表一个矩形区域（如上图黑色的根节点代表最外围黑色边框的矩形区 域），每一个矩形区域又可划分为四个小矩形区域，这四个小矩形区域作为四个子节点所代 表的矩形区域较之四叉树，八叉树将场景从二维空间延伸到了三维空间八叉树（Octree）的定义是：若 不为空树的话，树中任一节点的子节点恰好只会有八个，或零个，也就是子节点不会有0与8 以外的数目。

那么，这要用来做什么？想象一个立方体，我们最少可以切成多少个相同等分的小 立方体？答案就是8个如下八叉树的结构示意图所示：1. /* 一个矩形区域的象限划分：：2.2. UL(1) | UR(0)3. I 4. LL(2) | LR(3)5. 以下对该象限类型的枚举6. */7. typedef enum8. {9. UR = 0,10. UL = 1,11. LL = 2,12. LR = 313. }QuadrantEnum;15.14. /*矩形结构*/15. typedef struct quadrect_t16. {17. double left,18. top,19. right,20. bottom;21. }quadrect_t;24.25. /*四叉树节点类型结构*/26.typedef structquadnode_t27.{28.quadrect_trec t;〃节点所代表的矩形区域29.list_t*lst_object;//节点数据，节点类型一般为链表，可存储多个对象30. struct quadnode_t *sub[4]; //指向节点的四个孩子31. }quadnode_t;32.32. /*四叉树类型结构*/33. typedef struct quadtree_t34. {35. quadnode_t *root;36. int dep th; //四叉树的深度}quadtree_t;四叉树的建立1、利用四叉树分网格，如本文的第一张图＜四层完全四叉树结构示意图＞,根据左图的网格 图形建立如右图所示的完全四叉树。

伪码：FuntionQuadTreeBuild( depth, rect ){QuadTree-〉depth = depth;/*创建分支，root树的根，depth深度，rect根节点代表的矩形区域*/QuadCreateBranch( root, depth, rect );}FuntionQuadCreateBranch( 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]);}}2、假设在一个矩形区域里有N个对象，如下左图一个黑点代表一个对象，每个对象的坐标 位置都是已知的，用四叉树的一个节点存储一个对象，构建成如下右图所示的四叉树。

将所有黑点播入四叉树中构建四叉树方法也是采用递归的方法对该矩形进行划分分区块，分完后再往里分，直到每一个子矩形区 域里只包含一个对象为止伪码：FuntionQuadtreeBuild(){Quadtree = {empty}；For (i = 1;i

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;。