计算几何算法与应用 pdf.pdf

发布时间：2022-06-01 发布人：admin 分类：说明书资料大小：4.56M 资料格式：pdf 举报版权申诉

libao632725532-7675389-4744302543349023512.pdf-第1页.png

第1页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第2页.png

第2页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第3页.png

第3页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第4页.png

第4页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第5页.png

第5页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第6页.png

第6页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第7页.png

第7页 / 共509页

libao632725532-7675389-4744302543349023512.pdf-第8页.png

第8页 / 共509页

前言

1 计算几何：导言

1.1 凸包的例子

1.2 退化及鲁棒性

1.3 应用领域

1.3.1 计算机图形学

1.3.2 机器人学

1.3.3 地理信息系统

1.3.4 CAD/CAM

1.3.5 其它应用领域

1.4 注释及评论

1.5 习题

2 线段求交：专题图叠合

2.1 线段求交

2.2 双向链接边表

2.3 计算子区域划分的叠合

2.4 布尔运算

2.5 注释及评论

2.6 习题

3 多边形三角剖分：画廊看守

3.1 看守与三角剖分

3.2 多边形的单调块划分

3.3 单调多边形的三角剖分

3.4 注释及评论

3.5 习题

4 线性规划：铸模制造

4.1 铸造中的几何

4.2 半平面求交

4.3 递增式线性规划

4.4 随机线性规划

4.5 无界线性规划问题

4.6 *高维空间中的线性规划

4.7 *最小包围圆

4.8 注释及评论

4.9 习题

5 正交区域查找：数据库查询

5.1 一维区域查找

5.2 kd 树

5.3 区域树

5.4 高维区域树

5.5 一般性点集

5.6 *分散层叠

5.7 注释及评论

5.8 习题

6 点定位：找到自己的位置

6.1 点定位及梯形图

6.2 随机增量式算法

6.3 退化情况的处理

6.4 *尾分析

6.5 注释及评论

6.6 习题

7 Voronoi图：邮局问题

7.1 定义及基本性质

7.2 构造Voronoi图

7.3 线段集Voronoi图

7.4 最远点Voronoi图

7.5 注释及评论

7.6 习题

8 排列与对偶：光线跟踪超采样

8.1 差异值的计算

8.2 对偶变换

8.3 直线的排列

8.4 层阶与偏差

8.5 注释及评论

8.6 习题

9 Delaunay三角剖分：高度插值

9.1 平面点集的三角剖分

9.2 Delaunay三角剖分

9.3 构造Delaunay三角剖分

9.4 分析

9.5 *随机算法框架

9.5.1 半平面求交

9.5.2 梯形图

9.5.3 Delaunay三角剖分

9.6 注释及评论

9.7 习题

10 更多几何数据结构：截窗

10.1 区间树

10.2 优先查找树

10.3 线段树

10.4 注释及评论

10.5 习题

11 凸包：混合物

11.1 三维凸包的复杂度

11.2 构造三维凸包

11.3 *分析

11.4 *凸包与半空间求交

11.5 *再论Voronoi图

11.6 注释及评论

11.7 习题

12 空间二分：画家算法

12.1 BSP树的定义

12.2 BSP树及画家算法

12.3 构造BSP树

12.4 *三维BSP树的规模

12.5 低密度场景的BSP树

12.6 注释及评论

12.7 习题

13 机器人运动规划：随意所之

13.1 工作空间与C-空间

13.2 点机器人

13.3 Minkowski和

13.4 平移式运动规划

13.5 *允许旋转的运动规划

13.6 注释及评论

13.7 习题

14 四叉树：非均匀网格生成

14.1 均匀及非均匀网格

14.2 点集的四叉树

14.3 从四叉树到网格

14.4 注释及评论

14.5 习题

15 可见性图：求最短路径

15.1 点机器人的最短路径

15.2 构造可见性图

15.3 平移运动多边形机器人的最短路径

15.4 注释及评论

15.5 习题

16 单纯形区域查找：再论截窗

