《计算几何:算法与应用》是一本由Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars四位作者共同编写的经典教材,涵盖了计算几何的核心理论和广泛应用。本书旨在介绍计算几何的基本概念、算法以及它们在诸如图形学、计算机辅助设计、数据库管理、优化问题等领域的实际应用。
第一章,"计算几何:导言",首先通过实例介绍凸包的概念,让读者理解计算几何的基本思想,例如通过凸包来描述一组点集的边界。接着,章节探讨了计算几何的退化情况和鲁棒性,强调算法应对各种特殊情况的能力。此外,作者还介绍了计算几何的应用领域,包括计算机图形学、机器人学、地理信息系统等,并附有注释和评论以帮助读者深化理解,以及习题供实践练习。
第二章至第九章深入剖析了一系列核心主题。如:
- **线段求交:专题图叠合** 部分讲述了如何高效地检测和计算线段之间的交点,涉及双向链接边表数据结构和子区域划分的叠合技术。
- **多边形三角剖分:画廊看守** 主要讨论了用看守方法进行多边形分割,以及单调块划分和单调多边形的三角剖分策略。
- **线性规划:铸模制造** 展示了线性规划在制造过程中的应用,包括半平面求交、递增式和随机线性规划等不同类型的优化问题。
- **正交区域查找:数据库查询** 讲解了一维到高维区域搜索的数据结构,如kd-树和区域树,以及它们在数据库查询中的作用。
- **点定位:找到自己的位置** 介绍了定位算法,如梯形图和随机增量式方法,以及如何处理退化情况和特殊问题。
- **Voronoi图:邮局问题** 着重于Voronoi图的定义、构造以及其在诸如无线网络覆盖、地理编码等场景中的应用。
- **排列与对偶:光线跟踪超采样** 提供了计算光强度差异的方法,以及对偶变换在图像处理中的应用,如光线跟踪和图像渲染。
- **Delaunay三角剖分:高度** 介绍了Delaunay三角剖分,这是计算几何中的一个重要概念,常用于确保数据点的密度均匀分布。
这些章节不仅提供了扎实的理论基础,还展示了实际问题解决中的应用技巧,有助于读者理解和掌握计算几何的精髓,并能够在实际项目中灵活运用所学知识。每章末尾的注释和评论以及习题部分,进一步巩固了读者的理解,激发了他们的思考和探索欲望。