优化Bowyer-Watson算法：快速非结构三角网格生成与加点顺序优化

本文主要探讨了一种针对Delaunay三角网格的快速生成方法，特别是在分析和改进Bowyer-Watson算法的基础上。Bowyer-Watson算法是一种常用的生成三角网格的算法，它通过逐点加入的方式构建网格，但其运算效率受到两个关键因素的影响：一是树搜索过程中的复杂度，二是加点顺序对算法性能的影响。 首先，作者分析了影响算法效率的两个核心问题：传统的Bowyer-Watson算法在树搜索过程中，其运算量最多只能达到线性时间复杂度O(n)，这在处理大规模数据集时显得效率较低。为解决这一问题，作者提出了一个新的阶树搜索方法，这种方法利用加点过程中的已知信息，简化了搜索步骤，并强调其编程实现的便捷性。 其次，文章指出，尽管加点顺序理论上不会影响最终的网格形状，但在实际操作中，不同的加点顺序会导致算法运行速度的显著差异。通过对特定实例的深入分析，作者揭示了加点顺序对Bowyer-Watson算法效率影响的本质，表明合理的加点顺序优化至关重要。 为优化加点过程，文章提出了“相邻排列、分级加入”的预处理方案，这是一种将节点按照特定顺序加入的策略，它优先处理边界节点，然后按照层次结构逐步加入内部节点。这种策略有效地减少了搜索空间，从而大幅度提升了算法的运算效率。 最后，尽管Bowyer-Watson算法本身受限于需要预先指定节点，限制了其应用范围，但通过不断改进，已经衍生出一系列基于该算法的新方法，它们扩展了算法的适用性，使其能够更方便地生成复杂区域的网格并实现网格的自适应性。这些新算法在加点过程中普遍采用边界节点优先的策略，进一步优化了整体性能。 本文的关键贡献在于提出了一种新的阶树搜索方法和优化加点顺序的策略，旨在提升Delaunay三角网格生成的效率，使之在计算流体力学等领域的非结构网格生成中发挥更大的作用。