K - Order Voronoi Diagram Adjacent Parallel Algorithm And Its Application

Spatial adjacent relationship is an important spatial relationship. It is a kind of spatial relationship that is directly adjacent. There is no other spatial target between two spatial targets. Any spatial modeling system must contain adjacent relationship of recognition. Voronoi diagram and Delaunay triangulation are two kinds of spatial adjacent relationship models. Spatial adjacent relationship is widely used in the field of the natural surface interpolation, the query of spatial adjacency, the surface feature line extraction, etc.Spatial adjacency problem apply Voronoi diagram k-order neighbourhood to assist select objects. It not only can avoid choosing process repeatedly and reduce the searching range, but also is closer to human cognitive approach which can improve the efficiency and accuracy. Raster-based Voronoi diagram is easier to deal with various complex spatial objects. This paper discuss Voronoi diagram k-order neighbourhood generation algorithm in raster-based data model, but the generated Voronoi diagram precision depends on the grid size. In order to improve the precision of Voronoi diagram, the method of this paper mainly subdivide grid. However, grid is smaller, amount of calculation is bigger. So the method of this paper adopts parallel computing. In the view of data communication in the process of Voronoi diagram generation and data broadcasting, collection and operation in the process of Voronoi diagram k-order neighbourhood generation algorithm, the method of this paper adopts message passing programming model.This paper gives deep discussion and research above Voronoi diagram k-order neighbourhood generation algorithm, the main work includes:(1) This paper analyse the shortage of Wavefront method, Intersecting wave front method and Pass through method which are proposed by Zhao R. Wave method is suitable for the calculation of lower-order neighbourhood, Intersecting wavefront method based on Wave method is improved, it is suitable for the calculation of higher-order neighbourhood. But Wavefront method, Intersecting wavefront method possess complex data structure and their calculation are difficult. Pass through method possesses high computation efficiency and their data structure is simple, but the desires of order is the approximate solution, only specific space can get the optimal solution in the model. This paper propose matrix iteration algorithm which combine with relation data model. Voronoi diagram k-order neighbourhood matrix iteration algorithm advantages:The algorithm generate spatial all the k-order neighbourhood objects’ relations by one time, don’t repeat calculation and convergence. The algorithm is suitable for the parallel processing large data sets, using matrix storage k-order neighbourhood objects’ relations, is helpful for parallel computing to data block, broadcast, gather and reduce, etc.(2) The process of Voronoi diagram k-order neighbourhood generation needs data communication. This paper adopts MPI parallel programming model of message passing. MPI parallel computing model significantly improves the raster-based Voronoi diagram k-order neighbourhood generation algorithm computation efficiency. The algotithm possesses the outstanding advantages of multiple processes, move running time knee point backrward and get higher speed-up, the higher percision of Voronoi diagram in raster-based data model and the more number of the spatial objects.(3) Public service facilities layout rationalization is a current important subject in our country which overall urban-rural development and build a harmonious socialist society. Using the ArcGis software to preprocess sample map-vector-based data to raster-based data. This paper apply Voronoi diagram k-order neighbourhood to emergency medical service system and school site selection, this paper give person some advice respectively from the two angles of the rationality of people travel choice and facility location optimization.