16.1 划分树

16.2 多层划分树

16.3 切分树

16.4 注释及评论

16.5 习题

参考文献

图表索引

观察结论、引理、定理及推论索引

关键词索引

计算几何 ⎯⎯ 算法与应用 Mark de Berg Otfried Cheong Marc van Kreveld Mark Overmars 邓俊辉著译清华大学出版社

目录目录 i vi 1 目录前言 11 计算几何：导言 1.1 凸包的例子.................................................................................................................................................... 3 1.2 退化及鲁棒性.............................................................................................................................................. 12 1.3 应用领域...................................................................................................................................................... 13 1.4 注释及评论.................................................................................................................................................. 17 1.5 习题.............................................................................................................................................................. 19 22 线段求交：专题图叠合 23 2.1 线段求交...................................................................................................................................................... 25 i / viii

目录 2.2 双向链接边表.............................................................................................................................................. 37 2.3 计算子区域划分的叠合.............................................................................................................................. 42 2.4 布尔运算...................................................................................................................................................... 50 2.5 注释及评论.................................................................................................................................................. 51 2.6 习题.............................................................................................................................................................. 52 33 多边形三角剖分：画廊看守 57 3.1 看守与三角剖分.......................................................................................................................................... 58 3.2 多边形的单调块划分.................................................................................................................................. 63 3.3 单调多边形的三角剖分.............................................................................................................................. 73 3.4 注释及评论.................................................................................................................................................. 78 3.5 习题.............................................................................................................................................................. 79 44 线性规划：铸模制造 83 4.1 铸造中的几何.............................................................................................................................................. 84 4.2 半平面求交.................................................................................................................................................. 88 4.3 递增式线性规划.......................................................................................................................................... 94 4.4 随机线性规划............................................................................................................................................ 102 4.5 无界线性规划问题.................................................................................................................................... 105 4.6 *高维空间中的线性规划 ........................................................................................................................... 109 4.7 *最小包围圆 ............................................................................................................................................... 113 4.8 注释及评论................................................................................................................................................ 118 4.9 习题............................................................................................................................................................ 120 55 正交区域查找：数据库查询 123 5.1 一维区域查找............................................................................................................................................ 125 5.2 kd-树........................................................................................................................................................... 128 5.3 区域树........................................................................................................................................................ 136 5.4 高维区域树................................................................................................................................................ 141 5.5 一般性点集................................................................................................................................................ 143 5.6 *分散层叠 ................................................................................................................................................... 144 5.7 注释及评论................................................................................................................................................ 148 5.8 习题............................................................................................................................................................ 150 66 点定位：找到自己的位置 153 6.1 点定位及梯形图........................................................................................................................................ 155 6.2 随机增量式算法........................................................................................................................................ 162 6.3 退化情况的处理........................................................................................................................................ 172 6.4 *尾分析 ....................................................................................................................................................... 175 6.5 注释及评论................................................................................................................................................ 179 ii / viii

目录 6.6 习题............................................................................................................................................................ 180 77 Voronoi图：邮局问题 183 7.1 定义及基本性质........................................................................................................................................ 185 7.2 构造Voronoi图........................................................................................................................................... 190 7.3 线段集Voronoi图....................................................................................................................................... 202 7.4 最远点Voronoi图....................................................................................................................................... 206 7.5 注释及评论................................................................................................................................................ 210 7.6 习题............................................................................................................................................................ 214 88 排列与对偶：光线跟踪超采样 217 8.1 差异值的计算............................................................................................................................................ 220 8.2 对偶变换.................................................................................................................................................... 223 8.3 直线的排列................................................................................................................................................ 227 8.4 层阶与偏差................................................................................................................................................ 233 8.5 注释及评论................................................................................................................................................ 234 8.6 习题............................................................................................................................................................ 237 99 Delaunay三角剖分：高度插值 241 9.1 平面点集的三角剖分................................................................................................................................ 244 9.2 Delaunay三角剖分 ..................................................................................................................................... 248 9.3 构造Delaunay三角剖分............................................................................................................................. 253 9.4 分析............................................................................................................................................................ 260 9.5 *随机算法框架 ........................................................................................................................................... 264 9.6 注释及评论................................................................................................................................................ 272 9.7 习题............................................................................................................................................................ 273 1100 更多几何数据结构：截窗 277 10.1 区间树...................................................................................................................................................... 279 10.2 优先查找树.............................................................................................................................................. 287 10.3 线段树...................................................................................................................................................... 292 10.4 注释及评论.............................................................................................................................................. 300 10.5 习题.......................................................................................................................................................... 302 1111 凸包：混合物 307 11.1 三维凸包的复杂度 .................................................................................................................................. 310 11.2 构造三维凸包.......................................................................................................................................... 311 11.3 *分析 ......................................................................................................................................................... 317 *凸包与半空间求交.................................................................................................................................. 321 11.4 11.5 *再论Voronoi图......................................................................................................................................... 322 iii / viii

