资 源 简 介
几何化计算几何研究的对象是几个图形。早期人们对于图像的研究一般都是先建立坐标系，把图形转换成函数，然后用插值和逼近的数学方法，特别是用样条函数作为工具来分析图形，取得了可喜的成功。然而，这些方法过多地依赖于坐标系的选取，缺乏几何不变性，特别是用来解决某些大挠度曲线及曲线的奇异点等问题时，有一定的局限性。几何图形是实际物体的抽象描述，几何化是指被研究对象本身的性质所决定的一种必然趋势。代数化在国外，计算几何的代数化有一股很强的势头。为了在计算机和图形显示终端表示和处理各种复杂的曲面和几何形体，需进行大量的计算，往往需要将问题代数化、线性化、离散化，特别对于最新式的全色连续色调的图像，必须目录22双向链接边表…3723计算子区域划分的叠合24布尔运算5025汴释及评论.26习题+++2多边形三角剖分:画廊看守5731看守与三角剖分3.2多边形的单调块划分….6333单调多边形的三角剖分……34注释及评论.……35习题线性规划:铸模制造8341铸造中的几何.844.2半平面求交4.3谤增式线性规划9444随机线性规划l0245无界线性规划问题10546高维空间中的线性规划…1094.7最小包围圆48注释及评论11849习题120S止交区域查找:数据库查询5.1一维区域查找1255.2kd-树.5.3区域树113654高维区域树1415一股性点集14356“分散层叠1445.7注祥及评论…5.8习题150点定位:找到自己的位置15611点定位及梯形图1556.2随机增量式算法6.3退化情况的处理6.4尾分析17565注释及评论179目录6.6习题…180Voronoi图:邮局问题71定义及基本性质.18572构造 Vorono图7.3线段集 Voronoi图74最远点Vorono图7.5注释及评论7.6习题…2148排列与对偶:光线跟踪超采样2178.1差异值的训算2208.2对偶变换….2238.3直线的排列.84层阶与偏差.2338.5注释及评论.86习题2374 Delaunay三角剖分:高度插值9平面点集的角剖分92 Delaunay三角剖分2489.3构造 Delaunay三角剖分…25394分析26095随机算法框架.96注释及评论.2729.7习题2730更多儿何数据结构:截窗27710.1区间树27910.2优先査找树287103线段树292104注释及评论10.5题…302們1凸包:混合物3071.1三维凸包的复杂度……112构造三维凸包…311113“分析317114凸包与半空间求交11.5再论 Voronoi图322目录1.6注释及评论….………325117题.2空间二分:画家算法32912.1BSP树的定义.12.2BSP树及画家算法33312.3构造BSP树.335124维BSP树的规模12.5低密度场景的BSP树…34412.6注释及评论127习题侶机器人运动规划:随意所之35713.1工作空间与C空间…13.2点机器人133 Minkowski和367134平移式运动规划37613.5允许旋转的运动规划379136注释及评论….38313.7习题…...385№四叉树:非均匀网格生成38714.1均匀及非均匀网格.…38914.2点集的四叉树39114.3从四叉树到网格144注释及评论.…40214.5习题.404伛可性图:求最短路径」40715.1点机器人的最短路径…408152构造可见性图412153平移运动多边形机器人的最短路径417154注释及评论……41815.5习题419伛单纯形区域查找:再论截窗16.1划分树.·*42216.2多层划分树430163切分树433164注释及评论.439目录165习题..441参考文献图表索引观察结论、引理、定理及推论索引一XXXV111关健词索引前言前言十世纪七十年代末,计算几何学( computational geometry)从算法设计与分析中孕育而生。今天,它不仪拥有自己的学术刊物和学术会议,而且形成了个由众多活跃的研究人员组成的学术群体,因此已经成长为个被广泛认同的学科。该领域作为个研究学科之所以会取得成功,·方面是由」其涉及的问题及其解答木身所具有的美感,而另一方面,也是由于在(诸如计算机图形学、地理信息系统和机器人学等)众多的应用领域中,儿何算法都发挥了重要的作用。解决许多几何问题的早期算法,要么速度很慢,要么难于理解与实现。随着近年来一些新的算法技术的发展,此前的很多方法都得到了改进与简化。这本教材力图使得这些现代的算法能够为更泛的读者理解和接受。本书既是面向计算几何课程的一本教材,同时也可用于自学。本书的结构。除《导言》外,这16章中的每一章都从来自应用领域的某一实际问题入于。这个问题将被转化为一个纯粹的几何问题,进而通过计算几何所提供的方法加以解决。每章所讨论的,实质上就是对应的那个几何问题,以及解决该问题所需要的概念与方法。我们根据所希望覆盖的计算几何专题,来选取有关的应用;而就具体的应用领域而言,这些介绍还远远不够全面。引入这些应用的目的,只是为了激发读者的兴趣;而各章本身的目的,并不在于为这些问题提供现成可用的解决前言方法。虽然如此,我们还是认为,为有效地解决应用中的几何问题,计算几何方面的知识是非常重要的。希望本书不仅能够吸引来自算法学术圈的那些人,而且对来自应用领域的人们亦是如此。同一几何问题,可能有好几种不同的解决方法,不过,在论述大多数几何问题时,我们将只给出其中·种。我们通常所选取的,都是最易于理解与实现的方法。我们也十分注意,尽力使本书能够涵盖更多的方法,比如分治策略、平面扫描以及随机算法( randomized algorithm)等等。刈每个问题可能的种种变型,我们也不打算面面俱到;我们觉得,更重要的是首先对计算几何中的各个主要问题徹一介绍,而不是过」深入地去探究少数专题的细枝木节。某些章的若干节标有星号。这些节的内容涉及解法的改进与扩展,或者解释了不同问题之间的相互关联。就对后续章节的理解而言,它们并不十分重要。每章最后,都由名为“注释及评论”的一节进行概括总结。这些节会给出对应各章所介绍结果的来龙去脉,概述其它的解决方法、一般化处理方法及改进,并给出参考文献。虽然这些节可以被跳过,但是对于那些希望就某一章的专题做进一步了解的读者来说,其中的材料都是非常有用的。每章后面,都附有一定数量的习题。其中一些旨在检查读者对内容的理解程度,也有些是对书中内容的推广,需要精心解答。高难度的问题以及对应于标有星号各节的问题,也被标上星号。课程大纲。尽管在很大程度上,本书各章之间是相互独立的,但在进行介绍时,最好还是不要随意打乱其次序。例如,第2章介绍了平面打措算法,故在阅读采用了这一方法的其它各章之前,最好首先了解该章的内谷。出于同样考虑,在进入有关随机算法的各章之前,也应该首先阋读第4章。如果是作为计算几何的第门课程,建议(教师)按照书中的次序来讲授前十章。根据我们的经验,这丨章覆盖了任何一门计算儿何课程都必须介绍的概念和方法。如果还有可能顾及更多的内容,可以在后面六章中进行挑选。先修要求。做为教材,本书既适用于高年级本科生课程,也适用于低年级硏究生课程,具体安排视课桯的其它要求而定。者应具备算法设计与分析、数据结构的基本知识:必须熟知大O记号,以及诸如排序、二分査找和平衡査找树等基本的算法技术。读者不需要对这里所涉及的应用领域有所了解,也几乎不需要什么几何知识。在对随机算法进行分析时,会用到一些非常基本的概率理论。实现。夲书中的算法都是以伪代码的形式给出,虽略显慨括笼统,但也算详尽,实现起来相对容易。值得一提的是,我们还尝试着介绍了处理退化情况的方法,在具体实现过程中如不能解决好这一问题,往往会使整个计划落空我们认为,动手实现其中个或多个算法将十分有益;这可以令你获得对算法复杂度的实际感受。每·章都可以当成个编程训练的课程项目。根据可利用吋间的多少,你既可以只实现算法本身,也可以连同应用系统起完成为了实现一个几何算法,若干基本的数据类型点、直线和多边形等以及对其实施操作Ⅴi/vi前言的一些基本例程都是必需的。实现这些基本例程并使之具有鲁棒性,绝非易事,为此需要投入大量的时间。自己动手这样做一次不无裨益,然而如果能够找到一个提供基本数据类型及其捰作例程的现成的软件库,将很有帮助。在我们的万维网页面上,可以找到指向这类软件库的链接万维网站。本书还附有个万维网站,该网站提供了本书各个版本的勘误、所有插图、所有算法的伪代码,以及一些其它资源。其地址是:http://www.cs.uu.nl/geobook/如果您发现了书中的错误,或是对本书有何建议,可以通过该页面与我们联系。关于第三版。第三版的改动主要有两处:第7章“ Voronoi图:邮局问题”中,增加了关于线段 orono图、最远点 Voronoi图的讨论;第12章“空间二分:画家算法”中,针对低密度场景的BSP树,作为实际输入模型的导论,增加了一芍。此外,更正了大量瑕疵与错误(请参阅网站提供的第版勘误)每章的“注释及评论”一节也做了更新,以体现新的研究成果及相关文献。为不致影响学生继续在课程学习中沿用第版,第三版尽可能没冇改动原先各节与各习题的编号。致谢。编写教材是项耗吋的⊥作,即便有四位作者共同合作,也不例外。在过去几年中我们得到了很多人的帮助:关于本书应该包括、不应该包括哪些内容,有些人提供了有益的建议,有些人在阅读初稿后对如何修改提出了建议,另些人则指出并更止了前两版中的错误。感谢所有这些人,特别要感谢 Pankaj agarwal、 Helmut alu、 Marshall berr、 Jil bose、Ha∠ el Everett Gerald farin、 SteveFortune、 Geert-Jan giezeman、 Mordecai golin、 Dan Halperin, Richard Karp、 Matthew katz、 Klara Kedem、Nelson max、 Joseph s.B. Mitchell, Rene van oostrum、 Gunter rote、 Henry Shapiro、 Sven Skyum、Jack snoeyink、 Gert Vegter、 Peter Widmayer、 Chee Yap和 Gunther Zieg!ler。感谢 Springer-Verlag出版社给予的建议和支持,使得本书各版本得以出版,并被译成日文、中文及波兰文。最后,还要感谢荷ˇ科学研究组织( Netherlands Organization for Scientific Research-NW.O.)与韩国研究基金( Korea research foundation-KRF)的人力支持。2008年1月Mark de bergfried cheongMarc van KreveldMarkⅴ ermarsviii/viii计算几何:导言正漫步于校园的你,突然需要打一个紧急电话。在遍布校园的各个公用电话中,你当然想找到离自己最近的那部。然而,哪一部才是最近的呢?一张校园地图将能帮忙,无论你身处何处,都可以在地图上找到最近的公用电话。这张地图可能会将整个校园划分成不同区域,每个区域都对应着部最近的公用电话(如图1-1所示)。这些区域形状如何?又该如何计算出它们呢?尽管这算不上·个至关重要的问题,它却简要描述了个主要的几何概念,而这概念在众多应用中都扮演着重要的角色。
