四叉树算法.doc

前序四叉树或四元树也被称为Q树(Q-Tree)。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等,而八叉树(Octree)主要应用于3D图形处理。对游戏编程,这会很有用。本文着重于对四叉树与八叉树的原理与结构的介绍,帮助您在脑海中建立四叉树与八叉树的基本思想。本文并不对这两种数据结构同时进行详解,而只对四叉树进行详解,因为八叉树的建立可由四叉树的建立推得。四叉树与八叉树的结构与原理四叉树(Q-Tree)是一种树形数据结构。四叉树的定义是:它的每个节点下至多可以有四个子节点,通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。这个区域可以是正方形、矩形或是任意形状。以下为四叉树的二维空间结构(左)和存储结构(右)示意图(注意节点颜色与网格边框颜色):四叉树的每一个节点代表一个矩形区域(如上图黑色的根节点代表最外围黑色边框的矩形区域),每一个矩形区域又可划分为四个小矩形区域,这四个小矩形区域作为四个子节点所代表的矩形区域。较之四叉树,八叉树将场景从二维空间延伸到了三维空间。八叉树(Octree)的定义是:若不为空树的话,树中任一节点的子节点恰好只会有八个,或零个,也就是子节点不会有0与8以外的数目。那么,这要用来做什么?想象一个立方体,我们最少可以切成多少个相同等分的小立方体?答案就是8个。如下八叉树的结构示意图所示:四叉树存储结构的c语言描述:[cpp] viewplaincopy1./* 一个矩形区域的象限划分:: (1)   |    UR(0) 4.----------|----------- (2)   |    LR(3)  7.*/   enum  9.{   = 0,   = 1,   = 2,   = 3  14.}QuadrantEnum;  ./* 矩形结构 */   struct quadrect_t  18.{        left,   ,   ,   ;  23.}quadrect_t;  ./* 四叉树节点类型结构 */   struct quadnode_t  27.{      rect;          //节点所代表的矩形区域          *lst_object;   //节点数据, 节点类型一般为链表,可存储多个对象    quadnode_t  *sub[4]; //指向节点的四个孩子   31.}quadnode_t;  ./* 四叉树类型结构 */   struct quadtree_t  35.{    *root;           depth;           // 四叉树的深度                      }quadtree_t;  四叉树的建立1、利用四叉树分网格,如本文的第一张图<四层完全四叉树结构示意图>,根据左图的网格图形建立如右图所示的完全四叉树。伪码