Research On Decomposition And Computing Minkowski Sum Of Non-convex Polyhedral

Computational Geometry is an important embranchment of computertheoretical science. The subject has already made a tremendous developmentand produced a series of theoretical results. Minkowski sum algorithm hasthe great significance in theory and application as an embranchment ofComputational Geometry. It plays an important role in robotics, dynamicsimulation, computer graphics, and so on, especially in the field of robotics, itis an important tool for computing collision-free path. Therefore, how tocalculate the path of obstacle avoidance quickly and accurately has been animportant research subject of the home and foreign scholars.Firstly, the existed approach of Minkowski sum of two convexpolyhedral was researched in this paper. In order to reduce the amount ofcomputing overlay of two planar subdivisions and improve the efficiency ofthe algorithm, the concept of point projection based on the round face ofcenter is propsed in the paper.Secondly, convex decomposition is an important step of computingMinkowski sum of two non-convex polyhedral. So, for effectively computingthe Minkowski sum of non-convex polyhedral, a new algorithm is propsed in the paper, witch to decompose non-convex polyhedron that base on theminimum cut surfaces of approximate, without adding any new vertices.thealgorithm adding the lastest cut fases of approximate using the best loop todecomposition non-convex polyhedral. At the same time, the complexity ofthe algorithm is analyzed.Thirdly, the overall idea of computing the Minkowski sum ofnon-convex polyhedral is gived in the paeper. It uses the reformativeapproach of the Enhanced Marching Cubes to unite the boundary ofpolyhedral Minkowski sum of the sub polyhedral.Finally, the paper validates the above algorithm and gives the results.The paper also does some comparison and analysis with the existingalgorithm.