计算几何：算法应用升级，涵盖多领域实例

《计算几何：算法与应用(第三版)》是一本深入探讨计算几何理论和实践的著作，由Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars等人撰写，邓俊辉翻译，清华大学出版社出版。该书主要关注几何算法在多个领域的应用，如几何求交、三角剖分、线性规划，以及更复杂的几何结构分析。 首章通过实例介绍计算几何的基本概念，包括凸包的概念和其在实际问题中的作用，以及算法的鲁棒性和退化情况的处理。第二章和第三章深入研究线段求交和多边形的三角剖分，涉及双向链接边表、子区域划分、布尔运算等技术，并讨论了看守算法在三角剖分中的应用。线性规划在第四章中被用来模拟现实世界中的问题，如铸造过程中的几何优化，包括半平面求交、递增式和随机线性规划，以及高维空间中的应用。 第五章至第十章则转向了更高级的几何数据结构，如正交区域查找、kd-树、区域树和Voronoi图等，它们在数据库查询、点定位和光学渲染（光线跟踪）等领域有广泛应用。Voronoi图的构造和其在邮局问题中的模型是这部分的核心内容。章节六和七介绍了点定位算法，包括梯形图和随机增量式方法，以及如何处理退化情况和尾分析。 接下来的章节进一步探讨了排列与对偶关系，特别是在光线跟踪中的超采样，以及Delaunay三角剖分，这是处理空间数据的一种经典方法，强调了高度优化的几何布局。这些内容不仅展示了计算几何的理论深度，还突出了其在现代计算机图形学、计算机辅助设计（CAD）、地理信息系统（GIS）等领域的实际应用价值。 每一章都包含了丰富的注释和评论，用于解释算法背后的原理和复杂性，以及可能遇到的问题和解决方案。书中还配有许多习题，供读者巩固所学知识并进行实践练习。《计算几何：算法与应用(第三版)》为学习者提供了一个全面的框架，帮助他们理解和掌握计算几何的理论和技巧，以解决实际问题。