前序
四叉树或四元树也被称为Q树(Q-Tree)。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等,而八叉树(Octree)主要应用于3D图形处理。对游戏编程,这会很有用。本文着重于对四叉树与八叉树的原理与结构的介绍,帮助您在脑海中建立四叉树与八叉树的基本思想。本文并不对这两种数据结构同时进行详解,而只对四叉树进行详解,因为八叉树的建立可由四叉树的建立推得。若有不足之处,望能不吝指出
四叉树与八叉树的结构与原理
四叉树(Q-Tree)是一种树形数据结构。四叉树的定义是:它的每个节点下至多可以有四个子节点,通常把一部分二维空间细分为四个象限或区域并把该区域里的相关信息存入到四叉树节点中。这个区域可以是正方形、矩形或是任意形状。以下为四叉树的二维空间结构(左)和存储结构(右)示意图(注意节点颜色与网格边框颜色):
四叉树的每一个节点代表一个矩形区域(如上图黑色的根节点代表最外围黑色边框的矩形区域),每一个矩形区域又可划分为四个小矩形区域,这四个小矩形区域作为四个子节点所代表的矩形区域。
较之四叉树,八叉树将场景从二维空间延伸到了三维空间。八叉树(Octree)的定义是:若不为空树的话,树中任一节点的子节点恰好只会有八个,或零个,也就是子节点不会有0与8以外的数目。那么,这要用来做什么?想象一个立方体,我们最少可以切成多少个相同等分的小立方体?答案就是8个。如下八叉树的结构示意图所示:
四叉树存储结构的c语言
/* 一个矩形区域的象限划分:: 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;
四叉树的建立
1、利用四叉树分网格,如本文的第一张图<四层完全四叉树结构示意图>,根据左图的网格图形建立如右图所示的完全四叉树。
伪码:
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] );
}
}
2、假设在一个矩形区域里有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;
}
结语:
熟话说:结构之法,算法之道。多一种数据结构就多一种解决问题的方法,多一种方法就多一种思维模式。祝君学习愉快!^_^
==============================================
声明:版权所有,转载请注明出处: http://blog.csdn.net/zhanxinhang/article/details/6706217
参考:维基百科、百度百科
参考:CS267: Lecture 24, Apr 11 1996 Fast Hierarchical Methods for the N-body Problem, Part 1
相关推荐
总结来说,四叉树和八叉树细化算法在图像处理中扮演着至关重要的角色,它们结合了数据结构的优势与细化算法的智能,为图像分析和理解提供了强大的工具。在进行英文翻译时,需要准确传达这些概念和技术细节,以便于...
线性四叉树和线性八叉树是两种高效的空间数据结构,主要用于处理三维空间中的数据,例如图像处理、地理信息系统、遥感图像分析等领域。它们通过编码方式将三维空间中的每个元素(如像素或体素)映射为一个唯一的数字...
本文提出的基于四叉树的线性八叉树混合数据结构,旨在利用线性四叉树表示二维目标和线性八叉树表示三维目标的优势,同时通过十进制编码技术对混合结构进行编码,提高数据结构的适用性和效率。混合数据结构能够更好地...
描述中提到“基于四叉树的修改”,意味着八叉树是四叉树的一个扩展。四叉树是二维空间的分区结构,而八叉树则是将其扩展到了三维空间。在四叉树中,每个节点有四个子节点,分别对应上、下、左、右四个象限;而在八叉...
除了基本的四叉树,还有许多变种,如八叉树(Octree)用于三维空间,十六叉树(Hexadecatree)用于更高维度。这些变种在各自的应用领域中都能提供类似的优势。 总之,四叉树是一种强大的数据结构,尤其适用于处理二...
Unity3D是一款强大的跨平台3D游戏开发引擎,被广泛应用于游戏制作、虚拟现实和增强现实..."Unity Octree-master"这个压缩包可能包含了实现八叉树的源代码示例,开发者可以通过研究这些代码来加深对八叉树的理解和应用。
RegionTrees.jl:四叉树,八叉树及其N维表兄弟 这个Julia包是用于定义N维区域树的轻量级框架。 在2D中,这些称为区域四叉树,而在3D中,它们通常称为octree 。 区域树是一种简单的数据结构,用于描述具有不同分辨率...
6. **遍历与可视化**:四叉树的遍历方法通常包括前序遍历、中序遍历和后序遍历,这些方法可以帮助理解四叉树的结构。此外,可视化工具能帮助我们直观地查看四叉树的布局,这对于调试和理解代码至关重要。 7. **性能...
网格的多分辨率层次结构存储为不重叠的固定大小网格的复合结构,这些结构作为叶子存储在四叉树或八叉树的森林中。 基于高度可扩展的网格划分库p4est() 提供了针对双曲线PDE的求解器,包括Clawpack 4.x,Clawpack ...
在实际应用中,八叉树算法通常结合其他技术,如LOD(Level of Detail)来平衡细节和计算资源,或者采用四叉树(Quadtree)在二维空间进行类似操作。同时,考虑到不同的应用场景,还可以选择不同的压缩策略,例如基于...
在实际应用中,四叉树LOD算法通常与空间索引结构如Octree(八叉树)配合使用,因为四叉树更适合处理二维空间的数据,如地形、地图等。同时,LOD算法还可以结合其他优化策略,比如视锥剔除、背面剔除等,进一步提升...
5. **四叉树与八叉树工作模式**: 四叉树和八叉树通常用于图形数据结构和空间分割,是计算机图形学中常用的方法,用以快速检索空间信息。文档分析了方形栅格四叉树和八叉树模式的弊端,并指出了改进蜂巢栅格环境...
与常见的二叉树和四叉树相比,八叉树每节点有八个子节点,分别对应三维空间中的八个象限。这种数据结构特别适用于处理三维空间中的数据,如3D建模、游戏引擎、图像渲染、地理信息系统和虚拟现实等领域。 八叉树的...
分析了线性四叉树、线性八叉树两种数据结构的...针对矿山GIS中空间三维目标与二维目标叠置分析存在的问题,提出了一种基于四叉树的线性八叉树的数据结构。试验表明,这种数据结构能较好地解决矿山GIS与DEM、RS的结合。
地形渲染的动态LOD四叉树算法,读者应该熟悉递归程序设计,以及基本的VC OpenGL编程.
传统的场景管理方法包含场景图、二叉树、四叉树和八叉树等。其中,八叉树空间划分(Octree Space Division,OSD)技术,由于其在处理3D空间数据上的独特优势,成为了一种非常重要的场景管理技术。 八叉树方法的特点...
四叉树和八叉树法以及三角剖分法虽然理论上效率较高,但实现起来较为复杂,且在实际应用中使用较少。 网格法相较于上述方法,其优势在于容易实现,且在多数情况下具有较高的计算效率。但是,应用网格法时,需要合理...
sparse-voxel-octrees, CPU稀疏素八叉树实现 稀疏体素八叉方案在 C++ 中实现了多线程。CPU稀疏的体素八叉树实现,能够实时跟踪大型数据集,将原始体素文件转换为八叉树,转化为。转换例程能够处理比工作内存大得多的...
八叉树(Octree)是三维空间的一种数据结构,类似于二维空间的四叉树。它将三维空间划分为八个子空间,并递归地对每个子空间进行细分,直到所有子空间内没有或只有单个网格元素(如顶点、面片等)。八叉树通过节点...