Fast Intersection Detection And Distance Computation Of Convex Polygons Based On Voronoi Diagram

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:...