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

计算机几何 算法设计与人析 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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

1.1　点定位问题18

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

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

1.1.3　Z1-3算法30

1.2　范围查找问题31

1.2.1　多维二叉树（k-D树）的方法32

1.2.2　直接存取方法34

1.2.3　范围树方法36

1.3　判定点集是否在多边形内37

1.4　平面网络的处理与点q的定位39

第2章　多边形43

2.1 凸多边形43

2.2　简单多边形49

2.3　多边形的三角剖分54

2.4　多边形的凸划分58

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

2.6　下料问题71

2.7　红外图像边缘提取79

2.8　满足特定条件的多边形划分84

2.9　多边形与多边形链87

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

2.11　多边形放大、缩小及移动91

2.12　带状多边形的处理93

第3章　凸壳及其应用96

3.1　凸壳的基本概念96

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

3.2.1　卷包裹法100

3.2.2　格雷厄姆方法101

3.2.3　分治算法102

3.2.4　Z3-1算法与Z3-2算法104

3.2.5　实时凸壳算法107

3.2.6　增量算法111

3.2.7　近似凸壳算法112

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

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

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

3.4.2　解释与时间复杂性119

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

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

3.6.1　基本概念128

3.6.2　卷包裹法129

3.6.3　分治算法131

3.6.4 　Z3-8算法133

3.6.5　增量算法134

3.7.1 确定任意多边形的凸、凹顶点135

3.7　凸壳的应用135

3.7.2　利用凸壳求解货郎担问题138

3.7.3　凸多边形直径140

3.7.4　连接两个多边形成一条回路143

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

4.1　Voronoi图的基本概念147

4.2.1　半平面的交151

4.2.2　增量构造方法151

4.2　构造Voronoi图的算法151

4.2.3　分治法155

4.2.4　减量算法157

4.2.5　平面扫描算法158

4.2.6　构造最远点意义下Voronoi图的算法160

4.3　平面点集的三角剖分162

4.3.1　平面点集三角剖分的贪心算法162

4.3.2　Delaunay三角剖分与多边形内部点集的三角剖分164

4.3.3　平面点集三角剖分的算法166

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

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

4.6.1 最近邻近181

4.6　应用181

4.6.2　最大化最小角的三角剖分182

4.6.3　最大空圆182

4.6.4　最小生成树186

4.6.5　货郎担问题188

4.6.6 中轴188

4.6.7　Voronoi图与凸壳的关系195

4.6.8　Voronoi图的推广198

4.6.9　有约束的Voronoi图206

4.6.10　几何数据压缩207

4.6.11　车辆定位导航系统的新定位算法211

4.6.12　调色214

4.6.13　点集增（删）点之后的三角剖分215

第5章　交与并及其应用217

5.1　线段交的算法217

5.2　多边形的交224

5.2.1　凸多边形交的算法224

5.2.2　星形多边形交的算法228

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

5.3　半平面的交及其应用232

5.3.1　半平面的交232

5.3.2　两个变量的线性规划233

5.4　多边形的并239

5.5　凸多面体的交245

5.6　应用249

5.6.1　地图匹配249

5.6.2　地图数据的处理254

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

第6章　矩形几何256

6.1　判定垂直、水平线段是否相交的算法256

6.2　矩形几何问题的特征及解决问题的途径258

6.3　矩形并的面积与周长259

6.4　矩形并的轮廓262

6.5　矩形并的闭包266

6.6　矩形并的非平凡轮廓和外轮廓269

6.7　矩形的交271

6.8　应用举例274

第7章　几何体的排列276

7.1　基本概念276

7.2　确定直线排列的算法280

7.3　对偶性282

7.4　Voronoi图286

7.4.1　一维情况286

7.4.2　二维情况288

7.5.2　删去隐藏面289

7.5.1　k-最近邻近289

7.5　应用289

7.5.3　特征图290

7.5.4　点集的分割291

第8章　算法的运动规划294

8.1　最短路径295

8.1.1　可视图及其构造295

8.1.2　Z8-1算法296

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

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

8.2　移动圆盘309

8.3　平移凸多边形310

8.4　移动杆状机器人313

8.4.1 网格分解315

8.4.2　收缩方法317

8.5　机器人臂的运动319

8.5.1 可达性319

8.5.2　构造可达性321

8.6　可分离性324

8.6.1　多种可分离性324

8.6.2　借助于平移的可分离性325

8.6.3　分离问题是NP-难的326

8.6.4　模拟河内塔问题326

8.7　满足一定条件的运动规划327

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

9.1　G（S）问题330

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

9.1.2　最小覆盖问题（MIN C）333

9.1.3　2-中心问题337

9.1.4　k-中心问题341

9.1.5　最近对问题（CPP）349

9.1.6　所有最近邻近问题（ANNP）350

9.1.7 邮局问题（POFP）351

9.2　G（E）问题352

9.2.1　EMST问题353

9.2.2 欧几里得TSP355

9.2.3　欧几里得最大生成树问题（EMXT）356

9.3　G（S，E）问题357

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

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

9.4　G（Ω）问题362

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

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

9.4.3　具有障碍物的Steiner最小树问题（ESMTO）366

第10章　随机几何算法与并行几何算法371

10.1　分类和搜索线性表的随机算法372

10.1.1 随机二叉树373

10.1.2　跳越表376

10.2　增量算法378

10.2.1　四边形分解378

10.2.2　凸多胞形382

10.2.3　Voronoi图386

10.2.4　构形空间388

10.3　动态算法391

10.4　随机抽样395

10.4.1　具有限界的构形空间396

10.4.2　顶-向下的抽样397

10.4.3　底-向上的抽样399

10.4.4　动态抽样401

10.5　并行几何算法403

10.5.1 凸壳问题407

10.5.2　排列与分解408

10.5.3　邻近410

10.5.4　几何搜索410

10.5.5　可视性和最优化411

待解决的问题413

算法索引415

参考文献420