3D GIS空间索引技术

1、3D GIS空间索引技术3DGIS是新一代GIS技术的重要分支，是进行全方位、多层次、多要素时空分析的基础, 开发结构简单、功能完善的真3DGIS软件是当前GIS研究人员的重要目标。3DGIS需要管理 大量的三维空间对象，且常常需要根据空间位置对这些对象进行查询、检索和显示操作。 为了处理这类空间操作，传统的关系数据库搜索方法需要花费大量的磁盘访问时间和空间 运算时间。为了提高检索效率，传统的关系数据库一般都建立一系列的索引机制，如B+树 等。目前常用的索引机制多是一维索引，无法有效处理3DGIS空间数据库中的三维空间地 理实体。因此，必须为3DGIS空间数据库建立专门的索引机制空间索引。空间

2、索引是指根据空间要素的地理位置、形状或空间对象之间的某种空间关系，按照 一定规律排列的数据结构，它介于空间操作算法和空间对象之间，筛选、排除与特定的空 间操作无关的空间对象。空间索引机制是快速、高效地查询、检索和显示地理空间数据的 基础，其性能优劣直接影响GIS空间数据库的性能，关系到3DGIS软件系统的整体运行状 况。一、三维空间索引简介3DGIS是2DGIS在三维空间内的延展，是布满整个三维空间内的GIS，它与2DGIS的差 异主要体现在空间位置的确定、空间拓扑关系的描述与空间分析的延展方向上。3DGIS将三 维空间坐标（x，y，z）作为独立的参数来构建空间实体对象模型，能够实现空间实体的

3、真 三维可视化，以立体造型来展现空间地理现象，它不仅能够表达空间实体之间的平面关系， 还能够表达其垂向关系，在此基础上进行复杂的三维空间分析与操作。在GIS由二维扩充到三维后，其处理的空间对象也由二维空间中的“点、线、面”扩 充到三维空间中的“点、线、面、体”。2DGIS对平面空间的“有限-互斥-完整”剖分是基 于面的划分，而3DGIS对三维空间的“有限-互斥-完整”剖分则是基于体的划分。在3DGIS 空间数据库中，空间实体的表达形式复杂，各种空间操作不仅计算量大，而且多具有面向 邻域的特点。因此，在3DGIS中，由于空间维数的增加和空间实体关系复杂度的提高而导 致三维空间数据的海量性。海量数

4、据的存储与管理需要更加高效的空间数据结构和空间索 引机制。目前成熟的空间索引算法多集中在二维空间索引上，如网格索引、四叉树索引等, 而对3DGIS的空间索引问题研究较少。对低维空间数据而言，二维空间索引的索引效率较 高，并且多数可以进行扩展以支持高维数据集。但应用实践显示，仅仅简单地将二维空间 索引维数增加到三维，其效率并不高，且很多索引结构都是针对特定空间查询操作而设计 的，不具有通用性。因此，需要研究3DGIS所使用的空间索引技术。设计3DGIS空间索引面临的主要困难是：三维空间实体的空间关系比较复杂，有时甚 至呈一种相对无序的状态。从本质上看，3DGIS对空间索引的要求与2DGIS基本类

5、似，但在 数据采集、数据库维护、数据操作、界面设计等方面要比2DGIS复杂得多。目前的三维空 间索引大多是从二维空间索引的基础上发展而来的。与二维空间索引相似，三维空间索引 方法也是基于空间数据的层次化聚类原则，结构上类似于早期用于数据检索的B+树：数据 矢量存储在数据节点，空间位置邻近的矢量尽可能存储于同一节点。数据节点之间以层次 化目录结构来组织，每一个目录节点都指向下一级的一个子树。目前，索引结构大都采用平衡树的概念，即从根节点到所有数据节点的访问长度（索 引高度）相同（但在插入和删除操作后可能会有改变），在树的形状上表现为高度一致性。 从任意节点到数据节点的访问长度称为节点的级，数据节

6、点对应第0级。二、空间索引结构分类根据空间索引结构的演化过程，空间索引方法可分为4大类，即基于二叉树的索引技 术、基于B树的索引技术、基于Hashing的格网技术和空间目标排序法。空间索引的基本方法是将整个空间分割成不同的搜索区域，以一定的顺序在这些区域 中查找空间实体。针对3DGIS应用的实际，按照搜索分割对象不同，可将空间索引分为3 类，即基于点区域划分的索引方法、基于面区域划分的索引方法和基于三维体区域划分的 索引方法。常见的基于点区域划分的索引结构有KD树、B树、KDB树和点四叉树等；基于 面区域划分的索引结构有区域四叉树、R树系列和格网索引机制等；基于三维体区域划分的 索引结构有Mo

