Parallel Generation Algorithm Of Planar Voronoi Diagram Based On Multi-core Cpu

Voronoi diagram is a very important and practical part of them computational geometry, and in many areas, which has important applications. As the Voronoi diagram with the recent nature of adjacency and many other nature and a more systematic theoretical system, has now been in graphics, mechanical engineering, geographic information systems, virtual reality, robot path planning, image processing, CAD and other areas to be widely used, also for resolving the distance calculation, collision detection, path planning, computational geometry an effective tool for other issues.Given that it has such a wide range of applications and important applications in various fields to study the Voronoi diagram generation algorithm is very necessary.At present, the generated Voronoi diagram in two ways:Vector_based method and Raster_based method, Vector_based method for generating Voronoi diagram is very effective in terms of discrete points, but for the lines and other complex spatial objectives, algorithms and data structures are very complex and are difficult to achieve, the advantage of Vector_based method is obtained more accurate Voronoi diagram; Raster_based method for generating Voronoi diagram is relatively simple, especially for more complex spatial objects, because there are a great number of grids, generating a relatively low efficiency, there are some in the precision deviation. For these conditions, this processed data is the actual map data, more complex spatial objects, so using the Raster_based method to generate the Voronoi diagram.As the Voronoi diagram generation algorithm to solve the huge data, in order to improve the computational efficiency, parallel thinking applied to Voronoi diagram generation algorithm. However, the application of multi-core platform in this area has not yet commenced. Therefore, this paper carried out on the Voronoi diagram generation for multi-threaded parallel optimization, so that application performance greatly improved. And multi-core platform has been verified to be more efficient Voronoi diagram generation algorithm, multi-core platforms and proved the superiority of parallel computing theory.This paper summarized the work done by the following:(1)In previous work on the basis, the dialate of the use of mathematical morphology operators to generate Raster_based Voronoi diagram, and this algorithm is applied to the actual map data. Generate the actual Voronoi diagram of Raster_based data. (2) In multicore parallel computing platform combined with the theory of successfully Voronoi diagram grid algorithm is multi-threaded parallel, the effective efficiency. And achieved the purpose. In this part, the paper considers the following four aspects:①growth element are the point targets;②growth element are the line targets;③growth element are the polygon targets;④growth element are composite targets which contain point, line and polygon targets.(3) The Voronoi diagram applied to the urban public facility location analysis and optimization in the city of Xi'an in schools and park layout analysis and extraction of a number of recommendations.