Delaunay三角网格的一种快速生成法

１．引 言 在计算流体力学中，采用非结构网格有许多优点，如易于生成复杂区域的网格和作网格自适应．最常见的非结构网格是非结构三角网格，而生成非结构三角网格的方法主要有前沿推进法［１－４］和 Ｄｅｌａｕｎａｙ三角剖分法［５－８］两大类．本文仅考虑后者并只讨论生成给定点集的 Ｄｅｌａｕｎａｙ三角网格． 目前流行的生成Ｄｅｌａｕｎａｙ三角网格的算法是Ｂｏｗｙｅｒ－Ｗａｔｓｏｎ算法［６，７］．Ｂｏｗｙｅｒ－Ｗａｓｏｎ算法是以逐点加入的方式进行的，如何提高该算法的运算效率是一个十分重要的问题［８－１３］．用 Ｂｏ…

A Fast Algorithm for Generating Delaunay Triangulation

Delaunay triangulation has been widely used in many fields such as compu- tational fluid dynamics, statistics, meteorology solid state physics, computational geometry and so on. Bowyer-Watson algorithm is a very popular one for generating Delaunay triangulation. In generating the Delaunay triangulation of a preassigned set of n points, the complexity of Bowyer-Watson algorithm can at most be reduced to O(n log n) for the simple reason that the complexity of its tree search process is O(nlog n). In this paper we suggest a tree search technique whose complexity is O(n). Noting that the order of point insertion can affect the efficiency of Bowyer- Watson algorithm, we propose a technique to optimize the point insertion process. Based on these two techniques, we obtain a fast algorithm for generating Delaunay triangulation.