计算机几何 算法设计与人析 第2版PDF电子书下载
- 电子书积分:14 积分如何计算积分?
- 作 者:周培德著
- 出 版 社:北京:清华大学出版社
- 出版年份:2005
- ISBN:7302101955
- 页数:433 页
第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 欧几里得TSP 355
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
- 《计算机网络与通信基础》谢雨飞,田启川编著 2019
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《设计十六日 国内外美术院校报考攻略》沈海泯著 2018
- 《计算机辅助平面设计》吴轶博主编 2019
- 《计算机组成原理解题参考 第7版》张基温 2017
- 《高校转型发展系列教材 素描基础与设计》施猛责任编辑;(中国)魏伏一,徐红 2019
- 《云计算节能与资源调度》彭俊杰主编 2019
- 《景观艺术设计》林春水,马俊 2019
- 《Helmholtz方程的步进计算方法研究》李鹏著 2019
- 《我知道你在说谎》钱力德著 2019
- 《跟任何人都可以用英语聊聊天》蔡莱蒙德著 2019
- 《控辩平等论 第2版》冀祥德著 2018
- 《纳兰词 下 插图注释版》(清)纳兰性德著;(清)石涛插图 2018
- 《纳兰词》(清)纳兰性德著 2015
- 《dop室内施工图实战教程》赵鲲,朱小斌,周遐德著 2019
- 《瓶花谱》(明)张谦德著;刘靖宇绘 2018
- 《调亏灌溉对旱稻生长的影响》姚帮松,张文萍,陈宏德著 2018
- 《曾国藩全传》蒋星德著 2008
- 《列国志 卡塔尔》孙培德,史菊琴编著 2010
- 《大学计算机实验指导及习题解答》曹成志,宋长龙 2019
- 《指向核心素养 北京十一学校名师教学设计 英语 七年级 上 配人教版》周志英总主编 2019
- 《大学生心理健康与人生发展》王琳责任编辑;(中国)肖宇 2019
- 《大学英语四级考试全真试题 标准模拟 四级》汪开虎主编 2012
- 《大学英语教学的跨文化交际视角研究与创新发展》许丽云,刘枫,尚利明著 2020
- 《北京生态环境保护》《北京环境保护丛书》编委会编著 2018
- 《复旦大学新闻学院教授学术丛书 新闻实务随想录》刘海贵 2019
- 《大学英语综合教程 1》王佃春,骆敏主编 2015
- 《大学物理简明教程 下 第2版》施卫主编 2020
- 《指向核心素养 北京十一学校名师教学设计 英语 九年级 上 配人教版》周志英总主编 2019