《计算几何：算法设计与分析（第4版）》系统地介绍了计算几何中的基本概念、求解诸多问题的算法及复杂性分析，概括了求解几何问题所特有的许多思想方法、几何结构与数据结构。全书共分10章，包括：预备知识，几何查找（检索），多边形，凸壳及其应用，Voronoi图、三角剖分及其应用，交与并及其应用，多边形的获取及相关问题，几何体的划分与等分，路径与回路，几何拓扑网络设计等。
《计算几何：算法设计与分析（第4版）》可作为高等院校计算机、自动化等专业研究生或本科高年级学生的教材或教学参考书，也可供软件开发人员、相关专业科技工作者参考。
目录
- 第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点□是否在多边形P内
- 1.1.2确定点□在平面剖分中的位置
- 1.1.3Z□算法(判定点q在哪个三角形的算法)
- 1.2判定点集是否在多边形内
- 1.3平面网络的处理与点q的定位
- 1.4平面上链的处理与点q的定位
- 1.5平面上线段的处理与点q的定位
- 1.6判定点是否在多边形内部的新算法
- 第2章多边形
- 2.1凸多边形
- 2.2简单多边形
- 2.3多边形的三角剖分
- 2.4多边形的凸划分
- 2.5对多边形链的监视
- 2.6线段划分多边形
- 2.7凸多边形的内接三角形及外切最小三角形
- 第3章凸壳及其应用
- 3.1凸壳的基本概念
- 3.2计算平面点集凸壳的算法
- 3.3计算平面多边形顶点凸壳的算法
- 3.4计算平面多边形链顶点凸壳的算法
- 3.4.1概念、算法思想与描述
- 3.4.2解释与时间复杂性
- 3.5计算平面线段集凸壳的算法
- 3.6计算三维空间点集凸壳的算法
- 3.6.1基本概念
- 3.6.2Z粥算法(三维凸壳)
- 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.1z□算法(计算平面点集的Voronoi图)
- 4.2.2构造最远点意义下Voronoi图的算法
- 4.3平面点集的三角剖分
- 4.3.1Delaunay三角剖分与多边形内部点集的三角剖分
- 4.3.2平面点集三角剖分的算法
- 4.4平面线段集的三角剖分
- 4.5平面点线集的三角剖分
- 4.6平面点集的伪三角剖分
- 4.7伪三角形的产生
- 4.8三角剖分的表示
- 4.9推广及应用
- 4.9.1最近邻近
- 4.9.2化最小角的三角剖分
- 4.9.3空圆
- 4.9.4最小生成树
- 4.9.5货郎担问题
- 4.9.6中轴
- 4.9.7Voronoi图与凸壳的关系
- 4.9.8Voronoi图的推广
- 4.9.9有约束的Voronoi图
- 4.9.10线段集的Voronoi图
- 4.9.11关联于多边形的Voronoi图
- 4.9.12点线集的Voronoi图
- 4.9.13点、水平、垂直正交线段集的Voronoi图
- 4.9.14几何数据压缩
- 4.9.15车辆定位导航系统的新定位算法
- 4.9.16调色
- 4.9.17点集增(删)点之后的三角剖分
- 第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线段与凸多面体面的交
- 5.6.4与线段集中线段均相交的直线及其存在区域
- 5.6.5特定射线询问
- 第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多边形(链)的匹配(1)
- 6.17多边形(链)的匹配(2)
- 6.18构造凸多边形
- 6.19具有属性点集的控制区域
- 6.20多边形内区域的划分及多边形(点集)中心点的确定
- 6.21满足一定条件的多边形划分
- 6.22特定条件下凸多边形的缩小与放大
- 第7章几何体的划分与等分
- 7.1平面上不同类型点集的划分
- 7.2多边形内不同类型点集的等分
- 7.3平面上不同类型线段集的划分
- 7.4平面上不同类型线段集的等分
- 7.5平面上不同类型点线集的划分与等分
- 7.6链、多边形的划分与等分
- 第8章路径与回路
- 8.1最短路径
- 8.1.1可视图及其构造
- 8.1.2Z□算法(寻求网络中任意两点间最短路径的算法
- 8.1.3多面体面上任意两点之间的最短路径
- 8.1.4货运汽车调度及行驶路径问题
- 8.2最短路径问题的变型
- 8.3满足一定条件的运动规划
- 8.4多边形内点之间的可视图
- 8.5多边形内任意两点之间的最短路径
- 8.6自主车自动定位及确定行车方向
- 8.7迷宫问题
- 8.8棋盘上的路径与回路
- 8.9选择道路及判定道路的通过能力
- 8.10多边形内中心区域的确定
- 第9章几何拓扑网络设计
- 9.1G(S)问题
- 9.1.1间隙问题(MAXG)
- 9.1.2点集中空凸多边形问题及空矩形问题
- 9.1.3线段集中空凸多边形问题
- 9.1.4点线集中空凸多边形问题
- 9.1.5最小覆盖问题(MINC)
- 9.1.6包含平面点集的最小正方形
- 9.1.7子点集包含问题
- 9.1.82-中心问题
- 9.1.9k-中心问题
- 9.1.10最近对问题(CPP)
- 9.1.11所有最近邻近问题(ANNP)
- 9.1.12邮局问题(POFP)
- 9.1.13寻找具有属性点集的最近点对或点团
- 9.2G(E)问题
- 9.2.1EMST问题
- 9.2.2线段集、点线集的最小生成树
- 9.2.3直线最小生成树及其相关问题
- 9.2.4欧几里得TSP
- 9.2.5欧几里得生成树问题(EMXT)
- 9.2.6最小生成网络
- 9.3G(S，E)问题
- 9.3.1欧几里得Steiner最小树问题(ESMT)
- 9.3.2直线Steiner最小树问题(RSMT)
- 9.3.3求解ESMT问题的算法
- 9.4G(□)问题
- 9.4.1有障碍物的空隙问题(MAXG(□)
- 9.4.2多边形集中空隙问题
- 9.4.3具有障碍物的欧几里得最短路径问题(ESPO)
- 9.4.4求解E3中ESPO问题的算法
- 9.4.5具有障碍物的Steiner最小树问题(ESMTO)
- 待解决的问题
- 算法一览
- 参考文献
- 名词索引
