QTM-based Spherical Voronoi Diagram Generating Algrotihms And Its Application

With the deepening integration of the global ecological environment, society and economy, our study area has been expanded gradually from local area to the entire earth. The rapid development of modern earth observation technology, such as photogrammetry, remote sensing and global positioning system has resulted in the possibility of getting global, multi-scale and multi-temporal spatial data. A global, continuous and multi-scale dynamic data model is needed in order to manage and analyse the spatial data effectively. The spherical Voronoi diagram, which has the property of natural nearby, dynamic stability, has become one of the most potential solutions to manage and analyse spatial data.Aiming at the deficiencies in the existing spherical Voronoi diagram generating algorithm, spherical Voronoi diagram generation algorithms, dynamic maintenance and applications are studied in this paper. The main works are as follows:(1) A QTM-based belonging algorithm for generating spherical Voronoi diagram is proposedQTM, which is more uniform than the Longitude-Latitude grid, is used as the minimum unit when generating spherical Voronoi diagram. Distances from each grid to all the sites are computed and compared in order to get the nearest site of the grid. When the computation and comparsion finished, grids have same nearest site form the Voronoi region of the site. Results show that Voronoi errors can be limited within 2 grids and the precision problem in the existing raster-based spherical Voronoi diagram generating algorithms is sloved.(2) The belonging algorithm is optimized by GPU parallel computation(hardware optimization)Massive computation and comparison have to be done in the belonging algorithm. Meanwhile, the computation and comparison for each of the grids are similar and independent to each other. So the algorithm has the characteristic of compute-intensive, instruction similarity and mutual independence, which is very suitable for GPU single instruction multiple data computing model. So, CUDA is used in this paper to implement the belonging algorithm. Also, GPU global memory, shared memory, constant memory and register are used to optimize the algorithm in order to improve the efficiency. Results show that the efficiency can be improved more than 100 times after the optimization.(3) The belonging algorithm is improved by the sweeping method(algorithm optimization)A QTM grid always has the same nearest site with all or some of its neighbor grids, so neighbor grids can be used to propagate the nearest site. When the spherical surface is subdivided in QTM mode, sweep the sphere in the order left to right, top to bottom and right to left, bottom to top. When sweeping, compute and compare the distances from the grid to all of its neighbors’ nearest sites and get the nearest one as the nearest site of the grid. When the sweeping progress finished, the Voronoi diagram is obtained. Results show that many unnecessary computations in the belonging algorithm are reduced in the improved algorithm. Also, the improved algorithm can get a nearly constant efficiency(independent to the number of sites) in specific QTM level.(4) The belonging algorithm is improved using the hierarchy of QTM(scale optimization)The difference between Voronoi diagrams genenerated in different QTM levels are only on Voronoi boundaries. Voronoi diagram generated in heigher levels has more precise boundaries and vice versa. So when heigher level Voronoi diagram is needed, we can compute lower level Voronoi diagram first. Then extract the Voronoi boundaries and subdivide the grids on the boundaries again. At last, compute the nearest sites of the sub-grid of the boundary grids using a local belonging algorithm. Repeat the steps until the resolution is satisfied. Results show that, the efficiency is improved greatly and Voronoi diagrams of much higher levels can be obtained using the improved algorithm.(5) An experimental system is designed and developed to verify the proposed algorithmsAn experimental system based on the.net framework is designed and developed using Microsoft Visual C#/C++ and CUDA that is a GPU parallel programing architecture. Global administrative data, rivers, lakes and mainland border lines in different scales are used to verify the proposed spherical Voronoi diagram generating algorithms from the aspect of efficiency and precision. In addition, dynamic maintenance operations like insertion, deletion and update methods of spherical Voronoi diagram are given in the system. Also, a raster Voronoi-based spherical natural neighbor interpolation algorithm is given based on the dynamic insection method and a CVT(Centroidal Voronoi Tessellation)-based global terrain adaptive modeling method is explored tentatively.