计算几何：算法与应用第三版

"Computational Geometry: Algorithms and Applications Third Edition 是一本关于计算几何的书籍，由Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars合著。这本书探讨了计算几何领域的算法和应用，特别强调了其在计算机图形学、地理信息系统（GIS）、机器人学等领域的基础性作用。" 计算几何是20世纪70年代末从算法设计与分析领域发展起来的一个研究分支。该学科的成功一方面源于其所研究问题的美感和解决方案的巧妙，另一方面则得益于几何算法在众多应用领域中的核心地位，如计算机图形学用于创建和渲染图像，地理信息系统用于处理和分析地理数据，机器人学则在路径规划和避障等方面依赖几何算法。 本书第三版涵盖了计算几何的广泛主题，可能包括但不限于以下内容： 1. 基本概念：点、线、面的表示与操作，以及几何对象之间的基本关系，如相交、包含和距离计算。 2. 图形绘制算法：Bresenham算法、扫描线算法等用于二维图形的精确描绘。 3. 几何变换：平移、旋转、缩放等操作在计算机图形学中的应用。 4. 多边形处理：多边形的遍历、剪切、求面积和周长，以及凸包和凹包算法。 5. 平面分割：如何高效地分割平面，如Voronoi图和Delaunay三角剖分。 6. 三维计算几何：扩展到三维空间的几何运算，如三维物体的碰撞检测。 7. 线性规划与几何优化：利用几何特性解决最优化问题，如最近点对、最小二乘拟合等。 8. 数据结构：如kd树、voronoi树等，用于高效存储和查询几何数据。 9. 遗留问题与复杂性理论：探讨算法的时间和空间复杂度，以及计算几何中的NP完全问题。 10. 应用实例：深入讲解计算几何在GIS中的应用，如地形分析、道路网络建模，以及机器人导航中的路径规划。 书中还可能介绍了各种算法的实现细节，包括伪代码和实际编程语言的示例，以帮助读者理解和应用这些概念。此外，可能还包含了练习题和案例研究，以促进学习和深化理解。 《Computational Geometry: Algorithms and Applications》是一本全面介绍计算几何的教材，适合计算机科学、工程和数学专业的学生，以及从事相关领域工作的专业人士阅读和参考。通过这本书，读者可以系统地学习计算几何的基本理论和实用技术，从而更好地运用几何算法解决实际问题。