Page 204 - Basic Structured Grid Generation

Unstructured grid generation 193

sum of the angles BAD and BCD, which is greater than 180 degrees). This gives a
simple method for checking if the way in which four data points are connected to form
two triangles is Delaunay or not.

8.2.2 The Bowyer-Watson algorithm

Among various methods for implementing Delaunay triangulation by means of a
sequence of local operations, the Bowyer-Watson algorithm, due to Bowyer (1981)
and Watson (1981), has been found to be very convenient and efficient. We suppose
that there already exists a set of data points with a Delaunay triangulation, and seek to
incorporate further points, one at a time. To initiate the iterative procedure, we could
start if necessary with a sufficiently large equilateral triangle, large enough to contain
all the data points to be triangulated, using the three vertices as the initial points.
When all data points have been incorporated and triangulated, triangles containing the
original three points of the equilateral triangle could then be removed. A sufficiently
large square (divided by a diagonal into two triangles), with four initial vertices, could
also be used.
Suppose the existing Delaunay triangulation contains i data points x 1 , x 2 ,..., x i ,
where the xs represent position vectors. Let the union of the triangles in the triangula-
tion be T i and the union of all the circumcircles of the triangles be B i . We now wish
to insert a new point x i+1 into the triangulation. There are three main possibilities:

1. x i+1 ∈ T i ;
2. x i+1 /∈ T i and x i+1 ∈ B i ;
3. x i+1 /∈ B i .

In case 1, the new point lies in one of the triangles of T i . It is necessary to determine
the set S which is the union of those triangles belonging to T i whose circumcircles
contain the new point. The next step of the algorithm is to remove the internal edges
of the triangles composing S, thus creating a ‘hole’ within the triangulation. Finally,
a new set of edges is obtained by connecting the new point to each vertex of S.This
process always produces a new Delaunay triangulation T i+1 .
Figure 8.5 shows an example of a Delaunay triangulation with five points
x 1 , x 2 ,..., x 5 , with a new point x 6 lying in one triangle and also within two cir-
cumcircles. In this case S is the quadrilateral with vertices x 2 , x 3 , x 4 , x 5 . The only
internal edge in S is that connecting x 2 and x 4 . Removing this creates a hole in the

x 5 x 4
x 1
x 3
x 6
x 2

Fig. 8.5 Delaunay triangulation and new point X 6 .