平面点集最优三角剖分：理论与应用详解

本章节讨论的主题是平面点集的三角剖分在计算流体力学与传热学中的应用，特别是在Delaunay三角剖分中的高度插值。Delaunay三角剖分是一种重要的几何结构，它通过将给定的点集划分为一系列三角形，使得任何不在该剖分中的点到最近三角形的顶点的距离都小于或等于到其他顶点的距离，从而确保了插值精度。 首先，作者强调了一个关键的概念——极大平面子区域划分，即一个点集中，不能添加新边而不破坏平面性（即新边会与现有边相交）的划分。三角剖分便定义为这些点集的极大平面子区域划分，每个面除边界外都是由三个顶点构成的三角形。对于无限大的面，它们可以通过连接点集凸包边界上的点来确定，确保了三角形组合能够覆盖整个定义域。 图9-6展示了同一点集的不同三角剖分中，三角形数量和边数保持恒定，这个数量取决于点集的规模和凸包的大小。定理指出，三角剖分中的三角形数和边数等于凸包边界上的点数，包括那些位于边界内部的点。 此外，章节还涉及到了与三角剖分相关的计算几何算法，例如线段求交、多边形三角剖分（如单调块划分和单调多边形的三角化）、线性规划、正交区域查找以及点定位等技术。这些算法在实际应用中扮演着重要角色，比如在数据库查询、模具制造中的几何优化、光线跟踪的超采样以及点定位系统的设计等。 Delaunay三角剖分，作为核心概念，是本章的核心内容。它不仅用于计算几何，还在图形学、地理信息系统、计算机辅助设计等领域有着广泛的应用。理解Delaunay三角剖分的关键在于掌握其构造原理和优化方法，以及如何通过算法实现高效的三角化过程，这对于保证插值精度和性能至关重要。 本节内容深入浅出地介绍了平面点集三角剖分的基本概念、理论以及在实际问题中的应用，对于从事相关领域的研究人员和工程师来说，是理解和运用计算几何算法的基础。