计算几何算法精讲：从线段求交到Voronoi图

"《计算几何--算法与应用》(第三版)是一本深入探讨计算几何领域的书籍，由Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars编写，由邓俊辉翻译，由清华大学出版社出版。本书包含多个章节，详细介绍了计算几何中的关键算法和应用，如线段求交、多边形三角剖分、线性规划、正交区域查找、点定位、Voronoi图和排列与对偶等。书中的每个主题都配备了实例、注释、评论和习题，旨在帮助读者理解和掌握计算几何的核心概念和技术。" 在计算几何这个领域，本书首先引入了计算几何的基本概念，通过凸包的例子展示了其在实际问题中的应用，并讨论了退化情况的处理和鲁棒性问题。接着，第二章聚焦于线段求交，介绍了专题图叠合和双向链接边表等数据结构来高效解决这个问题，同时涉及布尔运算。 第三章关注多边形三角剖分，这是一个在图形学和科学计算中有广泛应用的技术。通过看守与三角剖分的关系，讲解了如何将多边形分割为简单的三角形，并特别讨论了单调多边形的三角剖分方法。 第四章涉及线性规划，这是运筹学中的一个重要分支，书中详细讲解了半平面求交、递增式线性规划以及随机线性规划等方法，还触及到高维空间的线性规划问题和最小包围圆的计算。 第五章主要介绍正交区域查找，这是数据库查询和空间索引的关键技术，包括了一维查找、kd-树、区域树以及高维区域树的概念和实现。 第六章关注点定位问题，解释了梯形图和随机增量式算法，讨论了如何处理退化情况，并简要提及了尾分析。 第七章深入Voronoi图，这是一种描述空间中点分布的几何结构，书中详细描述了Voronoi图的定义、构建方法，以及线段集和最远点Voronoi图的特性。 第八章涉及排列与对偶，讲解了如何利用对偶变换解决光线跟踪和超采样问题，以及排列的计算和偏差分析。 最后，第九章介绍了Delaunay三角剖分，这是一种在几何建模和数据分析中广泛使用的三角化方法，强调了高度与邻接性的关系。 《计算几何--算法与应用》提供了丰富的理论知识和实践技巧，是学习和研究计算几何的重要参考资料。