An algorithm for automatic Delaunay triangulation of arbitrary planar domains

In this paper an algorithm for automatic Delaunay triangulation of arbitrary planar domains is presented. A new method in which a Delaunay triangle is constructed by computing the angles of points with respect to a baseline in a region instead of checking the empty circumcircle is proposed. The algorithm is based on a working boundary, which starts from the original boundary and moves dynamically to the centre of the planar domains. An edge on the working boundary is taken as a baseline, a third point is then searched for forming a Delaunay-satisfying triangle. The triangulation is finished when the working boundary is empty. The algorithm is numerically stable, sufficiently robust to handle irregular regions and simple to implement. Several examples and applications are included to demonstrate the validity of the algorithm as well as its effectiveness. Copyright (C) 1996 Civil-Comp Limited and Elsevier Science Limited