| 第一章 绪论 | 第1-13页 |
| §1-1 凸包问题的提出 | 第9页 |
| 1-1-1 凸包问题广泛的应用背景 | 第9页 |
| 1-1-2 凸包的研究现状简介 | 第9页 |
| §1-2 凸包的概念和凸包问题 | 第9-12页 |
| 1-2-1 和凸包概念相关的几个定义 | 第9-11页 |
| 1-2-2 关于凸包构造的问题的陈述 | 第11-12页 |
| §1-3 研究内容 | 第12-13页 |
| 1-3-1 目前凸包算法研究存在的问题 | 第12页 |
| 1-3-2 本论文研究的主要内容 | 第12-13页 |
| 第二章 关于凸包构造的下界和凸包特性的理论 | 第13-21页 |
| §2-1 凸包基本问题之间的联系 | 第13页 |
| 2-1-1 凸包的基本问题的回顾 | 第13页 |
| 2-1-2 凸包两个问题之间难度关系 | 第13页 |
| §2-2 凸包的基本问题1和分类问题的联系 | 第13-14页 |
| 2-2-1 对于凸包的基本问题1到分类问题之间的变换 | 第13-14页 |
| §2-3 凸包的基本问题2的复杂度的下限 | 第14-16页 |
| 2-3-1 问题2复杂度的原始运算类型 | 第14-15页 |
| 2-3-2 问题2复杂度的下界的实现方法 | 第15-16页 |
| 2-3-3 问题2的复杂度的下界 | 第16页 |
| §2-4 关于凸包特性的一些理论 | 第16-19页 |
| 2-4-1 凸多胞形是一个有限的点集 | 第16-17页 |
| 2-4-2 关于凸包顶点特征的几个定理 | 第17页 |
| 2-4-3 凸包内点的寻找方法的讨论 | 第17-19页 |
| §2-5 利用凸包特性实现平面点集凸包的一个算法 | 第19-21页 |
| 2-5-1 利用形心实现凸包算法 | 第19-21页 |
| 第三章 凸包经典算法及其优缺点的分析 | 第21-32页 |
| §3-1 卷包裹法 | 第21-23页 |
| 3-1-1 卷包裹算法的算法综述 | 第21页 |
| 3-1-2 卷包裹算法的算法描述 | 第21-23页 |
| 3-1-3 卷包裹算法的算法分析 | 第23页 |
| 3-1-4 卷包裹算法的优缺点的分析 | 第23页 |
| §3-2 Z_（3-1）算法和Z_（3-2）算法 | 第23-27页 |
| 3-2-1 Z_（3-1）算法和Z_（3-2）算法的算法思想 | 第24页 |
| 3-2-2 Z_（3-1）算法的算法步骤 | 第24-25页 |
| 3-2-3 Z_（3-1）算法的算法分析 | 第25-26页 |
| 3-2-4 Z_（3-1）算法的算法复杂度分析 | 第26页 |
| 3-2-5 Z_（3-2）算法的算法步骤 | 第26-27页 |
| 3-2-6 Z_（3-2）算法的算法复杂度分析 | 第27页 |
| §3-3 金文华、唐荣锡的简单快速的平面散乱点集凸包算法 | 第27-32页 |
| 3-3-1 概念定义 | 第27页 |
| 3-3-2 矢量叉积法判断顶点凹凸性 | 第27-29页 |
| 3-3-3 算法步骤 | 第29-30页 |
| 3-3-4 算法效率分析 | 第30-32页 |
| 第四章 凸包加速算法 | 第32-43页 |
| §4-1 综述 | 第32-33页 |
| 4-1-1 凸包加速算法引入的原因 | 第32页 |
| 4-1-2 凸包加速算法的算法思想 | 第32-33页 |
| §4-2 凸包加速算法 | 第33-38页 |
| 4-2-1 凸包加速算法的算法步骤 | 第33-34页 |
| 4-2-2 关于点与直线的位置的判断 | 第34页 |
| 4-2-3 凸包加速算法的算法正确性证明 | 第34页 |
| 4-2-4 凸包加速算法的流程图 | 第34-36页 |
| 4-2-5 凸包加速算法的算法复杂度的分析 | 第36-37页 |
| 4-2-6 凸包加速算法的加速效果分析 | 第37-38页 |
| §4-3 对于加速算法中小区间宽度的讨论 | 第38-41页 |
| 4-3-1 小区间宽度的最佳值 | 第38-39页 |
| 4-3-2 加速算法中连续区间之间剩余三角面积的分析 | 第39页 |
| 4-3-3 不同分布下的小区间个数的推导 | 第39-41页 |
| §4-4 对于计算机图形计算凸包的一个推论 | 第41-43页 |
| 4-4-1 相关概念 | 第41页 |
| 4-4-2 基本方法 | 第41页 |
| 4-4-3 算法步骤 | 第41-42页 |
| 4-4-4 算法分析 | 第42-43页 |
| 第五章 凸包加速算法步骤8的算法选择和GRAHAM算法的改进 | 第43-50页 |
| §5-1 GRAHAM算法概述 | 第43-47页 |
| 5-1-1 Graham扫描算法的算法思想 | 第43页 |
| 5-1-2 Graham扫描算法的算法步骤 | 第43-46页 |
| 5-1-3 Graham算法的效率 | 第46页 |
| 5-1-4 Graham算法的优缺点 | 第46-47页 |
| §5-2 关于GRAHAM算法的改进 | 第47-48页 |
| 5-2-1 Grham算法中避免极角运算 | 第47页 |
| 5-2-2 改变Graham算法扫描过程中对简单多边形的处理方式 | 第47-48页 |
| §5-3 凸包加速算法中步骤8使用算法的选择和GRAHAM算法的改进 | 第48-50页 |
| 5-3-1 对步骤8使用算法的选择 | 第48页 |
| 5-3-2 基于凸包的加速算法使用的改进的Graham扫描算法 | 第48页 |
| 5-3-3 使用改进后的Graham算法的效率分析 | 第48-50页 |
| 第六章 凸包加速和改进算法的实现和结果分析 | 第50-55页 |
| §6-1 凸包加速算法的实现的介绍 | 第50-51页 |
| 6-1-1 输入数据的产生 | 第50-51页 |
| 6-1-2 经典算法的选择 | 第51页 |
| 6-1-3 凸包加速算法的实现 | 第51页 |
| 6-1-4 Graham算法改进的实现 | 第51页 |
| §6-2 凸包加速算法的运行结果及其分析 | 第51-55页 |
| 6-2-1 对于均匀分布的点集的加速效果 | 第51-52页 |
| 6-2-2 对于正态分布加速的效果 | 第52页 |
| 6-2-3 凸包加速算法和其他算法运行效率的比较 | 第52-53页 |
| 6-2-4 对结果的综合分析 | 第53-55页 |
| 第七章 结论 | 第55-56页 |
| 参考文献 | 第56-59页 |
| 附录A | 第59-61页 |
| 附录B | 第61-65页 |
| 致谢 | 第65-66页 |
| 攻读学位期间所取得的相关科研成果 | 第66页 |
