"计算几何--算法与应用(第三版)" 是一本深入探讨计算几何领域的书籍,由Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars撰写,邓俊辉翻译,并由清华大学出版社出版。这本书涵盖了计算几何的各种算法和实际应用,包括GIS(地理信息系统)相关的知识。
本书共分为16章,每章都围绕一个特定的主题展开,旨在帮助读者理解和掌握计算几何的核心概念。以下是各章的主要内容:
1. **计算几何:导言** - 引入了计算几何的基本概念,通过凸包的例子展示其重要性,讨论了退化情况的处理和算法的鲁棒性,同时概述了计算几何在不同领域的应用。
2. **线段求交:专题图叠合** - 详细介绍了线段的相交问题,包括双向链接边表的构建,以及如何计算子区域划分的叠合,用于布尔运算。
3. **多边形三角剖分:画廊看守** - 讨论了多边形三角剖分的重要性,如在画廊看守问题中的应用,介绍了单调块划分和单调多边形的三角剖分方法。
4. **线性规划:铸模制造** - 将几何概念应用于铸造过程,解释了半平面求交、递增式线性规划和无界问题的解决策略,还涉及了高维空间的线性规划和最小包围圆问题。
5. **正交区域查找:数据库查询** - 研究了一维和高维空间中的区域查找技术,如kd-树、区域树,适用于数据库查询和数据结构优化。
6. **点定位:找到自己的位置** - 介绍点定位问题,通过梯形图和随机增量式算法解决此问题,讨论了处理退化情况的方法。
7. **Voronoi图:邮局问题** - 定义了Voronoi图的基本概念,展示了如何构造和应用Voronoi图,包括线段集和最远点Voronoi图的特殊情况。
8. **排列与对偶:光线跟踪超采样** - 详细讲解了排列和对偶变换的概念,用于光线跟踪和超采样,以及层阶和偏差的计算。
9. **Delaunay三角剖分:高度插值** - 探讨Delaunay三角剖分在高度插值中的应用,这是地理信息系统中的关键操作。
10. **更多几何数据结构:截窗** - 介绍其他几何数据结构,如截窗,它们在图形学和可视化中有重要作用。
11. **凸包:混合物** - 讨论了凸包算法,这对于理解和处理复杂形状的边界至关重要。
12. **空间二分:画家算法** - 研究了空间分割技术,如画家算法,用于解决图形绘制中的顺序问题。
13. **机器人运动规划:随意所之** - 介绍了机器人路径规划中的几何算法,帮助机器人在复杂环境中导航。
14. **四叉树:非均匀网格生成** - 四叉树作为一种数据结构,用于高效地管理和操作非均匀网格,如地形建模。
15. **可见性图:求最短路径** - 通过构建可见性图来寻找两点间的最短路径,对路径规划问题提供了几何解决方案。
16. **单纯区域查找:再论截窗** - 进一步深化对截窗的理解,引入单纯区域查找,优化了空间搜索和处理。
这本书不仅涵盖了理论知识,还包含注释、评论和习题,旨在帮助读者实践并巩固所学内容,对于学习计算几何及其在GIS和其他应用中的实践非常有帮助。