7、r ton编码、无边界Qu编码、球面QTM编码以及球面HSDS编码等。按照空间分割方法将空间分割分为规则分割法和对象分割法。规则分割法是将地理空 间按照某种规则或半规则的方式进行分割，分割单元间接地与空间要素相关联，空间要素 的几何形状可能被分割到几个相邻的单元中，这时空间要素的描述保持完整，而空间索引 单元只存储空间要素地址的参考信息。在对象分割法中，索引空间的分割直接由空间要素 确定，索引单元包括空间要素地址的参考信息和空间要素的外包络矩形。规则分割法包括 规则网格、BSP树、八叉树、KD树、KDB树和R树系列等，对象分割法一般通过层次包围体 （bounding volume hierar

8、chy）实现。下文按照分割方法对常见的空间索引结构进行详细 讨论。三、常见的三维空间索引结构（一）对象分割法对象分割法一般由层次包围体实现。层次包围体是一种简单的树结构，它用一些特定 的方法对空间实体对象进行分割，最终将树的每一个节点保存为所在层次的包围体信息， 叶子节点则存储基本对象。如当对两个物体做碰撞检测时，首先检测两者的包围体是否有 交，若不相交，则说明两个物体未相交，否则再进一步对两个物体进行检测。求包围体的 交比求物体的交要简单得多，以便快速排除很多不相交的物体，从而加速检索算法。常见 的包围体有5种：包围球（Spheres ）。包围球是一种最简单的包围体，易于计算，非常易于做重叠

9、测 试和节点修改，但缺点是与物体的逼近程度较差。轴向包围盒（Axisaligned Bounding Box，ABB）。轴向包围盒是一种长方体的包围 体，其各轴的方向与坐标轴的方向一致，它也是一种易于做重叠测试的包围体，但与物体 的逼近程度也较差。方向包围盒（Oriented Bounding Box，OBB）:方向包围盒是一个任意方向的长方体 包围体，与前二者相比，它可提供非常紧凑的逼近效果，而且更新计算的效率较高。4离散方向多面体（Discre te Orien tat ion Poly topes， DOP）:离散方向多面体是一 个凸多面体，它的面由一些半空间所确定，这些半空间的外法向是

10、从k个固定的方向中选 取的。与包围球和轴向包围盒相比，离散方向多面体对物体的逼近程度相对较好，与方向 包围盒和凸包相比，它的重叠测试和节点修改耗费相对较低。5.凸包Convex Hull）。凸包是一种极端情况，它提供了物体最紧凑的凸包围体，但它 的重叠测试和节点修改的耗费都相当高。层次包围体的基本算法包括包围体的计算、分割和相交判断等。一般以上几种包围体 （包围盒）的紧凑程度依次增大，但相应地计算复杂度也越来越高。（二）规则分割法规则分割法将空间按照某些规则分割成均匀的单元，然后将空间中每个实体对应到一 个或多个单元中，这一方法很适于实体在空间中均匀分布的稀疏环境。但对于更为一般的 环境，则很

11、难选择一个最优的剖分尺寸，若选择不当，会导致空间耗费大，计算效率低。 常用的空间剖分法有规则网格、KD树、KDB树、BSP树、八叉树和R树系列等（图1）。规则格网空间索引的思路简单，容易理解和实现，其基本思想是将研究区域用横竖线 划分为大小相等或不等的网格，记录每一个网格所包含的地理对象。为了建立空间索引的 线性表，可将空间格网按Mor ton码编码，建立Mor ton码与空间对象的关系。当用户进行 空间查询时，首先计算出用户查询对象所在的网格，然后通过该网格快速查询所选地理对象。规则格网空间索引的查询速度快，但数据量大，数据维护较为困难。KD树（K维搜索二叉树）是将二叉树推广到多维数据的一种

12、主存数据结构，它是一个K 维空间中的二叉树。在每个内部节点中，用一个K-1维的超平面（如二维空间中的线）将 节点所表示的K维空间分成两部分，这些超平面在K个可能的方向上交替出现，而且在每 一个超平面中至少包括一个点数据。在二维坐标下，根据插入点的纵横坐标将空间进行交 叉分裂，把空间数据递归地划分为一个二叉树。为了将KD树存储组织到外存，将其与B树 结合，形成KDB树。八叉树是对二维GIS中四叉树索引进行扩展的一种三维空间数据结构，其基本思想是 将三维区域划分成三维栅格，每一个小正方体（称为一个体元）有一个或多个属性数据。 属性相同的区域用大块表示，而复杂区域则用小块表示，以一大块分为八小块进行

