工学硕士学位论文
三维空间内凹多面体的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 University

燕山大学硕士学位论文原创性声明
本人郑重声明：此处所提交的硕士学位论文《三维空间内凹多面体的Minkowski和的算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文中以明确方式注明。本声明的法律结果将完全由本人承担。
      作者签字                    日期：    年  月  日
燕山大学硕士学位论文使用授权书
《三维空间内凹多面体的Minkowski和的算法研究》系本人在燕山大学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，本人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版本，允许论文被查阅和借阅。本
人授权燕山大学，可以采用影印、缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。
                    保密□，在    年解密后适用本授权书。
本学位论文属于
不保密□。
（请在以上相应方框内打“√” ）
作者签名：                  日期：    年  月  日
导师签名：                  日期：    年  月  日

毕业设计（论文）原创性声明和使用授权说明
原创性声明
本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得          及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。
作 者  签 名：  　    　　日　  期：  　  
指导教师签名：  　     日  期：  　  
使用授权说明
本人完全了解      大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。
作者签名：  　    　　    日　  期：  　  

学位论文原创性声明
本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。
作者签名：                日期：  年    月    日
学位论文版权使用授权书
本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权  　    　大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。
涉密论文按学校规定处理。
作者签名：                    日期：  年    月    日
导师签名：            日期：  年    月    日
摘 要
计算几何是计算机理论科学的一个重要分支，该学科已经有了巨大的发展，产生了一系列的理论成果。Minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义，其研究成果已在机器人学、动态仿真、计算机图形学等许多领域中得到了广泛的应用，尤其在机器人学领域，它是计算无碰撞路径的一个重要工具。因此，如何快速而准确地计算避障路径，一直是国内外学者研究的重要课题。
首先，在对国内外研究现状进行综合分析的基础上，进一步研究了计算两个凸多面体Minkowski和的求和算法。本文脱离以往算法中基于传统的高斯映射的算法，以减少计算平面划分叠置的次数、提高算法的执行效率为目标，提出了正四面体映射和点投影的概念，通过计算凸多面体的正四面体映射和点投影，把三维空间的问题转换到二维平面进行解决。
其次，凸剖分是计算凹多面体的Minkowski和的一个重要步骤。为了有效地计算凹多面体的
Minkowski和，在研究了国内外许多凸剖分算法后，本文采用集合论和图论的思想，提出了基于成功回路的凹多面体的剖分算法，同时对剖分算法的时间复杂度进行了分析。
再次，给出了计算凹多面体的Minkowski和算法的总体思想。采用成功回路的算法对凹多面体进行剖分，得到若干子凸多面体；利用正四面体映射和点投影的算法计算所有可能成对的子凸多面体的Minkowski和；通过已改进的Enhanced Marching Cubes算法合并子凸多面体的Minkowski和多面体的边界。
最后，通过实验验证了上述的研究内容，给出了实验结果，并将结果与现有的算法进行了对比分析。
关键词 计算几何；正四面体映射；点投影；凹多面体；成功回路；Enhanced Marching Cubes；Minkowski和