Dissertation > Excellent graduate degree dissertation topics show

Parallel generation algorithm of planar Voronoi diagram based on a multi-core CPU

Author: LiShuYan
Tutor: CaoZuo
School: Shaanxi Normal University
Course: Applied Computer Technology
Keywords: Voronoi diagram Vector method Grid method OpenMP Public facility location
CLC: TP391.41
Type: Master's thesis
Year: 2010
Downloads: 92
Quote: 2
Read: Download Dissertation

Abstract


Voronoi diagram is a very important part of computing geometric them, and in many areas which have important applications. Voronoi diagram has recently, adjacency many properties and more systematic theoretical system, and now in the field of graphics, mechanical engineering, geographic information systems, virtual reality, robot path planning, image processing, CAD and other widely used, but also solve the distance calculation, collision detection, path planning, effective tool for computational geometry other problems. In view of its important applications of such a wide range of application areas and in all aspects of research Voronoi diagram generation algorithm is very theoretical and practical significance. Generate Voronoi diagram there are two types: vector and raster methods, vector method to generate the Voronoi diagram is valid for discrete points, lines, surfaces and complex spatial objectives, algorithms and data structures are very complex, and achieve great difficulties, advantage can be obtained more accurate Voronoi diagram; grid method generates a Voronoi diagram is relatively simple, especially for more complex spatial target number, but the grid generation efficiency is relatively low there are some errors in the accuracy. In view of these circumstances, the processing of the data in this article is the actual map data space goals are more complex, so using the grid method to generate the Voronoi diagram. Solve the large amount of data grid Voronoi diagram algorithm in order to improve the computational efficiency of the parallel thinking applied Voronoi diagram algorithm. However, the application of the multi-core platform in this area has not yet commenced. Therefore, we carried out the Voronoi diagram generation multi-threaded parallel optimization, application performance greatly improved. On multi-core platform, resulting in efficient Voronoi diagram generation algorithm, to prove the superiority of multicore platforms and parallel computing theory. This article is the summary of the work done as follows: (1) On the basis of previous work, the use of mathematical morphology expansion operator to generate raster Voronoi diagram, this algorithm will be applied to the actual map data above. The actual map data is generated raster Voronoi diagram. This part which, in this article from the following four aspects to consider: ① growth element for point targets; ② growth element for a linear object; ③ growth element planar target; ④ growth elements of point, line, surface composite target . (2) in the multi-core platform combined with the theory of parallel computing, multithreaded parallel optimization of the Voronoi diagram grid algorithm to improve efficiency. Reached research purposes. (3) Finally, the Voronoi diagram applied to urban public facility location analysis and optimization of Xi'an city schools and the layout of the park, and some more reasonable suggestions.

Related Dissertations

  1. Online Education News Text Categorization System Design and Implementation,TP391.1
  2. Garage management system line method of generation and reuse,TP315
  3. Image-based detection of wheel alignment parameters of the mathematical model and algorithm,TP391.41
  4. Modern architecture bolted and welded steel welding stress and deformation of,TU391
  5. Precision fluid animation fast simulation,TP391.41
  6. Based on Voronoi diagram of image information hiding method,TP309
  7. Paralleling Genetic Annealing Algorithm with OpenMP,TP301.6
  8. FCM combines multi-resolution image cone multicore parallel image segmentation algorithm,TP391.41
  9. Study on Coordinating the Layout of Urban-Rural Construction Land,F301
  10. Application of Parallel FDTD and MPSTD Algorithm in EM Scattering,O441.4
  11. A Parallel DDM Preconditioner for Solving Finite Element Discretization of Elasticity Problem in Three Dimension,O241.82
  12. Study on New Producing Zones of Non-fluorine and Low-fluorine Continuous Casting Mould Fluxes,TF777
  13. Meshless Method and Its Application in Metal Forming Process with Contact Interface of Arbitrary Shape,TG306
  14. BSD protocol stack performance analysis and optimization of parallel,TP393.04
  15. Software optimization techniques in software development projects,TP311.52
  16. The Research of Three-dimensional FDTD Parallel Algorithm Based on MPI and OpenMP,TN011
  17. Approximate expansion patch comprehensive analysis and forming simulation,TG386
  18. Research on the Path Planning Based on Space Restriction and the Scene Simulation,U116.2
  19. Discuss on Painting Philosophy and Painting of Song Dynasty,J209.2
  20. Autonomous mobile robot path planning method,TP242
  21. Research on the Discovery and Restoration of Blind Spots in Wireless Sensor Networks,TN929.5

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Pattern Recognition and devices > Image recognition device
© 2012 www.DissertationTopic.Net  Mobile