个人外贸网站制作,三明市网站建设,弄个app要花多少钱,网站建设和域名的关系参考#xff1a;http://blog.csdn.net/zhouxuguang236/article/details/12312099 原博客地址还有c#xff0b;#xff0b;源码。。。 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间#xff0c;如此递归下去…参考http://blog.csdn.net/zhouxuguang236/article/details/12312099 原博客地址还有c源码。。。 四叉树索引的基本思想是将地理空间递归划分为不同层次的树结构。它将已知范围的空间等分成四个相等的子空间如此递归下去直至树的层次达到一定深度或者满足某种要求后停止分割。四叉树的结构比较简单并且当空间数据对象分布比较均匀时具有比较高的空间数据插入和查询效率因此四叉树是GIS中常用的空间索引之一。常规四叉树的结构如图所示地理空间对象都存储在叶子节点上中间节点以及根节点不存储地理空间对象。 四叉树示意图 四叉树对于区域查询效率比较高。但如果空间对象分布不均匀随着地理空间对象的不断插入四叉树的层次会不断地加深将形成一棵严重不平衡的四叉树那么每次查询的深度将大大的增多从而导致查询效率的急剧下降。 本节将介绍一种改进的四叉树索引结构。四叉树结构是自顶向下逐步划分的一种树状的层次结构。传统的四叉树索引存在着以下几个缺点 (1)空间实体只能存储在叶子节点中中间节点以及根节点不能存储空间实体信息随着空间对象的不断插入最终会导致四叉树树的层次比较深在进行空间数据窗口查询的时候效率会比较低下。 (2)同一个地理实体在四叉树的分裂过程中极有可能存储在多个节点中这样就导致了索引存储空间的浪费。 (3)由于地理空间对象可能分布不均衡这样会导致常规四叉树生成一棵极为不平衡的树这样也会造成树结构的不平衡以及存储空间的浪费。 相应的改进方法将地理实体信息存储在完全包含它的最小矩形节点中不存储在它的父节点中每个地理实体只在树中存储一次避免存储空间的浪费。首先生成满四叉树避免在地理实体插入时需要重新分配内存加快插入的速度最后将空的节点所占内存空间释放掉。改进后的四叉树结构如下图所示。四叉树的深度一般取经验值4-7之间为最佳。 图改进的四叉树结构 为了维护空间索引与对存储在文件或数据库中的空间数据的一致性作者设计了如下的数据结构支持四叉树的操作。 (1)四分区域标识 分别定义了一个平面区域的四个子区域索引号右上为第一象限0左上为第二象限1左下为第三象限2右下为第四象限3。 typedef enum { UR 0,// UR第一象限 UL 1, // UL为第二象限 LL 2, // LL为第三象限 LR 3 // LR为第四象限 }QuadrantEnum; (2)空间对象数据结构 空间对象数据结构是对地理空间对象的近似在空间索引中相当一部分都是采用MBR作为近似。 /*空间对象MBR信息*/ typedef struct SHPMBRInfo { int nID; //空间对象ID号 MapRect Box; //空间对象MBR范围坐标 }SHPMBRInfo; nID是空间对象的标识号Box是空间对象的最小外包矩形MBR。 (3)四叉树节点数据结构 四叉树节点是四叉树结构的主要组成部分主要用于存储空间对象的标识号和MBR也是四叉树算法操作的主要部分。 /*四叉树节点类型结构*/ typedef struct QuadNode { MapRect Box; //节点所代表的矩形区域 int nShpCount; //节点所包含的所有空间对象个数 SHPMBRInfo* pShapeObj; //空间对象指针数组 int nChildCount; //子节点个数 QuadNode *children[4]; //指向节点的四个孩子 }QuadNode; Box是代表四叉树对应区域的最小外包矩形上一层的节点的最小外包矩形包含下一层最小外包矩形区域nShpCount代表本节点包含的空间对象的个数pShapeObj代表指向空间对象存储地址的首地址同一个节点的空间对象在内存中连续存储nChildCount代表节点拥有的子节点的数目children是指向孩子节点指针的数组。 参考http://blog.csdn.net/zhouxuguang236/article/details/12312099 四叉树原理 四叉树是种很直接的空间索引技术。在四叉树中每个节点表示覆盖了部分进行索引的空间的边界框根节点覆盖了整个区域。每个节点要么是叶节点有包含一个或多个索引点的列表没有孩子。要么是内部节点有四个孩子每个孩子对应将区域沿两根轴对半分得到的四个象限中的一个四叉树也因此得名。 图1 展示四叉树是怎样划分索引区域的 来源维基百科 将数据插入四叉树很简单从根节点开始判断你的数据点属于哪个象限。递归到相应的节点重复步骤直到到达叶节点然后将该点加入节点的索引点列表中。如果列表中的元素个数超出了预设的最大数目则将节点分裂将其中的索引点移动到相应的子节点中去。 图2 四叉树的内部结构 查询四叉树时从根节点开始检查每个子节点看是否与查询的区域相交。如果是则递归进入该子节点。当到达叶节点时检查点列表中的每一个项看是否与查询区域相交如果是则返回此项。 注意四叉树是非常规则的事实上它是一种字典树因为树节点的值不依赖于插入的数据。因此我们可以用直接的方式给节点编号用二进制给每个象限编号左上是00右上是10等等 译者注第一个比特位为0表示在左半平面为1在右半平面。第二个比特位为0表示在上半平面为1在下半平面任一节点的编号是由从根开始它的各祖先的象限号码串接而成的。在这个编号系统中图2中右下角节点的编号是1101。 如果我们定义了树的最大深度不需通过树就可以计算数据点所在节点的编号只要把节点的坐标标准化到适当的整数区间中比如32位整数然后把转化后x, y坐标的比特位交错组合。每对比特指定了假想的四叉树中的一个象限。 如何在iOS地图上高效的显示大量数据 参考http://blog.163.com/l1_jun/blog/static/143863882013111651737708/转载于:https://www.cnblogs.com/lyggqm/p/5230733.html
