转自:
http://blog.csdn.net/sjzwl/archive/2008/10/06/3020276.aspx 四叉树索引(Quadtree),类似于前面介绍的网格索引,也是对地理空间进行网格划分,对地理空间递归进行四分来构建四叉树,本文将在普通四叉树的基础上,介绍一种改进的四叉树索引结构。
首先,先介绍一个GIS(Geographic Information System)或者计算机图形学上非常重要的概念——最小外包矩形(MBR-Minimum Bounding Rectangle):
最小外包矩形MBR就是包围图元,且平行于X,Y轴的最小外接矩形。MBR到底有什么用处呢,为什么要引入这个概念呢?因为,图元的形状是不规则的,而MBR是平行于X,Y轴的规则图形,设想一下,如果所有的图元都是平行于X,Y轴的矩形,那针对这样的矩形进行几何上的任何判断,是不是要简单很多呢?不管我们人自己写公式算法或者编写程序运行,是不是都要比原本复杂的图形几何运算要简洁很多呢?答案很显然。
然后,我们再介绍一下GIS空间操作的步骤(这个步骤,在前面忘记向大家说明了,在这里补充一下)
可见,过滤阶段,通过空间索引可以排除掉一些明显不符合条件的图元,得到后选集合,然后对后选图元集合进行精确几何运算,得到最终结果。大家可能会有这样的疑问,这样有必要吗?是不是反而把问题复杂化了?合适的空间索引只会提高计算机的效率,没有空间索引,我们无疑要对集合中的每个图元进行精确几何运算,而这样的运算是复杂的,是非常占用CPU的,所以需要空间索引,采取少量的内存和简单的CUP运算,来尽量减少那种高耗CUP的精确运算的次数,这样做是完全值得的。至于精确的几何运算到底复杂在哪里,该如何进行精确的几何运算,将在下面的章节中详细描述,这里主要介绍过滤阶段的空间索引。
现在,让我们来具体了解一下“四叉树索引”。
四叉树索引就是递归地对地理空间进行四分,直到自行设定的终止条件(比如每个节点关联图元的个数不超过3个,超过3个,就再四分),最终形成一颗有层次的四叉树。图中有数字标识的矩形是每个图元的MBR,每个叶子节点存储了本区域所关联的图元标识列表和本区域地理范围,非叶子节点仅存储了区域的地理范围。大家可以发现,同样存在一个图元标识被多个区域所关联,相应地存储在多个叶子节点上,比如“6“所代表的图元,分别存储在四个分枝上。这样,就存在索引的冗余,与网格索引存在同样的弊端。下面我们介绍一种改进的四叉树索引,或者说是分层的网格索引。
改进的四叉树索引,就是为了避免这种空间索引的冗余,基本改进思路是:让每个图元的MBR被一个最小区域完全包含。
可以看出,3和13分别都跨越了两个区域,要被一个最小区域完全包含,就只能是根节点所代表的区域,2,5跨越了两个区域,6跨越了四个区域,要被一个最小区域完全包含,就只能是NW区域。怎么判断一个图元被哪个最小区域完全包含呢?从直观上看,递归地对地理空间进行四分,如果图元与一个区域四分的划分线相交,则这个图元就归属于这个区域,或者直到不再划分了,那就属于这个不再划分的区域。呵呵。。。可能有点绕口,看图,结合“最小”“完全包含”这两个字眼,您就明白了。这颗四叉树中,图元的标识不再仅仅存储在叶子节点上,而是每个节点都有可能存储,这样也就避免了索引冗余。同时每个节点存储本节点所在的地理范围。
有了四叉树索引,下面又该如何利用这颗树来帮助检索查找呢?还是矩形选择为例吧!(为什么我总是拿这个例子来说事呢?因为这个例子简单,容易理解,有代表性!)我们在地图上画一个矩形,判断地图上哪些图元落在这个矩形里或者和这个所画矩形相交。方法很多,这里介绍一种简单的检索步骤,如下:1,首先,从四叉树的根节点开始,把根节点所关联的图元标识都加到一个List里;2,比较此矩形范围与根节点的四个子节点(或者叫子区域)是否有交集(相交或者包含),如果有,则把相应的区域所关联的图元标识加到List集合中,如果没有,则以下这颗子树都不再考虑。3,以上过程的递归,直到树的叶子节点终止,返回List。4,从List集合中根据标识一一取出图元,先判断图元MBR与矩形有无交集,如果有,则进行下面的精确几何判断,如果没有,则不再考虑此图元。(当然,这里只说了一个基本思路,其实还有其他一些不同的方法,比如,结合空间数据磁盘的物理存储会有一些调整)
总结:改进的四叉树索引解决了线,面对象的索引冗余,具有较好的性能,而被大型空间数据库引擎所采用,如ArcSDE,Oracle Spatial等,同时这种结构也适用于空间数据的磁盘索引,配合空间排序聚类,基于分形的Hilbert算法数据组织,将在空间数据格式的定义中发挥重要作用。
-
- 大小: 18.8 KB
-
- 大小: 15.4 KB
-
- 大小: 21.1 KB
-
- 大小: 22.9 KB
分享到:
相关推荐
gis原理时做的作业,感觉挺麻烦 四叉树索引 c#
ersi tilemap的四叉树详解与研究
基于改进四叉树索引的矢量地图叠加分析算法 描述了改进的空间叠加分析方法 是学习图形学算法和数据结构的很资料 特别是对于GIS开发的人员来特别有用
一种基于四叉树索引的海量激光扫描点云实时绘制方法
Kiwi 数据规格书,非常详细,近800页资料。GPS电子地图数据索引结构设计,索引方式介绍,四叉树索引_kiwi
用VC及OpenGL实现,采用四叉树做索引,实现的室外地景的模拟实现,通过该源代码可以初步熟悉OpenGL的初步用法以及四叉树索引的实现。
把一个四叉树结构的list转变成一棵四叉树的对象,并通过前序遍历遍历这棵树,一个脚本,一个类两个函数
面向移动GIS的动态四叉树空间索引算法 赵 波 边馥苓 摘 要:介绍了常用的空间索引算法,对其性能进行了比较,认为这些算法用于需要动态更新空间索引结构的移动GIS系统中时具有较大的局限性。针对移动GIS系统中对...
#资源达人分享计划#
这个代码是一个四叉树的C#实现,使用四叉树文成一个可视项目。四叉树是一种树结构可以用于编码和2D碰撞检测。多用在2D碰撞检测中,在大量的碰撞检测中可以提高效率,但结构略复杂。
高级数据库技术课程中,对四叉树索引进行了详细的讲述。
基于线性四叉树的全球离散格网索引
读取点云四叉树索引,建立LOD在OSG中显示。
对多维空间,基于地理位置应用,时间-空间,四叉树,HBase,等等
此资源为unity实现叉树逻辑,工程是unity2017版本。 四叉树广泛应用于图像处理、空间数据索引、2D中的快速碰撞检测、存储稀疏数据
综合分析了R-树和四叉树在处理移动对象的连续K近邻(简称CKNN)查询算法中的不足,提出了一种基于R树和四叉树索引结构,去解决移动对象连续K近邻查询算法。该算法通过对移动对象分配静态空间,并在研究区域内利用QR-...
针对现有数据结构无法支持WebGIS中多维空间数据的多尺度表达,提出了一种改进的数据结构:a)主树由金字塔层级结构规则分割的区域四叉树索引结构变形而来;b)具有支持多维数据的重叠子树结构;c)利用树的深度反映空间...
R树和四叉树的空间索引结构“RQOP”树.pdf
Oracle Spatial是甲骨文公司针对空间数据管理的一组插件, 其针对存储在Oracle Spatial数据库中空间元素提供了一种SQL 模式和便于存储、检索、更新、查询的函数集。它由以下组件构 ...即R树索引和四叉树索引。