计算几何：三角剖分与流体力学中的难题探讨

《计算流体力学与传热学》由陶文全编写，是一部深入探讨计算机科学中计算几何、算法及其在传热学领域的具体应用的专业书籍。该书主要聚焦于几个关键主题： 1. **计算几何**：这一章介绍凸包的概念，即一个集合中所有点构成的最小边界，以及如何处理可能出现的退化情况（如多边形边缘相切）以保证算法的鲁棒性。计算几何的应用领域广泛，包括图形学、地理信息系统等。 2. **线段求交与区域划分**：章节涉及如何处理线段之间的交点问题，通过双向链接边表实现高效处理，并讨论了如何通过叠合算法进行子区域划分，如用于布尔运算（如形状组合或减法）。 3. **多边形三角剖分**：这部分探讨了如何将一个多边形划分为三角形，这对于三维图形渲染和地形建模至关重要，特别是通过单调块划分和针对单调多边形的三角化算法。 4. **线性规划**：介绍了线性规划的基本原理，如在铸模制造中的几何应用，半平面求交、递增式和随机线性规划问题，以及在高维空间中的扩展方法。 5. **正交区域查找**：着重于数据库查询中的数据结构，如一维、kd-树、区域树以及在高维空间中的搜索策略，如分散层叠。 6. **点定位算法**：探讨如何在复杂环境中定位点，涉及到梯形图和随机增量式算法，同时考虑了处理特殊情况的方法。 7. **Voronoi图**：介绍Voronoi图的基本概念，如邮局问题中的应用，以及如何构建和分析不同类型的Voronoi图。 8. **排列与对偶**：这一部分讲解光线跟踪中的超采样技术，涉及差异值计算、对偶变换以及如何优化光线在场景中的传播路径。 9. **Delaunay三角网**：最后提到Delaunay三角网，这是一种重要的几何数据结构，常用于地理信息系统、图像处理和计算机视觉等领域，以确保数据分布的均匀性和稳定性。 这本书旨在提供计算几何和基础算法的理论背景，并通过实际问题展示其在流体力学与传热学中的实用价值，适合对这些主题有深入研究需求的读者。