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