| Computational Geometry is a new and fearfully vigorous subfield in the theoretical computer science field. Minkowski sum algorithm has the great significance in theory and application as an embranchment of Computational Geometry. It plays an important role in Robotics, Computer Graphics, CAD, and so on. How to provide the effective basic algorithm and theroy basis for some fields is always the research task of the home and foreign scholars.Overlay algorithm is an important step for computing Minkowski sum of two convex polyhedrons. So firstly, the overlay algorithm of planar subdivision is discussed from a completely new perspective for overcoming the limitation of old algorithm, and an overlay algorithm of simple planar convex subdivision in triangle is proposed in the paper. The whole algorithm consists of three steps: computing intersection, reconstructing topology and constructing the Doubly Connected Edge List for overlay graph. At the same time, validity and complexity of the algorithm are analyzed in the paper.Secondly, for decreasing the amount of computing overlay of two planar subdivisions and improving the efficiency of algorithm, Regular Tetrahedron Central Projection is proposed in the paper. According the conversion relation of coordinates, it can reduce the problem in 3D to one in 2D.Thirdly, for exactly computing the Minkowski sum of two convex polyhedrons, an algorithm is proposed in the paper, and it is based on Regular Tetrahedron Central Projection. The algorithm can compute overlay of four pairs of planar subdivisions respectively by the overlay algorithm proposed in the paper, and it fulfills the distribution for attributes. In the end, we can obtain Regular Tetrahedron Central Projection of Minkowski sum polyhedron, and get the Minkowski sum polyhedron by computing contrary mapping. At the sametime, time complexity of the algorithm is analyzed in the paper.Finally, we validate the above algorithms and give the results. |
PDF Full Text Request