Modeling Algorithm Of Spherical Total Factor Voronoi Diagram

As the highest goal of the Geographic Information System, the birth and research of Digital Earth brings great challenge to traditional expression, retrieve, analyze and modeling of spatial data and guides these techniques develop from2D plane to higher dimension. As the base of research and development of Globla GIS, expression of geographic data attract more and more researchers’ attention.Voronoi diagram is a classical mathematic object. And the full-feature Voronoi diagram is defined to adapt to the reality spatial object that its growth source is point, line and polygon feature element set. Voronoi diagram has particular mathematical properties, so it is the most prospective solution in dynamic field of GIS. Voronoi provides a new way of space adjacent cognitive, which could fundamentally solve the problem of spatial adjacent calculation. Therefore the generation of spherical full-feature Voronoi diagram is dramatically important for managing global spatial data and sustaining Spherical spatial relationship dynamically.Currently, the research of generation algorithm about spherical Voronoi looks not so sufficiently. Typical generation algorithm about spherical Voronoi diagram includes the insert method, which was proposed by Augenbaum, this method gives the generation algorithm base on n numbers of points on the surface of sphere, meanwhile its time complexity is O(n2). As well as the divide and conquer algorithm proposed by Robert is O(nlogn). Notwithstanding, these two kinds of algorithms are vector algorithm for spherical discrete point set, they can not process line set or polygon set. The QTM (Quaternary Triangular Mesh)-based Algorithm for the Generating of Voronoi Diagram for Spherical Objects was proposed by Xuesheng Zhao, specialized in the raster method for the spherical various data set, which has many advantages such as easy to manipulate and could process all kind of geographical entity, but the space complexity and time complexity restrict its development and applications.Considering the limitations of traditional vectorial and raster generation algorithm of Voronoi diagram, this paper propose a spherical Full-Feature Voronoi diagram generation algorithm based on vector data. Through designing an integrated perspective projection model, data and its connected relationship on the surface of a sphere will be projected to the Euclidean plane. And the discrete feature sets on this Euclidean plane will become point sets for generating sub-Voronoi diagrams. Then these sub-Voronoi diagrams will merge each other if they belong to the same feature to accomplish the generation of spherical full-feature Voronoi Diagram. The result of empirical experiment shows that this algorithm is viable. The accuracy of this algorithm and the rationality and flexibility of perspective projection model has been discussed at the end of this thesis.