Voronoi Diagram Grid Algorithm Research

Voronoi diagram is an important research in computational geometry content, in meteorology, geology, geographic information systems, urban planning, chemistry, ecology, image processing, computer graphics, virtual reality, CAD, collision detection and robot path planning and other fields Widely used, but also solve the Delaunay triangulation, skeleton computation, convex hull computation, and computational geometry minimum spanning tree problem of generating such an effective tool.Therefore, it is particularly important to construct Voronoi diagram, Voronoi diagram generation method consists of raster and vector generation method. Vector Method earlier, many methods, the most typical methods are:incremental method, divided method and indirect method. Vector method has the advantage of the Voronoi diagram generated high precision; a problem as on the growth element is required, only a point and a half lines, if the line and face the need to undermine the integrity of its decomposition, and the storage structure is more complex. The problem with the vector, people began to study the raster generation algorithm. Element grid is no limit on the growth, but the resulting Voronoi diagram low accuracy, time-consuming. There are two typical raster methods:Voronoi diagram based on the traditional distance transform grid method and the expansion initiative based on the active pixel grid method for Voronoi diagram.In practice, usually the actual map data as the growth Voronoi diagram element. Map data has two main characteristics:1 amount of data.2 usually contains points, lines, types of goals, and from points, lines, a combination of complex spatial entities complex object, it is difficult to generate the actual vector method using the map Voronoi diagram. Compared with vector, raster method can handle complex spatial entities, but to consider the algorithm efficiency and accuracy issues. By adjusting the grid size, grid subdivision to ensure the accuracy of Voronoi diagram. Map data itself, taking into account the amount of data to larger grid size gradually refined with the amount of data will further increase efficiency will be lower. To improve the efficiency of the algorithm, this paper applies parallel processing technology Voronoi grid generation algorithm, Voronoi diagram proposed two parallel grid generation algorithm, an initiative based on the growth of active pixels, and the other is based on the attribution method improved, At the same time with the sub-grid that can better guarantee that the generated Voronoi diagram of high precision and high efficiency. This paper summarized the work done by the following: (1) This paper proposes a parallel MPI-based raster Voronoi diagram generation algorithm to generate active pixels active growth as the basis of Voronoi diagram is proposed based on MPI's line of type, column type, and the chessboard 3 different methods of data partitioning in parallel Voronoi diagram grid generation algorithm, and 3 different methods of data partitioning efficiency and scalability analysis. Through multiple sets of comparative experiments, show that the parallel algorithm and the combination of sub-grid accuracy can be guaranteed under the premise of effectively improve the efficiency of the algorithm, but the efficiency for the cluster machines is not obvious.(2) Given the prevalence of the cluster machines, and since the original serial algorithm for cluster machines not good, so we improve the original serial algorithm and improved algorithm based on the proposed new parallel algorithm based on MPI. Through several experiments, it is shown that the parallel algorithm can improve the efficiency of the algorithm and apply the cluster machines. Also, because now most of the commercialization of multi-core processor cluster system clusters, hybrid programming model is more suitable for the model, it is also proposed based on MPI+OpenMP parallel algorithm, a large number of experiments show that the hybrid programming model has been improved in performance.(3) Presented in Wang Xinsheng a new approach based on the grid, a new blank grid to determine ownership of the raster method-Improved attribution method, by a large number of experiments show that:(a) inefficiency of the algorithm is not Simply the number of decisions by the blank grid, also need to take into account the number of spatial objects, distribution, shape; (b) algorithm has higher performance than the traditional grid method.(4) First proposed on the basis of MPI-based improved attribution method Voronoi diagram parallel raster algorithm, proved by several experiments:the parallel algorithm and sub-grid that ensure the accuracy can be combined in order to improve the efficiency of the algorithm, and for the cluster machines. Then made on the basis of OpenMP+MPI improved attribution method Voronoi diagram parallel raster algorithm, by comparing a large number of experiments, show that the hybrid programming model has been improved in performance.