三维空间内凹多面体的Minkowski和的算法研究工学硕士论文.doc

工学硕士学位论文 三维空间内凹多面体的Minkowski和 的算法研究 摘 要 计算几何是计算机理论科学的一个重要分支，该学科已经有了巨大的发展，产生了一系列的理论成果。Minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义，其研究成果已在机器人学、动态仿真、计算机图形学等许多领域中得到了广泛的应用，尤其在机器人学领域，它是计算无碰撞路径的一个重要工具。因此，如何快速而准确地计算避障路径，一直是国内外学者研究的重要课题。 首先，在对国内外研究现状进行综合分析的基础上，进一步研究了计算两个凸多面体Minkowski和的求和算法。本文脱离以往算法中基于传统的高斯映射的算法，以减少计算平面划分叠置的次数、提高算法的执行效率为目标，提出了正四面体映射和点投影的概念，通过计算凸多面体的正四面体映射和点投影，把三维空间的问题转换到二维平面进行解决。 其次，凸剖分是计算凹多面体的Minkowski和的一个重要步骤。为了有效地计算凹多面体的Minkowski和，在研究了国内外许多凸剖分算法后，本文采用集合论和图论的思想，提出了基于成功回路的凹多面体的剖分算法，同时对剖分算法的时间复杂度进行了分析。 再次，给出了计算凹多面体的Minkowski和算法的总体思想。采用成功回路的算法对凹多面体进行剖分，得到若干子凸多面体；利用正四面体映射和点投影的算法计算所有可能成对的子凸多面体的Minkowski和；通过已改进的Enhanced Marching Cubes算法合并子凸多面体的Minkowski和多面体的边界。 最后，通过实验验证了上述的研究内容，给出了实验结果，并将结果与现有的算法进行了对比分析。 关键词 计算几何；正四面体映射；点投影；凹多面体；成功回路；Enhanced Marching Cubes；Minkowski和 Abstract Computational Geometry is an important embranchment of computer theoretical science. The subject has already made a tremendous development and produced a series of theoretical results. Minkowski sum algorithm has the great significance in theory and application as an embranchment of Computational Geometry. It plays an important role in robotics, dynamic simulation, computer graphics, and so on, especially in the field of robotics, it is an important tool for computing collision-free path. Therefore, how to calculate the path of obstacle avoidance quickly and accurately has been an important research subject of the home and foreign scholars. Firstly, this paper researches the existed approach of Minkowski sum of two convex polyhedral. In order to reduce the amount of computing overlay of two planar subdivisions and improve the efficiency of the algorithm, this paper separates from the previous algorithm based on the traditional Gaussian Map and proposes the method of Regular Tetrahedron Map and Point Projection to resolve this problem. Through this method, it can reduce the problem in 3D to 2D. Secondly, convex decomposition is an important step of computing Minkowski sum of two non-conv