`
nlslzf
  • 浏览: 1046470 次
  • 性别: Icon_minigender_1
  • 来自: 北京
社区版块
存档分类
最新评论

四叉树索引

阅读更多
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
分享到:
评论

相关推荐

    四叉树索引c#gis原理时做的作业,感觉挺麻烦

    四叉树索引是一种在计算机科学中用于组织和检索图像数据、地理空间数据或类似二维数据结构的有效方法。它在GIS(地理信息系统)领域尤为重要,因为这类系统经常处理大量地图和地理位置信息。C#是一种广泛使用的编程...

    高级主题(一) esri tilemap 四叉树索引研究

    ### 高级主题(一) esri tilemap 四叉树索引研究 #### 四叉树索引:esri tilemap与Google Map的区别 在地理信息系统(GIS)领域,地图切片技术是将地球表面的大面积地理信息切割成小块进行存储、传输和展示的一种...

    GPS电子地图数据索引结构设计,索引方式介绍,四叉树索引_kiwi

    本文将深入探讨"GPS电子地图数据索引结构设计,索引方式介绍,四叉树索引"这一主题,并结合"kiwi"数据规格书的相关内容进行详细阐述。 首先,我们来了解GPS电子地图数据的基本构成。这些数据通常包括地理位置坐标...

    基于改进四叉树索引的矢量地图叠加分析算法

    ### 基于改进四叉树索引的矢量地图叠加分析算法 #### 概述 本文介绍了一种改进的四叉树索引方法应用于矢量地图叠加分析中的算法。该算法通过优化空间数据的组织和检索过程,提高了地图叠加分析的效率。此算法对于...

    基于Hadoop的分布式CIF四叉树索引方法.pdf

    针对标题《基于Hadoop的分布式CIF四叉树索引方法》,本文主要探讨了利用Hadoop平台和MapReduce编程模型,在分布式环境下,对大量矩形空间数据对象进行高效管理的CIF(空间信息过滤)四叉树索引技术。分布式系统和...

    面向移动GIS 的动态四叉树空间索引算法

    动态四叉树算法基于传统的四叉树索引方法进行改进,使其更适合移动GIS的应用场景。 - **动态调整机制**:算法可以根据实际数据分布情况动态调整四叉树的结构,减少不必要的节点,从而提高索引效率。 - **高效更新...

    一种基于四叉树索引的海量激光扫描点云实时绘制方法.

    一种基于四叉树索引的海量激光扫描点云实时绘制方法

    C++实现四叉树效果(附源码下载)

    四叉树是一种数据结构,主要用于二维空间的组织和索引,尤其在计算机图形学、图像处理和游戏开发等领域中有着广泛的应用。它扩展了二叉树的概念,每个节点有四个子节点,分别代表四个象限:左上(LT),右上(RT),...

    一种构建四叉树隧道点云索引的限界检测方法.docx

    本文的主要贡献在于提出了一个新颖的限界检测方法,利用四叉树索引和四叉树最邻近点搜索算法来计算限界,从而提高限界检测的效率和精度。该方法可以广泛应用于地铁限界检测、隧道建筑检测等领域。 本文提出了一种...

    基于Oracle Spatial的四叉数索引调整研究.pdf

    因此,大多数GIS平台提供的四叉树索引深度是固定的,导致存储空间的不可预测增长和查询速度的下降。 文章通过对比分析不同索引类型和索引值,揭示了如何调整四叉树索引以优化性能。它指出,更精细的索引划分虽然...

    python生成四叉树

    把一个四叉树结构的list转变成一棵四叉树的对象,并通过前序遍历遍历这棵树,一个脚本,一个类两个函数

    四叉树_C++_四叉树_

    四叉树是一种特殊的树结构,它在计算机科学中主要用于图像处理、数据索引和地理信息系统等领域。与常见的二叉树不同,每个节点在四叉树中可以有四个子节点,分别对应于上、下、左、右四个方向。这种结构在处理二维...

    QuadTree四叉树实现代码 C#

    四叉树(QuadTree)是一种数据结构,特别适用于二维空间的组织和检索。它是由四分树的概念演变而来的,每个节点都有四个子节点,分别代表左上、右上、左下和右下四个区域。四叉树在计算机图形学、地理信息系统、图像...

    四叉树算法的C#实现

    四叉树算法是一种在计算机科学中广泛应用于二维空间数据组织的数据结构,特别是在图像处理、地图索引和游戏编程等领域。它的基本思想是将平面分割成四个相等的区域,每个区域可以进一步分为四个子区域,以此类推。...

    四叉树实现

    四叉树是一种数据结构,特别适用于处理二维空间中的数据,如图像处理和地图索引等场景。它将二维空间划分为四个象限,类似于一个坐标轴的四个角落:西北(NW)、东北(NE)、西南(SW)和东南(SE)。四叉树的核心思想是将每...

    四叉树 unity实现 源码

    在Unity游戏引擎中,四叉树常被用于优化空间数据索引和碰撞检测,以提高性能和效率。本资源提供了Unity2017版本下的四叉树实现源码,这对于开发者来说是一个很好的学习和实践机会。 四叉树是二叉树的扩展,每个节点...

    load_cache-0.0.0.zip_lod osg_osg显示点云_四叉树_点云 osg_lod_点云索引

    总之,"load_cache-0.0.0.zip"所涉及的点云四叉树索引和LOD技术,是点云数据在OSG中高效管理和显示的关键。通过对这些技术的深入理解和应用,开发者可以构建出能够在大规模点云数据中游刃有余的三维可视化应用。

    四叉树的详细讲解四叉树的详细讲解四叉树的详细讲解

    这种结构使得四叉树在处理二维空间的数据时具有独特的优势,例如在图像分割、索引构建和地理信息系统中广泛应用。 四叉树的定义: 四叉树是一种n-ary树(n=4),每个节点最多包含四个子节点。这些子节点通常被理解...

    四叉树代码

    4. 数据索引:四叉树也可以作为一种数据索引结构,用于快速查找和更新二维数据。 四叉树的实现: 实现四叉树通常涉及以下几个关键步骤: 1. 初始化:创建根节点,初始化为空或者包含初始数据。 2. 插入操作:根据...

    四叉树编码的原理

    这种类型的四叉树主要用于数据索引和图幅索引等领域。 - **线性四叉树**:仅存储叶子节点的信息,包括位置、深度和节点属性。相比常规四叉树,线性四叉树减少了数据的冗余,提高了效率。 - **四叉树编码的特点**:...

Global site tag (gtag.js) - Google Analytics