计算几何 ⎯⎯ 算法与应用

计算几何：算法与应用（第三版） 二十世纪七十年代末,计算几何学(computational geometry)从算法设计与分析中孕育而生。 今天,它不仅拥有自己的学术刊物和学术会议,而且形成了一个由众多活跃的研究人员组成的学术 群体,因此已经成长为一个被广泛认同的学科。该领域作为一个研究学科之所以会取得成功,一方 面是由于其涉及的问题及其解答本身所具有的美感,而另一方面,也是由于在(诸如计算机图形学、 地理信息系统和机器人学等)众多的应用领域中,几何算法都发挥了重要的作用。

计算几何 = Computational geometry : 算法与应用algorithms and applications

计算几何 算法与应用 pdf

非扫描版

第一章 计算几何：导言 第二章 线段求交：专题图叠合 第三章 多边形三角剖分：画廊看守 第四章 线性规划：铸模制造 第五章 正交区域查找：数据库查询 第六章 点定位：找到自己的位置 第七章 Voronoc图：邮局问题 第八章 排列与对偶：光线跟踪超采样 第九章 Delaunay三角剖分：高度插值 第十章 更多几何数据结构：截窗 第十一章 凸包：混合物 第十二章 空间二分：画家算法 第十三章 机器人运动规划：随意所之 第十四章 四叉树：非均匀网格生成 第十五章 可见性图：求最短路径 第十六章 单纯区域查找：再论截窗

中文名: 计算几何--算法与应用 原名: Computational Geometry:Algorithms and Applications 作者: (荷)Mark de Berg, Marc van Kreveld等资源格式: PDF 版本: 第3版　清晰版 出版社: Springer Berlin Heidelberg书号: 3642096816发行时间: 2009年 地区: 美国 语言: 英文 简介: 内容简介： 计算几何是计算机理论科学的一个重要分支.自20世纪70年代末从算法设计与分析中独立出来起，不到30年，该学科已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用. 本书的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是本书的一个鲜明特点.第5章至第10章介绍了多种几何结构，包括几何查找、kd树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等.第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前十章内容的进一步深化. 本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，为读者更深入的理解提供了可能. 目录: Table of Contents 1 Computational Geometry --- Introduction 1.1 An Example: Convex Hulls 1.2 Degeneracies and Robustness 1.3 Application Domains 1.4 Notes and Comments 1.5 Exercises 2 Line Segment Intersection --- Thematic Map Overlay 2.1 Line Segment Intersection 2.2 The Doubly-Connected Edge List 2.3 Computing the Overlay of Two Subdivisions 2.4 Boolean Operations 2.5 Notes and Comments 2.6 Exercises 3 Polygon Triangulation --- Guarding an Art Gallery 3.1 Guarding and Triangulations 3.2 Partitioning a Polygon into Monotone Pieces 3.3 Triangulating a Monotone Polygon 3.4 Notes and Comments 3.5 Exercises 4 Linear Programming --- Manufacturing with Molds 4.1 The Geometry of Casting 4.2 Half-Plane Intersection 4.3 Incremental Linear Programming 4.4 Randomized Linear Programming 4.5 Unbounded Linear Programs 4.6* Linear Programming in Higher Dimensions 4.7* Smallest Enclosing Discs 4.8 Notes and Comments 4.9 Exercises 5 Orthogonal Range Searching --- Querying a Database 5.1 1-Dimensional Range Searching 5.2 Kd-Trees 5.3 Range Trees 5.4 Higher-Dimensional Range Trees 5.5 General Sets of Points 5.6* Fractional Cascading 5.7 Notes and Comments 5.8 Exercises 6 Point Location --- Knowing Where You Are 6.1 Point Location and Trapezoidal Maps 6.2 A Randomized Incremental Algorithm 6.3 Dealing with Degenerate Cases 6.4* A Tail Estima

Mard de Berg Otfried Cheong Marc van Kreveld Mard Overmars

NULL 博文链接：https://yye.iteye.com/blog/740390

计算几何算法与应用(中文版).pdf