计算几何：算法与应用详解——从求交到Voronoi图

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