Fortune算法：高效构建Voronoi图

"陶文全的《计算流体力学与传热学》讲解了Voronoi图的构造方法，特别是通过平面扫描算法（Fortune算法）实现O(nlogn)的时间复杂度。此书深入探讨了计算几何领域的算法与应用，涉及线段求交、多边形三角剖分、线性规划、正交区域查找和点定位等多个主题。" Voronoi图是一种几何构造，用于描述给定点集中的每个点周围的空间区域，其中该点是最近的点。在描述中提到，传统的构造方法基于第4章的算法，需要O(nlogn)时间，但Fortune算法利用平面扫描技术将时间复杂度降低到同样级别，同时保持线性空间复杂度。平面扫描算法的核心是一个自上而下的扫描线，它在扫描过程中处理事件点，这些事件点是扫描线与Voronoi图边界相交的地方。扫描线的移动只在特定事件点时更新所需信息。 在Voronoi图的构建中，关键在于理解当扫描线经过Voronoi单元的高顶点时，需要考虑上方和下方的基点来确定顶点。为此，算法需要维护与扫描线上方基点对应的局部Voronoi图，这部分不受扫描线下方基点的影响。图7-9展示了扫描线及其上方不再变化的部分，即l+，对于l+上的点，可以确定它们最近的基点。 书中还涵盖了其他计算几何主题，如线段求交、多边形三角剖分（用于例如画廊看守问题）、线性规划（在铸模制造等场景中的应用），以及正交区域查找（关联于数据库查询）和点定位问题。每个主题都有详细的技术讲解、算法实现和习题，旨在帮助读者深入理解和应用这些概念。 此外，书中还讨论了排列与对偶的概念，这对光线追踪和超采样等图形学问题至关重要。排列涉及到直线的组织和对偶变换，它们在解决计算几何中的难题时扮演着重要角色。 总结来说，《计算流体力学与传热学》通过陶文全的解释，提供了计算几何领域内多个核心算法的深入分析，对于理解并应用这些算法解决实际问题具有很高的价值。