第1章 引论 1
1.1计算几何 1
1.1.1概述 1
1.1.2几何学的历史及发展 3
1.1.3计算几何的研究对象 4
1.2计算机算法 6
1.2.1计算机算法、程序与程序设计 6
1.2.2计算机算法的性能标准 8
1.2.3计算机算法分析与算法比较 9
1.2.4计算机算法的时间复杂度分析 15
1.2.5计算机算法描述工具与算法抽象程度 24
1.3凸壳问题与凸壳算法 36
1.3.1二维点集凸壳问题与凸壳算法描述 37
1.3.2二维点集凸壳研究的意义与现状分析 38
第2章 现行二维点集凸壳算法概述 43
2.1国外现行二维点集凸壳算法简述 43
2.1.1卷包裹凸壳算法 44
2.1.2格雷汉姆凸壳算法 45
2.1.3折半分治凸壳算法 46
2.2国内现行二维点集凸壳算法简述 49
2.2.1增点递推凸壳算法及其改进 49
2.2.2顶点凹凸化凸壳改进算法 55
2.2.3初始顶点八向化凸壳算法 59
2.2.4初始顶点四角化凸壳算法 64
第3章 二维凸壳串行算法的同构化改进 69
3.1同构化二维凸壳构造基本定理与改进方向 69
3.2动态基线倾角最大化圈绕凸壳新算法 72
3.2.1动态基线倾角最大化圈绕凸壳算法描述 72
3.2.2本算法技术关键与核心基础的数学证明 75
3.3单域单向水平倾角最小化圈绕凸壳新算法 76
3.3.1单域单向水平倾角最小化圈绕凸壳算法的描述 77
3.3.2本算法技术关键与核心基础的数学证明 79
3.4单域双向水平倾角最值化圈绕凸壳新算法 80
3.4.1单域双向水平倾角最值化圈绕凸壳算法描述 80
3.4.2本算法技术关键与核心基础的数学证明 84
3.5双域单向水平倾角最小化圈绕凸壳新算法 86
3.5.1双域单向水平倾角最小化圈绕凸壳算法描述 86
3.5.2本算法技术关键与核心基础的数学证明 91
3.6双域多向水平倾角最值化圈绕凸壳新算法 93
3.6.1双域四向水平倾角最小化圈绕凸壳算法描述 94
3.6.2本算法技术关键与核心基础的数学证明 100
3.7L域M向水平倾角最小化圈绕串行凸壳新算法群 104
3.8L域M向基线倾角最大化圈绕串行凸壳新算法群 105
第4章 二维凸壳并行算法的同构化改进 107
4.1并行计算概述 107
4.1.1并行算法概要 107
4.1.2工作站机群COW概要 109
4.2双群双域四向水平倾角最小化圈绕并行凸壳新算法 111
4.3四群四域四向基线倾角最大化圈绕并行凸壳新算法 117
4.4四群四域四向基线倾角与距离最大化圈绕并行凸壳新算法 123
第5章 二维凸壳算法的时间复杂度研究 129
5.1凸壳算法时间复杂度的归约化分析 129
5.2同构化凸壳算法时间复杂度基本定理 132
5.2.1壳算法时间复杂度的研究现状质疑 133
5.2.2壳算法时间复杂度的深化改进研究 134
5.3凸壳新算法时间复杂度的案例分析 139
第6章 二维凸壳应用示例 143
6.1基于凸壳的指纹轮廓线快速计算 143
6.2基于凸壳像素比特征的粘连汉字切分 145
6.2.1基于背景细化的切分方法 146
6.2.2凸壳像素比特征与使用 147
6.3基于凸壳“文纹”的数字签名创新技术研究 149
6.3.1数字签名定义及实现过程 150
6.3.2基于“文纹”的数字签名新技术 151
6.4基于凸壳的城市用地空间扩展类型识别 154
6.4.1基于凸壳的城市用地空间扩展类型 154
6.4.2城市外围轮廓形态紧凑性的测度与作用 157
第7章 二维凸壳算法的编程实现示例 158
7.1格雷汉姆凸壳算法的编程实现 158
7.2折半分治法凸壳算法的编程实现 163
7.3单域单向水平倾角最小化圈绕凸壳新算法的编程实现 177
7.4单域双向水平倾角最小化圈绕凸壳新算法的编程实现 183
7.5动态基线倾角最大化圈绕凸壳新算法的编程实现 195
参考文献 217