计算几何

出版时间：2009-6  出版社：清华大学出版社  作者：（德）伯格（Berg，M.D.） 等著，邓俊辉 译  页数：407  字数：636000  译者：邓俊辉  
Tag标签：无  

前言

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

内容概要

计算几何是计算机理论科学的一个重要分支，自20世纪70年代末从算法设计与分析中独立出来起，已经有了巨大的发展，不仅产生了一系列重要的理论成果，也在众多实际领域中得到了广泛的应用。    本书的前4章对几何算法进行了讨论，包括几何求交、三角剖分、线性规划等，其中涉及的随机算法也是本书的一个鲜明特点。第5章至第10章介绍了多种几何结构，包括几何查找、kd树、区域树、梯形图、Voronoi图、排列、Delaunay三角剖分、区间树、优先查找树以及线段树等。第11章至第16章结合实际问题，继续讨论了若干几何算法及其数据结构，包括高维凸包、空间二分及BSP树、运动规划、网格生成及四叉树、最短路径查找及可见性图、单纯性区域查找及划分树和切分树等，这些也是对前10章内容的进一步深化。    本书不仅内容全面，而且紧扣实际应用，重点突出，既有深入的讲解，同时每章都设有“注释及评论”和“习题”，方便读者更深入的理解，被世界众多大学作为教材。

书籍目录

前言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 注释及评论2 线段求交：专题图叠合  2.1 线段求交  2.2 双向链接边表  2.3 计算子区域划分的叠合  2.4 布尔运算  2.5 注释及评论  习题3 多边形三角剖分：画廊看守  3.1 看守与三角剖分  3.2 多边形的单调块划分  3.3 单调多边形的三角剖分  3.4 注释及评论  习题4 线性规划：铸模制造  4.1 铸造中的几何  4.2 半平面求交  4.3 递增式线性规划  4.4 随机线性规划  4.5 无界线性规划问题  4.6 高维空间中的线性规划  4.7 最小包围圆  4.8 注释及评论  习题5 正交区域查找：数据库查询  5.1 一维区域查找  5.2 kd-树  5.3 区域树  5.4 高维区域树  5.5 一般性点集  5.6 分散层叠  5.7 注释及评论  习题6 点定位：找到自己的位置  6.1 点定位及梯形图  6.2 随机增量式算法  6.3 退化情况的处理  6.4 木尾分析  6.5 注释及评论  习题7 Voronoi图：邮局问题  7.1 定义及基本性质  7.2 构造Voronoi图  7.3 线段集Voronoi图  7.4 最远点Voronoi图  7.5 注释及评论  习题8 排列与对偶：光线跟踪超采样  8.1 差异值的计算  8.2 对偶变换  8.3 直线的排列  ……9 Delaunay三角剖分：高度插值10 更多几何数据结构：截窗11 凸包：混合物12 空间二分：画家算法13 机器人运动规划：随意所之14 四叉树：非均匀网格生成15 可见性图：求最短路径16 单纯形区域查找：再论截窗参考文献图表索引观察结论、引理、定理及推论索引关键词索引

章节摘录

　　与上例相同，这一问题的实质也是几何的：给定一组几何形状不同的障碍物，我们需要在不与任何障碍物发生碰撞的前提下，找出连接于任意两点之间的最短通路。这就是所谓的运动规划（motion planning），在机器人学中，这类问题的求解至关重要。第13和15章将针对运动规划所需的几何算法做一讨论。　　第三个例子。假设你可以利用的不是一张而是两张地图：一张描述了各个建筑物，包括公用电话；另一张则画出了校园内的道路。为了规划出通往公用电话的运动路径，我们需要将这两张地图叠合（overlay）起来——也就是说，需要将这两张地图所提供的信息合并起来。在地理信息系统（geographic information system）中，地图的叠合是基本的操作之一。这种操作涉及到某张地图中的对象在另一张弛图中的定位、不同特征物之间的求交计算等问题。第2章将讨论这一问题。　　许多几何问题的解决都要依靠精心设计的几何算法，上面只是其中的三个例子。诞生于20世纪70年代的计算几何（computational geometry），正是旨在解决这类几何问题。这一学科可定义为“针对处理几何对象的算法及数据结构的系统化研究”，其重点在于“渐进快速的精确算法”。由几何问题带来的挑战吸引了众多的研究人员。从对问题的明确表述，到得出高效而优雅的解决方法，往往需要经历漫长的过程，其间既要克服诸多困难，也要积累一些次优的中间结果。今天，我们已经掌握了功能广泛的一整套几何算法，它们不仅高效而且相对更易理解和实现。　　本书将介绍计算几何中最重要的那些概念、方法、算法以及数据结构，但愿我们的介绍方式，能够吸引那些有志于将计算几何的研究成果付诸实际应用的读者。本书的每一章都从某一实际问题入手，而这种问题的求解，都需要借助几何算法。为了说明计算几何之应用范围的广泛性，这些问题分别选自不同的应用领域：机器人学、计算机图形学、CAD／CAM以及地理信息系统等。

用户评论 (总计3条)

•   还不错啊！！！ 满意！！！
•   刚刚收到，总体浏览了一下。
  书中内容基本是以叙述为主，很少见到数学公式这样的内容。后面的定理大部分都有证明。
  算法流程是以描述性的伪代码给出的，没有计算机源程序。
  
  总体感觉像是一本导论类的书。感觉应该是大学课程教材比较好吧。
  
  如果是想编程的时候参考，最好还是买一本像计算机图形向量运算之类的书，里面给出了完整的计算公式，这样方便编程。
  
  书中的算法还要等后面看了才知道。
  本人非计算机相关专业，属于外行看热闹，只是需要用到一部分计算机几何对象数据结构的内容，才买了。
  
•   还行，有用