计算几何：算法与应用详解

"《计算几何--算法与应用（第2版）》是由荷兰学者Mark de Berg、Marc van Kreveld等人编写的计算几何经典著作，该书深入探讨了计算几何领域的算法及其应用。书中涵盖了从基础的几何求交、三角剖分到高级的几何结构如kd树、Voronoi图等，并结合实际问题讨论了如高维凸包、运动规划等几何算法。此书特别强调了随机算法的使用，并在每一章中提供了注释、评论和习题以帮助读者深入理解和实践。" 计算几何是计算机科学的一个关键分支，主要研究如何用算法解决与几何形状相关的数学问题。本书首先介绍了计算几何的基本概念，通过一个例子——凸包问题，引导读者进入这个领域。接着，详细讨论了线段求交的算法，包括使用双连通边缘列表进行求解，并介绍了如何进行两个几何分割的叠合操作。多边形三角剖分章节则涉及了如何将多边形分解为三角形网络，这对图形学和三维建模至关重要。 书中还详细阐述了线性规划的几何解释和算法，包括半平面求交和随机化方法，这些都是优化问题的基础。正交区域查找部分探讨了kd-树和区域树等数据结构，这些结构在数据库查询和空间索引中有广泛应用。点定位问题则讲解了如何在复杂几何环境中确定点的位置，如使用梯形图和随机增量算法。 Voronoi图和排列章节是计算几何中的重要概念，它们在地理信息系统、机器人路径规划等领域有广泛应用。Delaunay三角剖分是一种特殊类型的三角剖分，其性质保证了相邻三角形的最大内角不相交，对于地形建模和数据分析很有价值。 此外，书中还介绍了高维凸包、空间二分、运动规划、网格生成、最短路径查找、可见性图等高级主题，这些都与现实世界的问题紧密相关。例如，四叉树在图像处理中用于快速访问像素，而BSP树在3D渲染中用于高效地组织物体。最后，书中包含的习题和评论为读者提供了进一步学习和实践的机会。 这本书是计算几何领域的一本权威教材，不仅覆盖了广泛的理论知识，还提供了丰富的实际应用案例，是学习计算几何的理想资源。