第1章 概述 1
1.1 地理信息系统 1
1.2 数字高程模型 4
1.3 Delaunay三角网 8
1.4 主要内容及其组成部分 9
1.5 小结 11
第2章 凸包及其应用 13
2.1 凸包的基本概念 13
2.2 计算平面点集凸包的算法 17
2.3 计算三维空间点集凸壳的算法 42
2.4 凸包的应用 54
2.5 小结 58
第3章 Voronoi图、三角剖分及其应用 59
3.1 Voronoi图的基本概念 59
3.2 构造Voronoi图的算法 65
3.3 平面点集的三角剖分 76
3.4 应用 94
3.5 小结 96
第4章 基于K-order Voronoi图的RkNN查询 97
4.1 预备知识 97
4.2 K-order Voronoi性质 98
4.3 BRKVD算法 101
4.4 算法测试 105
4.5 BRKVD系统实现 112
4.6 小结 128
第5章 一种改进的逐点插入Delaunay三角网生成算法 129
5.1 基本概念 129
5.2 数据结构 131
5.3 算法及关键步骤的实现 133
5.4 算法分析 136
5.5 基于TIN的三维DEM构建 136
5.6 DEM空间数据挖掘 141
5.7 小结 154
第6章 基于剪枝策略和Graham的Delaunay三角网生成算法 156
6.1 基于剪枝策略的Delaunay三角网生成算法 156
6.2 基于Graham三角剖分的Delaunay三角网生成算法研究 164
6.3 小结 172
第7章 一种基于分治策略的快速构建Delaunay三角网算法 173
7.1 Delaunay三角网的性质 173
7.2 传统构建Delaunay三角网的算法 174
7.3 快速生成Delaunay三角网的分治算法 179
7.4 实验分析 182
7.5 小结 183
第8章 基于最大外接圆的约束Delaunay三角剖分算法 184
8.1 约束Delaunay三角网基本性质 184
8.2 传统构建约束Delaunay三角网方法 185
8.3 基于最大外接圆的约束Delaunay三角剖分算法 189
8.4 实验分析 193
8.5 小结 194
第9章 基于半边数据结构的逐点插入Delaunay三角剖分算法 195
9.1 基于半边数据结构的逐点插入Delaunay三角剖分算法 195
9.2 实体造型与CSG概述 204
9.3 建筑物的CSG建模 206
9.4 建筑物三维数据的获取 208
9.5 地形模型与建筑物模型的整合 211
9.6 实验 211
9.7 小结 214
第10章 高阶Delaunay三角网及生成算法研究 215
10.1 基本概念及相关性质 216
10.2 高阶Delaunay三角网生成算法 219
10.3 1-阶Delaunay三角网 227
10.4 实验分析 228
10.5 小结 229
第11章 用高阶Delaunay三角网生成实际地形 231
11.1 最小化局部极小数量是NP-难问题 232
11.2 两种启发式规则减少局部极小的数量 234
11.3 高阶Delaunay三角网的应用 240
11.4 实验分析 242
11.5 小结 244
