计算几何 算法设计与分析PDF|Epub|txt|kindle电子书版本网盘下载

计算几何 算法设计与分析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欧几里得TSP540

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