Page 300 - Computational Fluid Dynamics for Engineers

290 9. Grid Generation

(a) (b)
Fig. 9.18. Example of Delaunay criterion; (a) satisfies the criterion while (b) does not.

regions Vi, defined as the set of points that are closer to a point Pi than to any-
other point [8]. Figure 9.17 illustrates that in two dimensions, the sides of the
Voronoi polygon around point P is made of segments of the bisectors of lines
joining P to all its neighboring points. If all pairs of points that have a segment
of a Voronoi polygon in common are joined by straight lines, the result is a
triangulation within the convex hull of the set of points known as the Delaunay
triangulation T(Pi) [9]. In three dimensions, the territorial boundaries are faces
that form Voronoi polyhedra and are equidistant between point pairs. If points
with a common face are connected, then a set of tetrahedra is formed that covers
the convex hull of points.
One interesting property of the Delaunay triangulation is the in-circle cri-
terion. The circumcircle of a triangle is the circle passing through the three
vertices of the triangle. It can be seen that each vertex of a Voronoi diagram is
the circumcenter of the triangle formed by three points. The in-circle criterion
states that the circumcircle through each triangle of a Delaunay triangulation
contains no points other than its forming points (Fig. 9.18). This applies to any
number of dimensions and is the property used to construct algorithms for the
triangulation.

Bowyer-Watson Algorithm

There are several algorithms used to construct the Delaunay triangulation. One
approach, which is flexible in that it readily applies to two and three dimensions,
is due to Bowyer and Watson and is explained by Baker in Reference [10]. It
is an incremental algorithm that exploits the circle criterion of the Delaunay
triangulation a follows.
Consider T n , the Delaunay triangulation of a set of n points, V n = {Pi | i =
1 to n}. For any simplex S belonging to T n , let R s be the radius and Q the center
of the circumcircle. Now introduce a new point P n +i inside the convex hull of
and define B = {S \ S G T n , (P n +i, Q) < R s} where d{P 1 Q) is the distance
d
V n
between points P and Q. B is not empty, since P n +i is inside the convex hull of
and therefore inside some simplex S' belonging to T n. It follows that S' G B.
V n