计算几何 算法分析与设计2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

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

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

第0章 预备知识1

0.1 算法与数据结构1

0.1.1 算法1

0.1.2 数据结构4

前言7

0.2 相关的几何知识8

0.2.1 基本定义8

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

0.2.3 几何对偶性10

0.3 计算模型11

第1章 几何查找(检索)14

1.1 点定位问题15

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

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

1.2 范围查找问题27

1.2.1 多维二叉树(k-D树)的方法28

1.2.2 直接存取方法30

1.2.3 范围树方法31

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

1.4 平面中线段集和空间中三角形集的正交询问34

1.4.1 吊床询问及推广的吊床询问35

1.4.2 正交限制36

第2章 多边形38

2.1 凸多边形38

2.2 简单多边形42

2.3 多边形的三角剖分47

2.4 多边形的凸划分49

第3章 凸壳57

3.1 凸壳的基本概念57

3.2.1 卷包裹法60

3.2 计算凸壳的算法(二维)60

3.2.2 格雷厄姆方法61

3.2.3 分治算法62

3.2.4 Z3-1算法和Z3-2算法64

3.2.5 实时凸壳算法66

3.2.6 增量算法70

3.2.7 近似凸壳算法71

3.3 计算凸壳的算法(三维)71

3.3.1 基本概念71

3.3.2 卷包裹法73

3.3.3 分治算法74

3.3.4 Z3-3算法76

3.3.5 增量算法77

3.4 凸壳的应用78

3.4.1 确定任意多边形的凸、凹顶点78

3.4.2 利用凸壳求解货郎担问题80

3.4.3 凸多边形直径82

3.4.4 连接两个多边形成一条回路84

4.1 Voronoi图的基本概念88

第4章 Voronoi图及其应用88

4.2 构造Voronoi图的算法92

4.2.1 半平面的交92

4.2.2 增量构造方法93

4.2.3 分治法95

4.2.4 减量算法97

4.2.5 平面扫描算法98

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

4.3 平面点集的三角剖分101

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

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

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

4.4 Voronoi图与三角剖分的应用110

4.4.1 最近邻近110

4.4.2 最大化最小角与三角剖分110

4.4.3 最大空圆111

4.4.4 最小生成树114

4.4.5 货郎担问题115

4.4.6 中轴116

4.4.7 Voronoi图形与凸壳的关系121

4.4.8 Voronoi图的推广123

4.4.9 几何数据压缩130

第5章 交与并133

5.1 线段交的算法133

5.2 多边形的交139

5.2.1 凸多边形交的算法139

5.2.2 星形多边形交的算法143

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

5.3 半平面的交及其应用146

5.3.1 半平面的交146

5.3.2 两个变量的线性规划147

5.4 多边形的并153

5.5 凸多面体的交157

第6章 矩形几何161

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

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

6.3 矩形并的面积与周长163

6.4 矩形并的轮廓166

6.5 矩形并的闭包168

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

6.7 矩形的交173

6.8 应用举例175

第7章 几何体的排列177

7.1 基本概念177

7.2 确定直线排列的算法180

7.3 对偶性181

7.4 Voronoi图185

7.4.1 一维情况185

7.4.2 二维情况187

7.5 应用187

7.5.1 k-最近邻近187

7.5.2 删去隐藏面188

7.5.3 特征图189

7.5.4 点集的分割190

第8章 算法的运动规划192

8.1 最短路径192

8.1.1 可视图及其构造192

8.1.2 Dijkstra算法193

8.2 移动圆盘196

8.3 平移凸多边形197

8.4 移动杆状机器人200

8.4.1 网格分解201

8.4.2 收缩方法203

8.5 机器人臂的运动204

8.5.1 可达性205

8.5.2 构造可达性206

8.6 可分离性209

8.6.1 多种可分离性209

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

8.6.3 分离问题是NP-难的210

8.6.4 模拟河内塔问题211

9.1 G(S)问题212

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

9.1.1 最大间隙问题(MAX G)213

9.1.2 最小覆盖问题(MIN C)215

9.1.3 最近对问题(CPP)218

9.1.4 所有最近邻近问题(ANNP)219

9.1.5 邮局问题(POFP)219

9.2 G(E)问题220

9.2.1 EMST问题221

9.2.2 欧几里德TSP222

9.2.3 欧几里德最大生成树问题(EMXT)223

9.3 G(S，E)问题224

9.3.1 欧几里德Steiner最小树问题(ESMT)225

9.3.2 直线Steiner最小树问题(RSMT)227

9.4 G(Ω)问题228

9.4.1 有障碍物的最大空隙问题(MAX G(Ω))229

9.4.2 具有障碍物的欧几里德最短路径问题(ESPO)230

9.4.3 具有障碍物的Steiner最小树问题(ESMTO)231

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

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

10.1.1 随机二叉树237

10.1.2 跳越表240

10.2 增量算法241

10.2.1 四边形分解242

10.2.2 凸多胞形245

10.2.3 Voronoi图248

10.2.4 构形空间250

10.3 动态算法253

10.4 随机抽样257

10.4.1 具有限界的构形空间257

10.4.2 顶-向下的抽样258

10.4.3 底-向上的抽样260

10.4.4 动态抽样261

10.5 并行几何算法264

10.5.1 凸壳问题266

10.5.2 排列与分解268

10.5.3 邻近269

10.5.4 几何搜索270

10.5.5 可视性和最优化270

算法索引272

参考文献275