Dissertation > Excellent graduate degree dissertation topics show

Fast Intersection Detection and Distance Computation of Convex Polygons Based on Voronoi Diagram

Author: ZhaoWei
Tutor: MengXiangXu
School: Shandong University
Course: Computer Software and Theory
Keywords: Collision Detection Voronoi Diagram Intersection Detection Polygon Distance Computation
CLC: TP391.7
Type: Master's thesis
Year: 2006
Downloads: 196
Quote: 0
Read: Download Dissertation

Abstract


Distance computation and the intersection detection of polygons are the basal problems of computer-aided design and manufacturing (CAD/CAM), computational geometry, robotics and automation, engineering analysis, computer graphics, virtual reality, etc., and also are the common methods to solve the problems of collision detection, path planning, clipping, visibility and so on. The merits of these algorithms also affect the corresponding application algorithms. The construction of the corresponding algorithms of convex polygons or polyhedrons is simple, so we often solve a complex problem by breaking a complex object into convex polygons or polyhedrons.So we mainly study the methods of fast intersection detection and distance computation of two convex polygons in this thesis. By analyzing deeply the properties of the Voronoi diagram of polygons and using the space adjacency and proximity recording by polygons’ outer Voronoi diagrams, we design and implement a fast intersection detection algorithm of two convex polygons and a fast distance computation algorithm between two disjoint convex polygons based on the outer Voronoi diagram of convex polygons. The two algorithms are simple and comprehensible, are easy to implement and fast. The two algorithms can be applied in 3D indoor scene (such as digital museum and so on) to solve the problems of path planning, collision detection, laying out collection and so on.The major works and contributions of this thesis are:

Related Dissertations

  1. Study on Model-Based Visualization of Rice Roots,S511
  2. Key Technologies of Modeling and Simulation in Virtual Surgery,TP391.41
  3. Research on Security Component Management of Information System Based on CORBA,TP309
  4. The Research on Carving Surface Modeling Based on Planar Random Closed Graph,TP391.72
  5. The Study and Application of Digital Tourism Based on Three Viewing Technology,TP391.9
  6. Research of Visualization of Multi-dimension Data,TP311.13
  7. The Building and Drawing of Geological Isoline Map,TP391.41
  8. A wide range of low-cost sensor configuration algorithm,TP212.9
  9. Dynamic Cloth Simulation under Realistic Scene,TP391.9
  10. Shape Preserving Parametric Spline Curve with Given Tangent Polygon,TP391.72
  11. On Fictitious Campus Three-dimensional Model and It’s Designment,TP391.9
  12. Research and Realization of Tri-Dimensional Interactive Simulation System Based on K7 Bogie,TP391.9
  13. Research of the Key Questions of RFID System,TP391.44
  14. The Automatic Generation Technology of Levels-of-Detail Landmark Model and Its Realization of 3D Visualization,TP391.9
  15. Research on the Spatial Distribution of Shandong Peninsula Urban Agglomeration,P208
  16. Research on Localization Algorithms for Mobile Nodes in Wireless Sensor Networks Based on Monte-Carlo,TP212.9
  17. Research on Construction of Model Information Database and Colission Detection Technology for Virtual Assembly System,TP391.7
  18. Research on Virtual Surgery System for Appendectomy,TP391.41
  19. Research of Spatial Index Method Based on the Convex Polygon Approach,TP391.41
  20. Research on Soft-object Deformation in the Computer Animation,TP391.41
  21. Research on Mathematical Models and Optimization Algorithms for Facility Location Problems,F717

CLC: > Industrial Technology > Automation technology,computer technology > Computing technology,computer technology > Computer applications > Information processing (information processing) > Machine-assisted technology
© 2012 www.DissertationTopic.Net  Mobile