张亚毕业硕士论文

《张亚毕业硕士论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、工学硕士学位论文三维空间内凹多面体的Minkowski和的算法研究燕山大学2009年11月国内图书分类号:TP301.6国际图书分类号：654工学硕士学位论文三维空间内凹多面体的Minkowski和的算法研究硕士研究生:导师:工学硕士计算机应用技术信息科学与工程学院燕山大学申请学位级别:学科、专业:所在单位:授予学位单位:ClassifiedIndex:TP301.6U・D.C・：654DissertationfortheMasterDegreeinEngineeringRESEARCHONCOMPUTINGMINKOWSKISUMOFNON-CONV

2、EXPOLYHEDRALINTHRESSDEMENSIONCandidate:Supervisor:AcademicDegreeAppliedfor:MasterofEngineeringSpeciality:ComputerApplicationTechnologyUniversity:YanshanUniversity燕山大学硕士学位论文原创性声明本人郑重声明：此处所捉交的硕士学位论文《三维空间内凹多而体的Minkowski和的算法研究》，是本人在导师指导下，在燕山大学攻读硕士学位期间独立进行研究工作所取得的成果。据本人所知，论文中除已注明部分外不

3、包含他人已发表或撰写过的研究成果。对本文的研究工作做出重要贡献的个人和集体，均已在文屮以明确方式注明。本声明的法律结果将完全由本人承担。作者签字日期：年月曰燕山大学硕士学位论文使用授权书《三维空间内凹多面体的Minkowski和的算法研究》系本人在燕山人学攻读硕士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归燕山大学所有，木人如需发表将署名燕山大学为第一完成单位及相关人员。本人完全了解燕山大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复印件和电子版木，允许论文被查阅和借阅。木人授权燕山大学，可以采用影印、缩印或其他复制

4、手段保存论文，可以公布论文的全部或部分内容。保密口，在年解密后适用本授权书o本学位论文属于不保密口。（请在以上相应方框内打“）作者签名：口期：年月口导师签名：年月H摘要计算几何是计算机理论科学的一个重要分支，该学科己经有了巨大的发展，产生了一系列的理论成果。Minkowski和算法作为计算儿何研究领域屮的一个分支，在理论和应用上都有着重要的意义，其研究成果已在机器人学、动态仿真、计算机图形学等许多领域屮得到了广泛的应用，尤其在机器人学领域，它是计算无碰撞路径的一个重要工具。因此，如何快速而准确地计算避障路径，一直是国内外学者研究的重要课题。首先，在对国

5、内外研究现状进行综合分析的基础上，进一步研究了计算两个凸多面体Minkowski和的求和算法。本文脱离以往算法中基于传统的高斯映射的算法，以减少计算平面划分叠置的次数、提高算法的执行效率为目标，提出了止四面体映射和点投影的概念，通过计算凸多面体的止四面体映射和点投影，把三维空间的问题转换到二维平面进行解决。其次，凸剖分是计算凹多而体的Minkowski和的一个重要步骤。为了有效地计算凹多面体的Minkowski和，在研究了国内外许多凸剖分算法后,本文采用集合论和图论的思想，提出了基于成功回路的凹多面体的剖分算法，同时对剖分算法的时间复杂度进行了分析。再

6、次，给出了计算凹多面体的Minkowski和算法的总体思想。采用成功回路的算法对凹多面休进行剖分，得到若干子凸多面休；利用正四面体映射和点投影的算法计算所有可能成对的子凸多面体的Minkowski和；通过已改进的EnhancedMarchingCubes算法合并子凸多面体的Minkowski和多面体的边界。最后，通过实验验证了上述的研究内容，给出了实验结果，并将结果与现有的算法进行了对比分析。关键词计算几何；止四面体映射；点投影；凹多面体；成功回路；EnhancedMarchingCubes；Minkowski和AbstractComputationa

7、lGeometryisanimportantembranchmentofcomputertheoreticalscience.Thesubjecthasalreadymadeatremendousdevelopmentandproducedaseriesoftheoreticalresults.MinkowskisumalgorithmhasthegreatsignificanceintheoryandapplicationasanembranchmentofComputationalGeometry.Itplaysanimportantroleinr

8、obotics,dynamicsimulation,computergraphics,ands