Page 301 - Computational Fluid Dynamics for Engineers

9.7 Unstructured Grids 291

The region C formed when B is removed from T is simply connected, contains
Pn+i (since P n +i is inside S f G B), and the new point P n +i is visible from all
points on the boundary of C. It is therefore possible to generate a triangulation
of the set of points V^+i = V n U P n +i} by connecting P n+i to all points on
{
the boundary of C. This triangulation is precisely the Delaunay triangulation
Tn+l-
The implementation of the Bowyer-Watson algorithm in two dimensions
starts with a super-triangle, or super-square partitioned into five triangles,
which contains all the other points. The remaining points, which comprise the
grid to be triangulated, are introduced one at a time and the Bowyer-Watson
algorithm is applied to create the Delaunay triangulation after each point in-
sertion. Two lists are maintained for each triangle in the existing structure: one
with the forming points of the triangle, the other with the addresses of the
neighboring triangles that have a common edge. The second list, which pro-
vides information about the contiguities between triangles, allows all triangles
belonging to a cavity to be found by means of a tree search, once one such tri-
angle has been found. Without the contiguity information the algorithm would
be extremely inefficient. It is also customary to store the radius and the coordi-
nates of the center of the circumcircle for each triangle. The remaining step in
the Bowyer-Watson algorithm is the updating of the data structure. Triangles
belonging to the set B are deleted from the lists, and new triangles, obtained by
connecting the new point to all edges of the cavity boundary, are added. Finally,
it is necessary to determine the contiguities that exist among the new triangles,
and also between the new triangle and the old triangles that have edges on the
cavity boundary.
Consider the problem of generating a boundary conforming grid within a
multiply connected domain defined between two concentric ellipses. The ellipses
are defined by a set of discrete points. Following the Bowyer-Watson algorithm,
these points can be contained within an appropriate hull and then connected
together. The result is shown in Fig. 9.19a. A set of valid triangles has been
derived that covers the region of the hull. Two issues can be raised immediately.
First, to derive a triangulation in the specified region, triangles outside this
region must be deleted. Second, in order for the triangles to provide a boundary
conforming grid it is necessary that edges in the Delaunay triangulation form
the given geometrical boundaries of the domain. Unfortunately, given a set
of points that define pre-specified boundaries there is no guarantee that the
resulting Delaunay triangulation will contain the edges defining the domain
boundaries. It is necessary, therefore, to check the integrity of boundaries, and
if found not to be complete, appropriate steps must be taken.
A combination of edge swapping can be used to recover boundary edges in
two dimensions. Once the boundary is complete, it is a simple task to delete
triangles exterior to the region of interest. Deletion of unwanted triangles in