计算几何算法详解与应用实例

《计算几何算法与应用(中文版)》是一本专为IT专业人士设计的书籍，它深入探讨了计算几何领域的核心概念和技术，旨在帮助读者理解和掌握这一领域在实际应用中的关键算法。该书由Mark de Berg、Marc van Kreveld、Mark Overmars和Otfried Schwarzkopf四位作者撰写，邓俊辉翻译，清华大学出版社出版。 本书共分为九个章节，每个章节都围绕一个特定的主题展开： 1. **计算几何导论**：介绍了凸包的概念，以及如何通过实例展示其重要性。同时，讨论了算法的退化性和鲁棒性，强调了处理复杂几何问题时需要考虑的问题。书中还列举了计算几何在诸如计算机图形学、地理信息系统等领域的应用，并提供了相关注释和习题供读者巩固理解。 2. **线段求交与专题图叠合**：详细阐述了线段之间的相交问题及其解决方法，涉及双向链接边表和子区域划分的叠合技术，以及布尔运算在图形操作中的应用。 3. **多边形三角剖分**：重点讲解了多边形的覆盖与三角分解，包括单调块划分和针对单调多边形的三角剖分，这在图形渲染和几何优化中至关重要。 4. **线性规划**：探讨了线性规划在制造业中的具体应用，如铸造过程中的几何建模，以及半平面求交、递增式线性规划和随机线性规划等算法。 5. **正交区域查找**：针对数据库查询场景，介绍了从一维到高维的区域查找算法，如kd-树和区域树，以及如何处理一般性点集和分散层叠问题。 6. **点定位**：讲述了如何确定点的位置，包括点定位算法和梯形图的应用，以及特殊情况下退化情况的处理和优化技术。 7. **Voronoi图与邮局问题**：介绍Voronoi图的基本概念，构造方法以及在邮政系统中的应用，同时提供相关习题供读者实践。 8. **排列与对偶：光线跟踪超采样**：涉及图像处理中的光线追踪，讲解了差异值计算、对偶变换和排列算法，以及层阶与偏差控制等内容。 9. **Delaunay三角剖分与高度插值**：深入研究了如何通过Delaunay三角剖分进行平面点集的几何分析，这对于地形建模和数据可视化具有重要意义。 整体而言，《计算几何算法与应用(中文版)》涵盖了从基础理论到实用技巧的广泛内容，适合于学生、研究人员和工程师们作为参考书，以便在计算几何的各个层面提升技能和解决问题的能力。尽管书中存在少量错误，但整体翻译质量较高，对于想要深入学习计算几何的读者来说是一本不可多得的资源。