目录 11.6 注释及评论.............................................................................................................................................. 325 11.7 习题.......................................................................................................................................................... 325 1122 空间二分：画家算法 329 12.1 BSP树的定义 ........................................................................................................................................... 331 12.2 BSP树及画家算法.................................................................................................................................... 333 12.3 构造BSP树............................................................................................................................................... 335 12.4 *三维BSP树的规模 .................................................................................................................................. 340 12.5 低密度场景的BSP树............................................................................................................................... 344 12.6 注释及评论.............................................................................................................................................. 353 12.7 习题.......................................................................................................................................................... 354 1133 机器人运动规划：随意所之 357 13.1 工作空间与C-空间.................................................................................................................................. 359 13.2 点机器人.................................................................................................................................................. 362 13.3 Minkowski和 ............................................................................................................................................ 367 13.4 平移式运动规划...................................................................................................................................... 376 13.5 *允许旋转的运动规划 ............................................................................................................................. 379 13.6 注释及评论.............................................................................................................................................. 383 13.7 习题.......................................................................................................................................................... 385 1144 四叉树：非均匀网格生成 387 14.1 均匀及非均匀网格.................................................................................................................................. 389 14.2 点集的四叉树.......................................................................................................................................... 391 14.3 从四叉树到网格...................................................................................................................................... 399 14.4 注释及评论.............................................................................................................................................. 402 14.5 习题.......................................................................................................................................................... 404 1155 可见性图：求最短路径 407 15.1 点机器人的最短路径.............................................................................................................................. 408 15.2 构造可见性图.......................................................................................................................................... 412 15.3 平移运动多边形机器人的最短路径 ...................................................................................................... 417 15.4 注释及评论.............................................................................................................................................. 418 15.5 习题.......................................................................................................................................................... 419 1166 单纯形区域查找：再论截窗 421 16.1 划分树...................................................................................................................................................... 422 16.2 多层划分树.............................................................................................................................................. 430 16.3 切分树...................................................................................................................................................... 433 16.4 注释及评论.............................................................................................................................................. 439 iv / viii

目录 16.5 习题.......................................................................................................................................................... 441 参考文献图表索引观察结论、引理、定理及推论索引关键词索引 i xxiv xxxviii xliv v / viii

前言前言二十世纪七十年代末，计算几何学（computational geometry）从算法设计与分析中孕育而生。今天，它不仅拥有自己的学术刊物和学术会议，而且形成了一个由众多活跃的研究人员组成的学术群体，因此已经成长为一个被广泛认同的学科。该领域作为一个研究学科之所以会取得成功，一方面是由于其涉及的问题及其解答本身所具有的美感，而另一方面，也是由于在（诸如计算机图形学、地理信息系统和机器人学等）众多的应用领域中，几何算法都发挥了重要的作用。解决许多几何问题的早期算法，要么速度很慢，要么难于理解与实现。随着近年来一些新的算法技术的发展，此前的很多方法都得到了改进与简化。这本教材力图使得这些现代的算法能够为更广泛的读者理解和接受。本书既是面向计算几何课程的一本教材，同时也可用于自学。本书的结构。除《导言》外，这 16 章中的每一章都从来自应用领域的某一实际问题入手。这个问题将被转化为一个纯粹的几何问题，进而通过计算几何所提供的方法加以解决。每章所讨论的，实质上就是对应的那个几何问题，以及解决该问题所需要的概念与方法。我们根据所希望覆盖的计算几何专题，来选取有关的应用；而就具体的应用领域而言，这些介绍还远远不够全面。引入这些应用的目的，只是为了激发读者的兴趣；而各章本身的目的，并不在于为这些问题提供现成可用的解决 vi / viii

