三维空间内多面体Minkowski和求和算法的研究

摘要

计算几何是计算机理论科学的一个较新的极有生命力的子领域，而Minkowski和算法作为计算几何研究领域中的一个分支，在理论和应用上都有着重要的意义，其研究成果已在图形学、机器人技术、地理数据库等领域中得到了广泛的应用。
　　首先，本文在对国内外研究现状进行综合分析的基础上，进一步研究了计算两个凸多面体Minkowski和求和算法。为进一步提高求和算法的执行效率，本文优化了基于正四面体中心投影的计算凸多面体精确Minkowski和求和算法，提出基于正四面体高斯映射的凸多面体精确Minkowski和求和算法。同时对算法的时间复杂度进行了对比分析。
　　其次，为有效的计算凹多面体Minkowski和，在研究了许多凸剖分算法后，提出按照三维几何造型的不同，对凹多面体进行四面体分解或者面分解的分而治之的剖分策略。同时对剖分算法的时间复杂度进行了分析。
　　然后，为提高合并算法的计算效率，本文利用改进的Enhanced Marching Cubes算法，提出了优化的合并子凸多面体的Minkowski和多面体边界面的算法。同时，本文研究了计算任意简单多面体Minkowski和的求和算法步骤，为进一步提高算法的效率和精确度，本文给出了新的计算任意简单多面体Minkowski和的求和算法步骤。
　　最后，通过实验验证了计算任意简单多面体Minkowski和的算法的可行性和有效性，并将结果与传统算法进行了对比分析。

目录

封面

声明

摘要

英文摘要

目录

第1章 绪论

1.1 研究意义

1.2 国内外研究现状

1.3 Minkowski和算法的应用

1.4 本文研究内容

1.5 本文组织结构

第2章 理论基础

2.1 相关的几何定义

2.2 基础知识及内容

2.3 算法与数据结构

2.4 本章小结

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

3.1 引言

3.2 凸多面体Minkowski和算法概述

3.3 相关定义

3.4 正四面体高斯映射

3.5 基于正四面体高斯映射的Minkowski和算法

3.6 本章小结

第4章 计算凹多面体的Minkowski和

4.1 引言

4.2 凹多面体Minkowski和算法概述

4.3 多面体凸剖分算法

4.4 合并子Minkowski和多面体

4.5 Enhanced Marching Cube 算法

4.6 计算简单多面体Minkowski和算法总体思想

4.7 本章小结

第5章 实验与分析

5.1 实验环境设置

5.2 LEDA简介

5.3 精确实数计算

5.4 多面体Minkowski和求和算法的实验验证

5.5 本章小结

结论

参考文献

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

致谢

作者简介