三维空间索引与显示判断算法

三维空间索引机制

空间索引是对存储在介质上的数据位置信息的描述，用来提高系统对数据获取的效率。

快速检索到有效模型的前提是建立快速的空间索引机制。

每一种空间索引方法都有其优越性、使用范围和适用对象。选取何种索引机制作为3DGIS空间数据库的空间索引，要根据实际情况和应用需要来确定。目前，多数GIS软件采用多种索引机制并存、取长补短的策略。

常见的三维空间索引结构

对象分割法：一般由层次包围体实现。层次包围体是一种简单的树结构，它用一些特定的方法对空间实体对象进行分割，最终将树的每一个节点保存为所在层次的包围体信息，叶子节点则存储基本对象。如当对两个物体做碰撞检测时，首先检测两者的包围体是否有交，若不相交，则说明两个物体未相交，否则再进一步对两个物体进行检测。求包围体的交比求物体的交要简单得多，以便快速排除很多不相交的物体，从而加速检索算法。

常见的包围体有5种：

包围球：是一种最简单的包围体，易于计算，非常易于做重叠测试和节点修改，但缺点是与物体的逼近程度较差；

轴向包围盒：一种长方体的包围体，其各轴的方向与坐标轴的方向一致，它也是一种易于做重叠测试的包围体，但与物体的逼近程度也较差；

方向包围盒：一个任意方向的长方体包围体，与前二者相比，它可提供非常紧凑的逼近效果，而且更新计算的效率较高；

离散方向多面体：是一个凸多面体，它的面由一些半空间所确定，这些半空间的外法向是从k个固定的方向中选取的。与包围球和轴向包围盒相比，离散方向多面体对物体的逼近程度相对较好，与方向包围盒和凸包相比，它的重叠测试和节点修改耗费相对较低；

PS：凸包：是一种极端情况，它提供了物体最紧凑的凸包围体，但它的重叠测试和节点修改的耗费都相当高。

规则分割法：将空间按照某些规则分割成均匀的单元，然后将空间中每个实体对应到一个或多个单元中，这一方法很适于实体在空间中均匀分布的稀疏环境。但对于更为一般的环境，则很难选择一个最优的剖分尺寸，若选择不当，会导致空间耗费大，计算效率低。常用的空间剖分法有规则网格、KD树、KDB树、BSP树、八叉树和R树系列等。

组合索引技术：空间索引技术的发展过程实际上就是针对不断出现的新需求，不断将各种索引技术重组、改进索引方法的过程。在3DGIS的实际应用中，往往只有结合多种技术才能将空间索引的功能充分发挥出来。

3D GIS空间索引方法对比

基于索引的三维空间查询步骤

① 根据用户的查询区域计算待搜索的索引号集合，包括查询区域跨越的子结点及其父结点对应的索引号；

② 根据索引号集合查询空间对象选择集, 创建SQL查 询语句；

③ 把选择集中每个对象的最小外接矩形和查询对象的最小外接矩形进行比较,过滤掉不在查询对象的最小外接矩形中的对象，得到较为精确的选择集。