摘要
三维空间可视查询作为一种贴近人们实际生活的查询技术，受到国内外专家和学者的广泛关注。三维空间数据具有数据量大、形态自由、分布随机的特点，给可视查询带来巨大的挑战。大多基于二维空间的查询方法对于三维空间是不适用的，当前的三维空间可视查询算法也在一定程度上存在模型设计不合理，查询效率低，不适合精确可视化查询和预测的缺陷，因此我们需要根据用户的实际需求建立一套关于三维空间可视查询的数据模型、索引结构、查询算法的研究方法。本文以三维空间中的数据对象为研究对象，从索引结构的构建到预测对象可视化查询方法进行研究。 首先，提出了一种三维空间数据对象混合索引结构AG-RTree，并在此基础上进行区域查询。单一的索引结构在处理大量的三维空间数据时，一颗平衡的R树构建困难并且中间结点相互重叠会造成多路查询。网格索引结构虽然具有较高的查询效率，但存在内存溢出的风险。三维空间数据对象混合索引结构解决了上述问题，采用自动划分网格，在子网格中构建R+树的方式，将构建索引的结点数量控制在一个阈值内，降低树形结构的深度，实现高效查询。在此基础上提出了区域查询算法，为区域数据Skyline查询和精确数据查询奠定基础。 其次，提出了三维空间区域数据对象Skyline可视查询算法。传统的Skyline查询算法只考虑非空间因素支配且各因素之间相互独立，没有权重的概念，不符合人们对事物的认知判断。为此，本文在三维空间中引入空间属性支配和空间支配域的概念，在三维空间中构建支配域进行数据筛选，减少参与计算的空间数据，提高查询效率。在障碍空间中构建三维可视图，通过最短路径算法计算障碍距离，实现三维障碍空间中的Skyline查询算法。对三维空间数据组进行组间排序和筛选，通过组内Skyline点集和全局Skyline点集获取全局组内Skyline点集，根据三维空间组属性偏好值对数据组进行排序，实现三维障碍空间组Skyline查询。 再次，提出了三维空间区域数据对象凸壳模型精确可视查询算法。常用的三维空间数据模型为最小外接矩形包围盒模型和方向包围盒模型，在空间上存在冗余，会造成误差，不适合精确可视查询，而凸壳模型可以解决该问题。采用凸壳模型表示三维空间中的目标物体和障碍物，利用GJK碰撞检测算法精确判断目标物体的可视性。给出凸壳模型索引结构HTree的构建、维护及K近邻查询算法。在K近邻查询中增加障碍物，并对障碍物分类实现三维空间物体可视性检测算法，给出三维障碍空间数据对象精确可视K近邻查询算法。 然后，提出了三维空间可视对象轨迹预测算法。三维空间物体在路网中的移动轨迹是可以预测的，根据预测的情况可以提前进行一些准备和处理工作，使移动的物体可控。给出转移概率、转移概率矩阵、轨迹区域的相关定义和定理，计算可达路径、转移概率矩阵，得到移动对象在有障碍物的情况下从起点到终点概率最大的可达路径，在此基础上进行轨迹预测，获得轨迹预测路径。 最后，提出了三维空间预测轨迹中数据对象可视化查询算法。根据三维空间移动对象的预测轨迹，查询最优的K个观察点，实现移动物体动态可视化监控。计算移动物体在当前时刻所处的位置和可视状态，对移动物体进行网格划分，采用八叉树索引结构存储网格单元，通过剪枝和过滤算法快速获取物体的可视化网格单元，实现多障碍物、多观察点K查询点可视化查询算法。
NETL