tags: 算法
转载：http://blog.csdn.net/zhanxinhang/article/details/
高德iOS聚合实例
高德Android聚合实例
四叉树或四元树也被称为Q树（Q-Tree）。四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据等，而八叉树（Octree）主要应用于3D图形处理。对游戏编程，这会很有用。本文着重于对四叉树与八叉树的原理与结构的介绍，帮助您在脑海中建立四叉树与八叉树的基本思想。本文并不对这两种数据结构同时进行详解，而只对四叉树进行详解，因为八叉树的建立可由四叉树的建立推得。
/* 一个矩形区域的象限划分：: 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
用四叉树查找某一对象
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; } 版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226218.html原文链接：https://javaforall.net
