球面全要素Voronoi图构建算法

发布时间：2018-08-01 19:10

【摘要】：作为地理信息系统发展的最高目标,数字地球的诞生与研究向传统的空间数据表达、检索、分析和建模等方面提出了新的挑战,引导他们由原来基于二维平面向着更高的维度发展。地球空间地理数据的表达作为全球地理信息系统(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图的精度和投影算法合理性与适用性给予讨论。
[Abstract]:As the highest goal of the development of GIS, the birth and research of digital earth presents new challenges to the traditional spatial data representation, retrieval, analysis and modeling. Guide them from the original two-dimensional plane to a higher dimension. As the basis of the research and development of global geographic information system (GlobalGIS), the expression of geospatial geographic data attracts more and more researchers' attention. Voronoi graph is a classical mathematical object. Based on the point growth source, the total element Voronoi diagram defines the growth source as the Vororoi diagram of the point, line and surface elements, which is the most promising solution in the field of dynamic GIS so far, in order to adapt to the actual spatial target. The Voronoi has unique mathematical properties, so it is the most promising solution in the field of dynamic GIS up to now. It also provides a new cognitive approach to spatial proximity, which is expected to fundamentally solve the problem of proximity computing in geographic information systems (GIS). Therefore, the establishment of spherical representation based on all-factor Voronoi graphs is of great value in managing global spatial data and maintaining the spatial dynamic relationship of the sphere. At present, there are few researches on the generation of spherical Voronoi diagrams in the world. Typically, Augenbaum uses the "interpolation method" to generate the Voronoi diagram of n points on the sphere. The time complexity of the algorithm is the divide-and-conquer algorithm proposed by O (N2) Robert. The time complexity is O (nlogn); Tong Xiaochong et al. The algorithm for generating spherical vector Voronoi graph with different sets and Zhao Xuesheng's algorithm for generating spherical grid Voronoi graph based on paving. The first two algorithms are vector algorithms for spherical discrete point sets, which are difficult to be applied to line elements and surface elements. The third method is spherical Voronoi generation method based on offset curve, which can operate line set and surface set. The concept is intuitionistic and easy to expand, but it is difficult to realize and the space-time complexity increases with the expansion of data scale. The last one is a grid method for various sets of spherical surfaces. The grid method has the advantages of high dimensional expansibility, full element and easy realization, but the complexity of time and space is large, which restricts the development and application of spherical Voronoi. To solve the problem of the algorithm of spherical Voronoi diagram, a new method of constructing full-element Voronoi diagram of spherical vector data is proposed. The linear and surface elements are discretized into a set of points containing attributes by using specific distance values. Firstly, the Voronoi subgraph of the elements is generated for the point set; secondly, the Voronoi graph of all elements of the plane is constructed according to the subgraph of the subordinate relation between the point and the element; finally, the spherical object is projected to the plane by using the central perspective projection. The whole factor Voronoi graph is generated on the plane and then projected back to the spherical surface to reduce the dimension of the problem. The correctness of the proposed algorithm is verified by experiments, and the efficiency of the algorithm, the accuracy of the full element Voronoi diagram and the rationality and applicability of the projection algorithm are discussed.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：P208

【参考文献】