Page 232 - Basic Structured Grid Generation

Unstructured grid generation 221

numerical scheme must be used to solve the global matrix equation for the unknown
coefficients φ i .
Similar procedures can be used to solve non-linear hosted equations, such as
the Navier-Stokes equations, using iterative methods based on an initial approxi-
mate solution. For example, see Rao, S.S. (1982) and Lewis, Morgan, Thomas, and
Seetharamu (1996).

8.5 Website programs

8.5.1 Subdirectory: book/Delaunay

This subdirectory contains two files, called Delaunay1.f and Delaunay2.f. The codes
involved are rather lengthy, and we do not give every detail here. However, they are
annotated to make them easier to follow.

1. Delaunay1.f
The ‘main’ routine contained in Delaunay1.f was written by S.W. Sloan
(Sloan (1987)). This is a small program, described as ‘A fast algorithm for con-
structing Delaunay triangulation in the plane’. It triangulates domains starting from
sets of boundary data, and generally produces completely unacceptable triangula-
tions. For domains with an internal boundary, such as the region around an airfoil,
not only is the quality of the triangles in the domain unacceptable, but the inner
circular region is also filled with unacceptable triangles. To make the grid accept-
able, (a) the unwanted triangles must be removed from the inner region, and (b) the
remaining triangles must be processed so that the final triangulation does not contain
triangles that are excessively large or skinny.
Delaunay1.f contains a subroutine called ‘Add-point’ which carries out the lengthy
process of refining the initial triangulation. The first task is the removal of unwanted
triangles from within any inner boundaries, and this is followed by the re-numbering
of the remaining triangles. Then the processing of these triangles is carried out.
The criteria used in this processing are those based on area and on aspect ratio,
as discussed in Section 8.2.3. Target values for area and aspect ratio, called here
‘amax’ and ‘armax’ respectively, are specified by the user.
All the triangles go through the ‘Add-point’ subroutine one at a time. From the
cartesian co-ordinates of the vertices of a triangle the lengths of the sides can be
calculated, and then eqns (8.1) and (8.5) permit the calculation of area and aspect
ratio. If either of these is greater than ‘amax’ or ‘armax’ respectively, then the
triangle qualifies for processing. (Otherwise we proceed to the next triangle for
consideration.)
If a triangle qualifies for processing, it is classified by the program according to
whether one of its sides is parallel to the x-axis (in which case it is called ‘horizon-
tal’), perpendicular to the x-axis (when it is called ‘vertical’), or neither of these
possible cases (when it is called ‘general’). Furthermore, given that in the initial
triangulation the vertices of a triangle are organized in an anti-clockwise manner,
and labelling them here as 1, 2, 3, we can label side 1-2 as side 1, side 2-3 as side 2,
and side 3-1 as side 3. This gives three further categories for classification. Finally