A FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS

A fast algorithm for generating constrained two-dimensional Delaunay t riangulations is described. The scheme permits certain edges to be spe cified in the final triangulation, such as those that correspond to do main boundaries or natural interfaces, and is suitable for mesh genera tion and contour plotting applications. Detailed timing statistics ind icate that its CPU time requirement is roughly proportional to the num ber of points in the data set. Subject to the conditions imposed by th e edge constraints, the Delaunay scheme automatically avoids the forma tion of long thin triangles and thus gives high quality grids. A major advantage of the method is that it does not require extra points to b e added to the data set in order to ensure that the specified edges ar e present.