四叉树应用于地图（点聚合）碰撞检测等问题游戏开发中经常有碰撞检测的算法，对于平面上N个图形，如果需要检测互相之间是否发

为了保证规律性和平均分配，采用区域划分方法显示标注。简单来说就是把屏幕分割成若干个区域，每个区域最多显示一个标注，然后根据地图缩放比例动态的设置这些区域的大小以达到最佳的用户体验。

将数据逐个放入这个树状结构，给每一个节点一个范围。创建过程较为费时，建议另开线程。

关键问题就是在用户拖拽旋转结束的时候，我们需要调整我们界面的显示UI，也就是说，关键问题就是从这个四叉树里面查找出需要的标注，这部分的速度至关重要。

四叉树没有删除的方法，因为删除成本大于重建树结构成本。

主要逻辑：第一步：遍历屏幕划分的区域第二步：比较该区域是否和四叉树元素范围有交集，无交集则舍弃，有交集继续向下查找

优化：我对查找逻辑做了小优化。在第二步的时候，如果有交集，给是否继续向下查找做了一个开关。理由是，我们查找出所有在该划分区域内的标注，如果目的只是为了算出他们的平均中心点，就显得意义不大，大可查找出几个就停止查找。

聚合分为四个级别：市、区、街道，点（不聚合）

非满四叉树优化：为每个结点添加一个“容量”的属性，在四叉树初始化时只有一个根结点，在插入数据时，如果一个结点内的数据量大于了结点“容量”，再将结点进行分裂。如此，可以保证每个结点内都存储着数据，避免了内存空间的浪费。

查询:只有找到了位置对应的结点，那么结点下的所有点都会是此位置的附近点，更小的“容量”意味着每个结点内点越少，也就意味着查询的精度会越高。

边界点问题:每个结点内的点必然是相邻的，但相邻的点越不一定在同一个结点内

特性：字典树，又称前缀树或trie树，是一种有序树，用于保存关联数组，其中的键通常是字符串。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。

解决：继续优化四叉树，给结点添加一个“编号”属性。

typedefenum{UR=0,//UR第一象限UL=1,//UL为第二象限LL=2,//LL为第三象限LR=3//LR为第四象限}QuadrantEnum;2)空间对象数据结构typedefstructSHPMBRInfo{intnID;//空间对象ID号MapRectBox;//空间对象MBR范围坐标}SHPMBRInfo;3)四叉树节点数据结构typedefstructQuadNode{MapRectBox;//节点所代表的矩形区域IntnShpCount;//节点所包含的所有空间对象个数SHPMBRInfo*pShapeObj;//空间对象指针数组IntnChildCount;//子节点个数QuadNode*children[4];//指向节点的四个孩子}QuadNode;四叉树原理四叉树是种很直接的空间索引技术。在四叉树中，每个节点表示覆盖了部分进行索引的空间的边界框，根节点覆盖了整个区域。每个节点要么是叶节点，有包含一个或多个索引点的列表，没有孩子。要么是内部节点，有四个孩子，每个孩子对应将区域沿两根轴对半分得到的四个象限中的一个，四叉树也因此得名。

后台实现聚合算法，App拿到数据后，直接显示聚合点或非聚合点。具体实现如下：