论文部分内容阅读
作为地理信息系统发展的最高目标,数字地球的诞生与研究向传统的空间数据表达、检索、分析和建模等方面提出了新的挑战,引导他们由原来基于二维平面向着更高的维度发展。地球空间地理数据的表达作为全球地理信息系统(GlobalGIS)的研究与发展的基础,吸引着越来越多研究者的目光。Voronoi图是一个经典的数学对象,全要素Voronoi图是在点生长源的基础上定义生长源为点、线和面要素的Vororoi图,以适应实际空间目标。Voronoi具有独特的数学性质,是迄今为止动态GIS领域最有希望的解决方法,并且提供了一种新的空间邻近认知途径,有望从根本上解决地理信息系统中的邻近计算问题。所以,建立基于全要素Voronoi图的球面表达对于管理全球空间数据和维护球面空间动态关系具有重大价值。目前,国际上对于球面Voronoi图生成算法的研究并不多且最新成果比较少。比较典型的是Augenbaum利用“插入法”给出的球面上n个点的、Voronoi图生成算法,时间复杂度为O(n2);Robert提出的“分治算法”,时间复杂度为O(nlogn);童晓冲等提出的不同集合的球面矢量Voronoi图矢量生成算法;赵学胜提出的基于铺盖的球面栅格Voronoi图生成算法。前两种算法都是针对球面离散点集的矢量算法,目前难以应用于线要素、面要素。第三种方法是基于偏置曲线的球面Voronoi生成方法,可对线集与面集进行操作,概念直观且易于扩展,但是实现较为困难且随着数据规模的扩大算法时空复杂度呈高次幂增长。最后一种是针对球面各种集合的栅格方法。栅格方法具有高维扩展性,全要素性和易实现性等优点,但是时空复杂度较大,制约了球面Voronoi的发展应用。针对球面、Voronoi图算法的问题,作者提出了一种新的球面矢量数据全要素Voronoi图构建方法。利用特定的距离值将线状、面状要素离散为包含属性的点集。首先,针对点集生成要素的Voronoi子图;其次,根据点与要素的隶属关系合并子图来构建平面的全要素Voronoi图;最后,利用中心透视投影,将球面目标一体化投影至平面,在平面上完成全要素Voronoi图生成后再反向投影回球面,实现问题的降维处理。实验验证本文算法的正确性,并针对算法的效率、全要素Voronoi图的精度和投影算法合理性与适用性给予讨论。