计算三维空间凸多面体的精确Minkowski和的算法研究

摘要

计算几何是理论计算机科学领域中一个新的极有生命力的子领域，而Minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义，其研究成果已在机器人学、计算机图形学、CAD等许多领域中发挥了重要的作用。如何为各种应用提供有效的基础算法以及理论依据，一直是国内外学者研究的方向。 本文针对叠置算法是计算两个凸多面体Minkowski的重要步骤的情况，为克服现有叠置算法的缺陷，从一个全新的角度对平面划分的叠置算法进行了研究，提出了三角形内简单平面凸划分的叠置算法。整个算法分为计算交点、拓扑重组和创建双向链接边表记录三步，文章同时对算法的正确性和复杂度进行了分析。 文中以减少计算平面划分叠置的次数，提高算法的执行效率为目标，提出了正四面体中心投影的概念。通过计算凸多面体的正四面体中心投影，按照给定坐标系下的坐标转换关系，把三维空间的问题转换到二维空间进行解决。提出了基于正四面体中心投影的凸多面体的精确Minkowski和求和算法。采用三角形内简单平面凸划分的叠置算法求四对平面划分的叠置，并根据求和的需要及特征完成了属性分配过程，由此得到Minkowski和多面体的正四面体中心投影，求它的逆映射得到Minkowski和多面体。文章同时对算法的时间复杂度进行了分析。最后，对上述的研究内容进行了实验验证并给出实验结果。

目录

文摘

英文文摘

声明

第1章绪论

1.1研究意义

1.2国内外研究现状

1.3 Minkowski和算法的应用

1.4本文研究内容

1.5本文组织结构

第2章理论基础

2.1相关的几何定义

2.1.1欧几里得空间

2.1.2点

2.1.3直线与线段

2.1.4多边形

2.1.5平面图及平面划分

2.1.6平面直线图

2.1.7多面体

2.1.8凸集与凸包

2.1.9测地线

2.2基础知识及内容

2.2.1 Minkowski和的定义

2.2.2 Minkowski和的性质

2.2.3平面点定位

2.2.4平面划分的叠置

2.2.5高斯映射

2.3算法与数据结构

2.3.1算法的预备知识

2.3.2数据结构

2.4本章小结

第3章三角形内简单平面凸划分的叠置算法

3.1引言

3.2叠置算法的研究状况

3.3辅助定义

3.4数据结构及辅助信息

3.5三角形内简单平面凸划分的叠置算法

3.5.1计算交点

3.5.2拓扑重组

3.5.3创建DCEL记录

3.6算法正确性分析

3.6.1求交算法的正确性

3.6.2拓扑重组算法的正确性

3.6.3创建DCEL记录算法的正确性

3.7算法复杂度分析

3.7.1算法的时间复杂度

3.7.2算法的空间复杂度

3.8本章小结

第4章计算凸多面体的精确Minkowski和

4.1引言

4.2现有的Minkowski和求和算法

4.3相关定义

4.4正四面体中心投影

4.4.1正四面体中心投影的定义

4.4.2空间坐标转换关系

4.5基于正四面体中心投影的Minkowski和求和算法

4.5.1数据结构及相关信息

4.5.2算法思想

4.5.3算法描述

4.5.4算法分析

4.6本章小结

第5章实验与分析

5.1实验环境设置

5.2 LEDA简介

5.3精确实数计算

5.4叠置算法的实验验证

5.4.1实验数据设置

5.4.2实验流程及结果分析

5.5 Minkowski和求和算法的实验验证

5.5.1实验数据设置

5.5.2实验流程

5.5.3实验结果分析

5.6本章小结

结论

参考文献

攻读硕士学位期间承担的科研任务与主要成果

致谢

作者简介