计算几何：算法与应用实战指南

《计算几何--算法与应用（第2版）（中文版）》是一本专为希望深入了解计算几何领域的读者设计的教材，特别适合那些对Voronoi图和网络路由感兴趣的人。该书的特点是注重理论与实践相结合，用简洁易懂的方式阐述复杂的概念，避免了全书式的冗长叙述。 本书共分为九章，涵盖了计算几何的核心主题，如线段求交、多边形三角剖分、线性规划、正交区域查找、点定位、Voronoi图、排列与对偶（如光线跟踪中的超采样）、Delaunay三角剖分等。每一章都深入浅出地介绍了相关算法，并通过实例和习题帮助读者理解和掌握这些技术。 1. 章节1：计算几何导论，介绍凸包的概念，探讨了其在实际问题中的应用，如退化情况和算法的鲁棒性。作者通过案例讨论，使读者对计算几何的基本原理有一个初步认识。 2. 章节2：着重于线段求交，包括如何利用双向链接边表进行高效的计算，以及如何通过叠合来确定子区域的划分和布尔运算。 3. 章节3：讲解多边形三角剖分，如看守与三角剖分方法，以及如何对单调多边形进行分割，为几何建模和图形学提供了关键工具。 4. 章节4：将线性规划应用于铸模制造，涉及半平面求交、递增式规划和随机规划等，展示了线性规划在优化问题中的强大作用。 5. 章节5-6：分别讨论正交区域查找和点定位，前者介绍了kd-树和区域树等数据结构，后者探讨了增量式算法和特殊情况下处理策略。 7. 章节7：深入研究Voronoi图，解释其邮局问题的定义和基本性质，以及如何构建和分析不同类型Voronoi图，这在空间分析和地理信息系统中有广泛应用。 8. 章节8：排列与对偶主题，涉及光线跟踪中的超采样，讨论了如何通过差异值计算和对偶变换来优化渲染效果。 9. 章节9：Delaunay三角剖分是最后一个重要部分，探讨如何通过高度优化的算法来处理空间数据的复杂结构。 整体而言，《计算几何--算法与应用（第2版）（中文版）》不仅提供理论知识，还提供了丰富的实践经验，是学习计算几何的理想参考书，对于网络路由、图形处理、计算机视觉等领域都有实际指导意义。书中包含的习题和注释及评论有助于巩固理解和应用所学知识。