计算几何 算法设计与分析PDF电子书下载

第0章 预备知识 1

0.1算法与数据结构 2

0.1.1算法 2

0.1.2数据结构 5

0.2相关的几何知识 9

0.2.1基本定义 9

0.2.2线性变换群下的不变量 11

0.2.3几何对偶性 12

0.3计算模型 13

第1章 几何查找（检索） 17

1.1点定位问题 18

1.1.1点q是否在多边形P内 19

1.1.2确定点q在平面剖分中的位置 23

1.1.3 Z1-3算法（判定点q在哪个三角形的算法） 27

1.2判定点集是否在多边形内 28

1.3平面网络的处理与点q的定位 30

1.4平面上链的处理与点q的定位 33

1.5平面上线段的处理与点q的定位 35

1.6判定点是否在多边形内部的新算法 38

第2章 多边形 41

2.1凸多边形 41

2.2简单多边形 47

2.3多边形的三角剖分 52

2.4多边形的凸划分 56

2.5对多边形链的监视 63

2.6线段划分多边形 67

2.7凸多边形的内接最大三角形及外切最小三角形 72

第3章 凸壳及其应用 78

3.1凸壳的基本概念 78

3.2计算平面点集凸壳的算法 82

3.3计算平面多边形顶点凸壳的算法 85

3.4计算平面多边形链顶点凸壳的算法 88

3.4.1概念、算法思想与描述 89

3.4.2解释与时间复杂性 91

3.5计算平面线段集凸壳的算法 92

3.6计算三维空间点集凸壳的算法 100

3.6.1基本概念 100

3.6.2 Z3-8算法（三维凸壳） 101

3.7时间复杂性低于下界O（nlogn）的凸壳算法 103

3.8凸壳的应用 106

3.8.1确定任意多边形的凸、凹顶点 106

3.8.2利用凸壳求解货郎担问题 108

3.8.3凸多边形直径 111

3.8.4连接两个多边形成一条回路 113

第4章Voronoi图、三角剖分及其应用 117

4.1 Voronoi图的基本概念 118

4.2构造Voronoi图的算法 122

4.2.1 Z′4-1算法（计算平面点集的Voronoi图） 122

4.2.2构造最远点意义下Voronoi图的算法 126

4.3平面点集的三角剖分 128

4.3.1 Delaunay三角剖分与多边形内部点集的三角剖分 129

4.3.2平面点集三角剖分的算法 131

4.4平面线段集的三角剖分 137

4.5平面点线集的三角剖分 141

4.6平面点集的伪三角剖分 146

4.7伪三角形的产生 154

4.8三角剖分的表示 159

4.9推广及应用 166

4.9.1最近邻近 166

4.9.2最大化最小角的三角剖分 167

4.9.3最大空圆 168

4.9.4最小生成树 171

4.9.5货郎担问题 172

4.9.6中轴 173

4.9.7 Voronoi图与凸壳的关系 181

4.9.8 Voronoi图的推广 183

4.9.9有约束的Voronoi图 191

4.9.10线段集的Voronoi图 193

4.9.11关联于多边形的Voronoi图 199

4.9.12点线集的Voronoi图 206

4.9.13点、水平、垂直正交线段集的Voronoi图 209

4.9.14几何数据压缩 215

4.9.15车辆定位导航系统的新定位算法 219

4.9.16调色 221

4.9.17点集增（删）点之后的三角剖分 223

第5章 交与并及其应用 225

5.1线段交的算法 225

5.2多边形的交 234

5.2.1凸多边形交的算法 234

5.2.2星形多边形交的算法 237

5.2.3任意简单多边形交的算法 238

5.3半平面的交及其应用 241

5.3.1半平面的交 241

5.3.2两个变量的线性规划 242

5.4多边形的并 248

5.5凸多面体的交 253

5.6应用 257

5.6.1地图匹配 257

5.6.2地图数据的处理 262

5.6.3线段与凸多面体面的交 262

