三维空间内凹多面体的Minkowski和的算法研究.doc

文档介绍：学位论文
三维空间内凹多面体的Minkowski和
的算法研究
2009年11月
工学硕士学位论文
三维空间内凹多面体的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和的一个重要步骤。为了有效地计算凹多面体的Minkowski和,在研究了国内外许多凸剖分算法后,本文采用集合论和图论的思想,提出了基于成功回路的凹多面体的剖分算法,同时对剖分算法的时间复杂度进行了分析。
再次,给出了计算凹多面体的Minkowski和算法的总体思想。采用成功回路的算法对凹多面体进行剖分,得到若干子凸多面体;利用正四面体映射和点投影的算法计算所有可能成对的子凸多面体的Minkowski和;通过已改进的Enhanced Marching Cubes算法合并子凸多面体的Minkowski和多面体的边界。
最后,通过实验验证了上述的研究内容,给出了实验结果,并将结果与现有的算法进行了对比分析。
关键词计算几何;正四面体映射;点投影;凹多面体;成功回路;Enhanced Marching Cubes;Minkowski和
Abstract
Computational 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 great significance in theory and application as an embranchment