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

"计算几何-算法与应用" 是一本关于计算几何领域的经典著作，由Mark de Berg、Otfried Cheong、Marc van Kreveld和Mark Overmars共同撰写，并由邓俊辉翻译成中文，由清华大学出版社出版。本书涵盖了计算几何的基础理论、算法及其在不同领域的应用。 内容概述： 1. 计算几何导论：本章介绍计算几何的基本概念，通过一个凸包的例子引入，讨论了计算几何中的关键问题和挑战，如退化情况的处理和算法的鲁棒性。此外，还提到了计算几何在图形学、物理模拟、工程设计等领域的广泛应用。 2. 线段求交：专题图叠合：本章聚焦于线段之间的交点检测，介绍了如何高效地处理大量线段的交点问题，包括双向链接边表的构建和计算子区域划分的叠合。此外，还讨论了布尔运算（如并、交、差）在计算几何中的应用。 3. 多边形三角剖分：画廊看守：章节关注多边形的三角剖分问题，解释了为何需要三角剖分以及如何进行，特别讨论了多边形的单调块划分和单调多边形的三角剖分方法。这对于三维图形渲染和几何建模至关重要。 4. 线性规划：铸模制造：这部分介绍了线性规划在几何中的应用，比如在铸造过程中的几何问题，讲解了半平面求交和递增式线性规划的算法，同时涉及了随机线性规划和无界问题的处理。高维空间中的线性规划和最小包围圆问题也作为扩展内容进行了讨论。 5. 正交区域查找：数据库查询：章节涉及一维和高维的区域查找算法，包括kd-树和区域树的构建，以及如何处理高维数据的查询效率问题。还介绍了适用于一般性点集的查找策略和分散层叠的概念。 6. 点定位：找到自己的位置：本章讲解点定位问题，通过梯形图和随机增量式算法解决，探讨了如何处理退化情况，以及高级的尾分析技术。 7. Voronoi图：邮局问题：Voronoi图是计算几何中的重要工具，本章介绍了其定义、基本性质，以及如何构建Voronoi图，还深入到线段集Voronoi图和最远点Voronoi图的特殊应用场景。 8. 排列与对偶：光线跟踪超采样：章节讨论了排列和对偶变换的概念，特别是在光线跟踪和图像处理中的应用，包括差异值计算、直线排列和层阶与偏差分析。 9. Delaunay三角剖分：高度：Delaunay三角剖分在几何建模和科学计算中有重要用途，本章将深入探讨它的构建方法和特性。 这些章节详细阐述了计算几何的关键算法，提供了丰富的习题以加深读者的理解，是学习和研究计算几何的宝贵资源。对于计算机科学、图形学、工程学等领域的学生和专业人士来说，这是一本不可或缺的参考书。