改进的Delaunay三角网构建算法研究

"这篇论文主要探讨了带约束的Delaunay三角网快速构建算法，作者为孔川和罗大庸，他们来自中南大学计算机系。该研究关注于如何在存在约束线的情况下，有效地构建Delaunay三角网，以满足实际应用需求，特别是地形建模领域。" 在构建不规则三角网（TIN）时，Delaunay三角网因其独特的几何特性，如空外接圆性质和最小内角最大化，被广泛应用。然而，在处理实际地形数据时，往往需要考虑地形特征线（如山脊线、山谷线）作为约束条件。为此，孔川和罗大庸针对传统的逐点插入算法和插入约束线算法进行了改进，以提高构建TIN的速度。 文中提出了一种新的约束线插入算法，采用"先统一后分解"的策略，这有助于快速高效地嵌入地形线并减少影响域的重建时间。该算法不仅执行效率高，而且设计思路清晰，易于实现，对于处理大规模的地形数据尤其有优势。 Delaunay三角网的定义包括两个关键性质：一是每个三角形的外接圆不包含除了其顶点之外的任何点；二是相同点集中的所有三角形，Delaunay三角网中的最小内角最大。基于这些性质，研究人员提出了改进的逐点插入法，通过对数据点到集合重心距离的计算，选择合适的起始三角形，优化插入过程，从而提升算法的效率。 传统逐点插入法虽然易于理解和实现，但由于其时间性能相对较低，因此需要优化。通过上述改进，论文旨在提供一种更适应实际地形约束的Delaunay三角网构建方法，这对于地理信息系统（GIS）、土地测绘、城市规划等领域的应用具有重要意义。 总结来说，这篇论文的核心贡献是提出了一个针对带约束条件的Delaunay三角网的快速构建算法，通过优化现有算法，提升了处理速度，尤其是在处理包含地形特征线的数据时。这一工作为不规则三角网的高效构建提供了新的理论和技术支持。