5.6.4与线段集中线段均相交的直线及其存在区域 263

5.6.5特定射线询问 267

第6章 多边形的获取及相关问题 270

6.1连接不相交线段成简单多边形（链） 270

6.2红外图像边缘提取 275

6.3提取可见光图像的边缘 281

6.4图像边界点行排列转换为顺序排列 287

6.5数字图像中目标边界的多边形表示 291

6.6包含密集点、线集多边形的获取 295

6.7满足特定条件的多边形划分 302

6.8多边形与多边形链 305

6.9圆弧、直线段组成的多边形顶点凸、凹性的确定 308

6.10多边形放大、缩小及移动 310

6.11带状多边形的处理 312

6.12下料问题（1） 313

6.13下料问题（2） 321

6.14下料问题（3） 330

6.15线锯问题 339

6.16多边形（链）的匹配（1） 346

6.17多边形（链）的匹配（2） 348

6.18构造凸多边形 353

6.19具有属性点集的控制区域 356

6.20多边形内区域的划分及多边形（点集）中心点的确定 361

6.21满足一定条件的多边形划分 367

6.22特定条件下凸多边形的缩小与放大 372

第7章 几何体的划分与等分 377

7.1平面上不同类型点集的划分 377

7.2多边形内不同类型点集的等分 387

7.3平面上不同类型线段集的划分 393

7.4平面上不同类型线段集的等分 400

7.5平面上不同类型点线集的划分与等分 402

7.6链、多边形的划分与等分 404

第8章 路径与回路 413

8.1最短路径 414

8.1.1可视图及其构造 414

8.1.2 Z8-1算法（寻求网络中任意两点间最短路径的算法） 415

8.1.3多面体面上任意两点之间的最短路径 419

8.1.4货运汽车调度及行驶路径问题 426

8.2最短路径问题的变型 428

8.3满足一定条件的运动规划 434

8.4多边形内点之间的可视图 435

8.5多边形内任意两点之间的最短路径 443

8.6自主车自动定位及确定行车方向 449

8.7迷宫问题 453

8.8棋盘上的路径与回路 459

8.9选择道路及判定道路的通过能力 462

8.10多边形内中心区域的确定 468

第9章 几何拓扑网络设计 479

9.1 G（S）问题 480

9.1.1最大间隙问题（MAX G） 481

9.1.2点集中最大空凸多边形问题及最大空矩形问题 483

9.1.3线段集中最大空凸多边形问题 487

9.1.4点线集中最大空凸多边形问题 490

9.1.5最小覆盖问题（MIN C） 493

9.1.6包含平面点集的最小正方形 499

9.1.7子点集包含问题 503

9.1.8 2-中心问题 508

9.1.9 k-中心问题 513

9.1.10最近对问题（CPP） 521

9.1.11所有最近邻近问题（ANNP） 522

9.1.12邮局问题（POFP） 522

9.1.13寻找具有属性点集的最近点对或点团 524

9.2 G（E）问题 527

9.2.1 EMST问题 528

9.2.2线段集、点线集的最小生成树 532

9.2.3直线最小生成树及其相关问题 534

9.2.4欧几里得TSP 540

9.2.5欧几里得最大生成树问题（EMXT） 542

9.2.6最小生成网络 544

9.3 G（S，E）问题 550

9.3.1欧几里得Steiner最小树问题（ESMT） 551

9.3.2直线Steiner最小树问题（RSMT） 552

9.3.3求解ESMT问题的算法 553

9.4 G （Ω）问题 559

9.4.1有障碍物的最大空隙问题（MAX G（Ω） ） 560

9.4.2多边形集中最大空隙问题 561

9.4.3具有障碍物的欧几里得最短路径问题（ESPO） 564

9.4.4求解E3中ESPO问题的算法 566

9.4.5具有障碍物的 Steiner最小树问题（ESMTO） 578

待解决的问题 581

算法一览 583

参考文献 590

名词索引 602