计算几何（第3版）

第0章预备知识
0.1算法与数据结构
0.1.1算法
0.1.2数据结构
0.2相关的几何知识
0.2.1基本定义
0.2.2线性变换群下的不变量
0.2.3几何对偶性
0.3计算模型
第1章几何查找(检索)
1.1点定位问题
1.1.1点q是否在多边形P内
1.1.2确定点q在平面剖分中的位置
1.1.3Z1-3算法(判定点q在哪个三角形的算法)
1.2范围查找问题
1.2.1多维二叉树(k-D树)的方法
1.2.2直接存取方法
1.2.3范围树方法
1.3判定点集是否在多边形内
1.4平面网络的处理与点q的定位
1.5平面上链的处理与点q的定位
1.6平面上线段的处理与点q的定位
第2章多边形
2.1凸多边形
2.2简单多边形
2.3多边形的三角剖分
2.4多边形的凸划分
第3章凸壳及其应用
3.1凸壳的基本概念
3.2计算平面点集凸壳的算法
3.2.1卷包裹法
3.2.2格雷厄姆方法
3.2.3分治算法
3.2.4Z3-1算法与Z3-2算法（求平面点集的凸壳）
3.2.5实时凸壳算法
3.2.6增量算法
3.2.7近似凸壳算法
3.3计算平面多边形顶点凸壳的算法
3.4计算平面多边形链顶点凸壳的算法
3.4.1概念、算法思想与描述
3.4.2解释与时间复杂性
3.5计算平面线段集凸壳的算法
3.6计算三维空间点集凸壳的算法
3.6.1基本概念
3.6.2卷包裹法
3.6.3分治算法
3.6.4Z3-8算法（三维凸壳）
3.6.5增量算法
3.7时间复杂性低于下界O（nlogn）的凸壳算法
3.8凸壳的应用
3.8.1确定任意多边形的凸、凹顶点
3.8.2利用凸壳求解货郎担问题
3.8.3凸多边形直径
3.8.4连接两个多边形成一条回路
第4章Voronoi图、三角剖分及其应用
4.1Voronoi图的基本概念
4.2构造Voronoi图的算法
4.2.1半平面的交
4.2.2增量构造方法
4.2.3分治法
4.2.4减量算法
4.2.5平面扫描算法
4.2.6构造最远点意义下Voronoi图的算法
4.3平面点集的三角剖分
4.3.1平面点集三角剖分的贪心算法
4.3.2Delaunay三角剖分与多边形内部点集的三角剖分
4.3.3平面点集三角剖分的算法
4.4平面线段集的三角剖分
4.5平面点线集的三角剖分
4.6平面点集的伪三角剖分
4.7三角剖分的表示
4.8应用
4.8.1最近邻近
4.8.2最大化最小角的三角剖分
4.8.3最大空圆
4.8.4最小生成树
4.8.5货郎担问题
4.8.6中轴
4.8.7Voronoi图与凸壳的关系
4.8.8Voronoi图的推广
4.8.9有约束的Voronoi图
4.8.10线段集的Voronoi图
4.8.11关联于多边形的Voronoi图
4.8.12几何数据压缩
4.8.13车辆定位导航系统的新定位算法
4.8.14调色
4.8.15点集增（删）点之后的三角剖分
第5章交与并及其应用
5.1线段交的算法
5.2多边形的交
5.2.1凸多边形交的算法
5.2.2星形多边形交的算法
5.2.3任意简单多边形交的算法
5.3半平面的交及其应用
5.3.1半平面的交
5.3.2两个变量的线性规划
5.4多边形的并
5.5凸多面体的交
5.6应用
5.6.1地图匹配
5.6.2地图数据的处理
5.6.3线段与凸多面体面的交
第6章多边形的获取及相关问题
6.1连接不相交线段成简单多边形(链)
6.2红外图像边缘提取
6.3提取可见光图像的边缘
6.4图像边界点行排列转换为顺序排列
6.5数字图像中目标边界的多边形表示
6.6包含密集点、线集多边形的获取
6.7满足特定条件的多边形划分
6.8多边形与多边形链
6.9圆弧、直线段组成的多边形顶点凸、凹性的确定
6.10多边形放大、缩小及移动
6.11带状多边形的处理
6.12下料问题(1)
6.13下料问题（2）
6.14下料问题（3）
6.15线锯问题
6.16多边形（链）的匹配
第7章几何体的划分与等分
7.1平面上不同类型点集的划分
7.2多边形内不同类型点集的等分
7.3平面上不同类型线段集的划分
7.4平面上不同类型线段集的等分
7.5平面上不同类型点线集的划分与等分
7.6链、多边形的划分与等分
第8章算法的运动规划
第9章几何拓扑网络设计
第10章随机几何算法与并行几何算法
待解决的问题
算法一览
参考文献
名词索引