前言方法。虽然如此，我们还是认为，为有效地解决应用中的几何问题，计算几何方面的知识是非常重要的。希望本书不仅能够吸引来自算法学术圈的那些人，而且对来自应用领域的人们亦是如此。同一几何问题，可能有好几种不同的解决方法，不过，在论述大多数几何问题时，我们将只给出其中一种。我们通常所选取的，都是最易于理解与实现的方法。我们也十分注意，尽力使本书能够涵盖更多的方法，比如分治策略、平面扫描以及随机算法（randomized algorithm）等等。对每个问题可能的种种变型，我们也不打算面面俱到；我们觉得，更重要的是首先对计算几何中的各个主要问题做一介绍，而不是过于深入地去探究少数专题的细枝末节。某些章的若干节标有星号。这些节的内容涉及解法的改进与扩展，或者解释了不同问题之间的相互关联。就对后续章节的理解而言，它们并不十分重要。每章最后，都由名为“注释及评论”的一节进行概括总结。这些节会给出对应各章所介绍结果的来龙去脉，概述其它的解决方法、一般化处理方法及改进，并给出参考文献。虽然这些节可以被跳过，但是对于那些希望就某一章的专题做进一步了解的读者来说，其中的材料都是非常有用的。每章后面，都附有一定数量的习题。其中一些旨在检查读者对内容的理解程度，也有些是对书中内容的推广，需要精心解答。高难度的问题以及对应于标有星号各节的问题，也被标上星号。课程大纲。尽管在很大程度上，本书各章之间是相互独立的，但在进行介绍时，最好还是不要随意打乱其次序。例如，第 2 章介绍了平面扫描算法，故在阅读采用了这一方法的其它各章之前，最好首先了解该章的内容。出于同样考虑，在进入有关随机算法的各章之前，也应该首先阅读第 4 章。如果是作为计算几何的第一门课程，建议（教师）按照书中的次序来讲授前十章。根据我们的经验，这十章覆盖了任何一门计算几何课程都必须介绍的概念和方法。如果还有可能顾及更多的内容，可以在后面六章中进行挑选。先修要求。做为教材，本书既适用于高年级本科生课程，也适用于低年级研究生课程，具体安排视课程的其它要求而定。读者应具备算法设计与分析、数据结构的基本知识：必须熟知大 O 记号，以及诸如排序、二分查找和平衡查找树等基本的算法技术。读者不需要对这里所涉及的应用领域有所了解，也几乎不需要什么几何知识。在对随机算法进行分析时，会用到一些非常基本的概率理论。实现。本书中的算法都是以伪代码的形式给出，虽略显概括笼统，但也算详尽，实现起来相对容易。值得一提的是，我们还尝试着介绍了处理退化情况的方法，在具体实现过程中如不能解决好这一问题，往往会使整个计划落空。我们认为，动手实现其中一个或多个算法将十分有益；这可以令你获得对算法复杂度的实际感受。每一章都可以当成一个编程训练的课程项目。根据可利用时间的多少，你既可以只实现算法本身，也可以连同应用系统一起完成。为了实现一个几何算法，若干基本的数据类型⎯⎯点、直线和多边形等⎯⎯以及对其实施操作 vii / viii

分享到：

赞收藏

资料库

计算几何算法与应用 pdf.pdf

相关推荐

行业

热门标签

最新资料