| 中文摘要 | 第1-6页 |
| Abstract | 第6-11页 |
| 第一章 绪论 | 第11-15页 |
| 1-1 凸包问题的应用及研究现状 | 第11-15页 |
| 1-1-1 凸包的应用 | 第11-14页 |
| 1-1-2 凸包的综合研究现状 | 第14-15页 |
| 第二章 凸包的相关概念 | 第15-25页 |
| 2-1 凸包的概念 | 第15-19页 |
| 2-1-1 关于凸包的几个定义 | 第15-17页 |
| 2-1-2 三维凸包复杂度分析 | 第17-19页 |
| 2-2 凸包和半空间的交 | 第19-24页 |
| 2-2-1 凸包与对偶 | 第19-20页 |
| 2-2-2 凸包的转化 | 第20-21页 |
| 2-2-3 凸包与Voronoi 图 | 第21-24页 |
| 2-3 构建三维凸包的关键命题 | 第24-25页 |
| 第三章 经典的三维凸包生成算法分析 | 第25-37页 |
| 3-1 Clarkson 和Shor 算法 | 第25-31页 |
| 3-1-1 随机算法框架 | 第25-30页 |
| 3-1-2 Clarkson 和Shor 算法描述 | 第30-31页 |
| 3-1-3 Clarkson 和Shor 算法复杂度 | 第31页 |
| 3-2 快速凸包算法 | 第31-37页 |
| 3-2-1 快速凸包算法介绍 | 第31页 |
| 3-2-2 快速凸包算法框架 | 第31-33页 |
| 3-2-3 算法描述 | 第33页 |
| 3-2-4 快速凸包算法的正确性以及复杂度分析 | 第33-37页 |
| 第四章 改进的三维凸包算法 | 第37-55页 |
| 4-1 改进的三维凸包算法框架 | 第37-39页 |
| 4-1-1 详细步骤 | 第37-38页 |
| 4-1-2 可见性 | 第38页 |
| 4-1-3 地平线 | 第38-39页 |
| 4-2 算法的数据结构 | 第39-42页 |
| 4-2-1 凸包空间结构 | 第39-41页 |
| 4-2-2 凸包中点和面的拓扑关系结构 | 第41-42页 |
| 4-3 算法的描述 | 第42-48页 |
| 4-3-1 算法的伪代码实现和流程图 | 第42-46页 |
| 4-3-2 算法的操作详解 | 第46-48页 |
| 4-4 算法的正确性分析 | 第48-49页 |
| 4-5 算法的复杂度分析 | 第49-55页 |
| 第五章 基于 OpenGL 的实验平台设计及实验分析 | 第55-67页 |
| 5-1 实验平台设计 | 第55-62页 |
| 5-1-1 动态链接库和OpenGL | 第55-56页 |
| 5-1-2 总体模块设计 | 第56-58页 |
| 5-1-3 几何基本工具库GeomCalc.dll | 第58-60页 |
| 5-1-4 几何内核库GeomKernal.dll | 第60-61页 |
| 5-1-5 凸包生成工具库ConvexHull.dll | 第61-62页 |
| 5-2 实验的效果 | 第62-65页 |
| 5-3 效率分析 | 第65-67页 |
| 第六章 总结与展望 | 第67-69页 |
| 6-1 总结 | 第67页 |
| 6-2 进一步工作 | 第67-69页 |
| 致谢 | 第69-70页 |
| 参考文献 | 第70-73页 |
| 攻读学位期间发表的学术论文 | 第73页 |
