计算几何 算法设计、分析及应用 第5版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 判定点是否在多边形内部的新算法 40

第2章 多边形 43

2.1 凸多边形 43

2.2 简单多边形 49

2.3 多边形的三角剖分 54

2.4 多边形的凸划分 58

2.5 对多边形链的监视 65

2.6 线段划分多边形 69

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

第3章 凸壳及其应用 80

3.1 凸壳的基本概念 80

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

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

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

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

3.4.2 解释与时间复杂性 93

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

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

3.6.1 基本概念 102

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

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

3.8 凸壳的应用 108

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

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

3.8.3 凸多边形直径 113

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

3.8.5 三维空间中平面群的重建 118

3.8.6 构造平面曲线 122

3.8.7 某些机型的识别及其他应用 126

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

4.1 Voronoi图的基本概念 140

4.2 构造Voronoi图的算法 144

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

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

4.3 平面点集的三角剖分 150

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

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

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

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

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

4.7 伪三角形的产生 176

4.8 三角剖分的表示 181

4.9 推广及应用 188

4.9.1 最近邻近 188

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

4.9.3 最大空圆 190

4.9.4 最小生成树 193

4.9.5 货郎担问题 194

4.9.6 中轴 195

4.9.7 Voronoi图与凸壳的关系 204

4.9.8 Voronoi图的推广 206

4.9.9 有约束的Voronoi图 214

4.9.10 线段集的Voronoi图 215

4.9.11 关联于多边形的Voronoi图 221

4.9.12 点线集的Voronoi图 228

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

4.9.14 几何数据压缩 237

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

4.9.16 调色 243

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

4.9.18 点云的处理及相关问题的求解 246

4.9.19 点云曲面边界线的提取及相关问题的求解 255

4.9.20 关联于圆的Voronoi图 263

4.9.21 曲面上点集的三角剖分 275

4.9.22 指纹识别算法 278

第5章 交与并及其应用 285

5.1 线段交的算法 285

5.2 多边形的交 294

5.2.1 凸多边形交的算法 294

5.2.2 星形多边形交的算法 297

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

5.3 半平面的交及其应用 301

5.3.1 半平面的交 301

5.3.2 两个变量的线性规划 302

5.4 多边形的并 308

5.5 凸多面体的交 313

5.6 应用 317

5.6.1 地图匹配 317

5.6.2 地图数据的处理 322

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

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

5.6.5 特定射线询问 327

5.6.6 水平、垂直边多边形逼近椭圆 331

5.6.7 紧致边界 343

5.6.8 射线与隐形凸多面体的交 352

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

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

6.2 红外图像边缘提取 361

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

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

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

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

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

6.8 多边形与多边形链 391

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

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

6.11 带状多边形的处理 398

6.12 下料问题（1） 399

6.13 下料问题（2） 407

6.14 下料问题（3） 416

6.15 线锯问题（1） 425

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

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

6.18 构造凸多边形 439

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

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

6.21 满足一定条件的多边形划分（1） 453

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

6.23 下料问题（4） 463

6.24 线锯问题（2） 469

6.25 线锯问题（3） 472

6.26 线锯问题（4） 475

6.27 满足一定条件的多边形划分（2） 478

6.28 隐形几何体（线段、多边形、长方体） 485

6.29 海洋划界 489

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

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

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

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

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

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

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

7.7 平面上点集划分的推广 529

7.8 用圆集划分平面点集 534

7.9 正方形内2k个点的划分 539

第8章 路径与回路 549

8.1 最短路径 550

8.1.1 可视图及其构造 550

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

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

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

8.2 最短路径问题的变型 564

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

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

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

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

8.7 迷宫问题（1） 589

8.8 棋盘上的路径与回路 595

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

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

8.11 迷宫问题（2） 615

8.12 网络中路径问题求解的一种搜索方法及回路问题的求解 620

8.13 多边形集合中任意两点之间最短路径（含多边形数目最少） 627

8.14 点、多边形、多面体之间的最短距离 630

8.15 球面上货郎担问题的求解及DNA双螺旋结构长链起源的探索 636

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

9.1 G（S）问题 646

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

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

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

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

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

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

9.1.7 子点集包含问题 669

9.1.8 2-中心问题 674

9.1.9 k-中心问题 679

9.1.10 最近对问题（CPP） 688

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

9.1.12 邮局问题（POFP） 690

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

9.2 G（E）问题 695

9.2.1 EMST问题 695

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

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

9.2.4 由单点或线段端点起始的生成树 708

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

9.2.6 最小生成网络 715

9.2.7 等长线段构成网格的变形 721

9.3 G（S，E）问题 727

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

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

9.3.3 求解ESMT问题的算法 730

9.4 G（Ω）问题 736

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

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

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

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

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

第10章 图形的学习、推理及判定 758

10.1 旋转与翻转 758

10.2 图形的运算 764

10.3 对称性 767

10.4 相似性 770

10.5 不同子域内的配对及正多边形的构造 774

10.6 由边数、子域数、子图位置间关系等寻找规则 788

10.7 图形序列及组合 796

10.8 由图形组成寻找规则 801

10.9 通过学习及或运算寻找规律 807

待解决的问题 812

算法一览 815

参考文献 826

名词索引 838