13、规则划 分。建立八叉树索引的难点一是空间分割时应遵循的原则，这可通过规定一个阈值k （表示 空间对象的个数）来解决，即只有当区域中空间对象的个数多于k个时，该区域才需要进 一步划分；二是分辨率问题（即空间分割时允许达到的最小子区是多大），这可以通过规定 一个不再需要分割的体元大小来解决。BSP （Binary Space Par tition）树采用二叉空间分割，其基本思想是：任何平面都可 以将空间分割成两个互不相交的半空间，所有位于这个平面一侧的点定义了一个半空间， 位于另一侧的点定义了另一个半空间。此外，如果在任何半空间中有一个平面，它会进一 步将此半空间分割为更小的两个子空间。可以使用多

14、边形列表将这一过程进行下去，当子 空间中仅存在单个平面时，即可构造出一个描述三维实体对象层次结构的二叉树（BSP树）。 在这个树中，一个进行分割的多边形被存储在树的节点，所有位于子空间中的多边形都在 相应的子树上。这一规则也适用于树中的每一个节点。构造BSP树的关键是如何在三维空 间中快速确定分割平面，以使生成的BSP树尽量趋于平衡。R树是近年应用最广泛的空间索引方法之一，可扩展为支持更高维的数据集。R树采用 最小约束矩形来递归分解索引空间，其存储效率相对较高。但R树的区域之间经常产生重 叠（这种重叠通常会随数据量或空间维数的增加而剧增），因此区域搜索可能需要沿多条路 径进行，从而降低了搜索效

15、率。在3DGIS中，通常需采用启发式算法来降低三维R树节点 的空白区域、各分支的重叠区域以及外包范围的体积，从而减少各分支的重叠区域，提高 节点利用率，改进R树的性能。如可采用球形或规则多面体作为三维空间对象的外包围， 从而避免使用正六面体作为外包围分解三维空间所造成的大量重叠区域和空白区域。国内 外学者对R树提出了许多不同的扩展，包括R+树、R*树等。R+树虽然避免了区域的重叠，但 它可能需要在不同的节点中存储同一个区域的标识，从而降低其存储效率。R*树则尽量减小 节点间的重叠面积，它对上溢节点进行删除，并强制重插入该节点中的所有对象。图1常见的规则分割法oTP r-11 11 1(e) R

16、树（三）组合索引技术从空间索引结构的演化进程看，空间索引技术的发展实际上就是针对不断出现的新需 求，不断将各种索引技术重组、改进索引方法的过程。例如，为了能索引复杂的空间目标, 提出了适合索引二维空间目标的基于实体标志重复存储技术的MKD树；为了将KD树存储组 织到外存，将其与B树结合，提出了 KDB树；为了减少空间目标的重复存储和空间映射， 提出SKI）树；为了减少查询中对外存的访问次数，提出了 Cell树；为了解决R*树适合高维数据集的问题，提出X树等。在3DGIS的实际应用中，往往只有结合多种技术才能将空间索引的功能充分发挥出来。 例如，针对三维城市模型逼真可视化的需要，引入了一种基于R

17、*树的多尺度空间数据库索 引LOD-OR树。LOD-OR树利用八叉树索引限制了 R*树表示的空间，减轻了 R*树插入、删除的 开销，并在查找性能上比R*树有显著的提高，且索引数据量越大，效果越明显；它还采用 细节层次索引方法，在记录的对象中加入三维实体的LOD信息，可以对各种尺度的对象根 据其大小以及与视点的距离、角度的不同，显示不同的细节。这不但保证了实时快速地产 生真实感三维场景，同时由于综合利用了数据库管理技术，也兼顾了不同尺度的空间查询 和分析等操作。在城镇管网信息系统UPNIS中，采用了一种基于固定三维网格空间划分和 面向类对象的二级查询技术的八叉树空间索引机制，有效解决了管网系统中

18、三维空间实体 的空间查询，能够缩小空间查询范围，提高查询效率，进而提高系统的整体性能。另外， 将对象分割与规则分割结合，用层次包围体表示三维实体的边界层次，然后建立三维空间 索引（如BSP索引或八叉树索引），可以加速三维空间检索，这种混合索引技术现在已广泛 应用于三维场景实时绘制（包括可见性判断、碰撞检测、光线追踪和辐射度计算等）。四、3DGIS空间索引方法比较每一种空间索引方法都有其优越性、使用范围和适用对象。选取何种索引机制作为 3DOIS空间数据库的空间索引，要根据实际情况和应用需要来确定。目前，多数GIS软件采 用多种索引机制并存、取长补短的策略。表1是在对各种类型索引研究的基础上归纳出来 的索引综合性能对照表，对实际应用具有参考意义。表1 3D GIS空间索引方法对比索引名称划分区域方法适合对象优点缺点规则网格面域等