（毕业设计论文）【硕士论文】三维空间内凹多面体的Minkowski和的算法研究.doc

工学硕士学位论文 三维空间内凹多面体的Minkowski和 的算法研究 燕 山 大 学 2009年11月 国内图书分类号：TP301.6 国际图书分类号：654 工学硕士学位论文 三维空间内凹多面体的Minkowski和 的算法研究 硕士研究生： 导师： 申请学位级别： 工学硕士 学 科、专 业： 计算机应用技术 所 在 单 位： 信息科学与工程学院 授予学位单位： 燕山大学 Classified Index: TP301.6 U.D.C.: 654 Dissertation for the Master Degree in Engineering RESEARCH ON COMPUTING MINKOWSKI SUM OF NON-CONVEX POLYHEDRAL IN THRESS DEMENSION Candidate: Supervisor: Academic Degree Applied for: Master of Engineering Speciality: Computer Application Technology University: Yanshan 燕山大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文《三维空间内凹多面体的Minkowski和的算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。 作者签字 日期： 年 月 日 燕山大学硕士学位论文使用授权书 《三维空间内凹多面体的Minkowski和的算法研究》系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 必威体育官网网址□，在 年解密后适用本授权书。 本学位论文属于 不必威体育官网网址□。 （请在以上相应方框内打“√” ） 作者签名： 日期： 年 月 日 导师签名： 日期： 年 月 日 摘要 PAGE VII 摘 要 计算几何是计算机理论科学的一个重要分支，该学科已经有了巨大的发展，产生了一系列的理论成果。Minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义，其研究成果已在机器人学、动态仿真、计算机图形学等许多领域中得到了广泛的应用，尤其在机器人学领域，它是计算无碰撞路径的一个重要工具。因此，如何快速而准确地计算避障路径，一直是国内外学者研究的重要课题。 首先，在对国内外研究现状进行综合分析的基础上，进一步研究了计算两个凸多面体Minkowski和的求和算法。本文脱离以往算法中基于传统的高斯映射的算法，以减少计算平面划分叠置的次数、提高算法的执行效率为目标，提出了正四面体映射和点投影的概念，通过计算凸多面体的正四面体映射和点投影，把三维空间的问题转换到二维平面进行解决。 其次，凸剖分是计算凹多面体的Minkowski和的一个重要步骤。为了有效地计算凹多面体的Minkowski和，在研究了国内外许多凸剖分算法后，本文采用集合论和图论的思想，提出了基于成功回路的凹多面体的剖分算法，同时对剖分算法的时间复杂度进行了分析。 再次，给出了计算凹多面体的Minkowski和算法的总体思想。采用成功回路的算法对凹多面体进行剖分，得到若干子凸多面体；利用正四面体映射和点投影的算法计算所有可能成对的子凸多面体的Minkowski和；通过已改进的Enhanced Marching Cubes算法合并子凸多面体的Minkowski和多面体的边界。 最后，通过实验验证了上述的研究内容，给出了实验结果，并将结果与现有的算法进行了对比分析。 关键词 计算几何；正四面体映射；点投影；凹多面体；成功回路；Enhanced Marching Cubes；Minkowski和 燕山大学工学硕士学位论文 Abstract PAGE VI Abstract Computational Geometry is an important embranchment of computer theoretical science. The subj