Page 207 - Basic Structured Grid Generation

196 Basic Structured Grid Generation

x 4
x 5
x 3

x 1
x 2

x 6

Fig. 8.10 New point lying outside triangulation and outside all circumcircles.

8.2.3 Point insertion strategies

The initial Delaunay triangulation of a two-dimensional domain, based on a selection
of boundary points together with the application of the Bowyer-Watson algorithm, can
often yield an unsatisfactory grid. Improvement of the grid must then be sought by
inserting new points into the domain, and the resulting triangulations will be judged
according to various geometric and physical criteria. The geometric criteria will nor-
mally be that the triangulation (grid) should be smooth and that the triangles (grid-cells)
should be of uniform shape and size. The physical criterion will be that of adaptivity,
which normally requires the grid-point density in the solution domain to vary so that
areas of sharp variation in the solution of the hosted partial differential equations have
greater grid-point density (and areas of low variation smaller grid-point density).
In Delaunay triangulation (in two dimensions) there are two main approaches to the
insertion of new points. The first Shenton and Cendes (1985) and Holmes and Snyder
(1988) is to place new interior points at the circumcentres of the triangles in an existing
triangulation. The second is known as Voronoi-segment point insertion Rebay (1993),
according to which new points are placed along so-called Voronoi segments.
One difficulty associated with Delaunay triangulation is that, since a given set of
data points has a unique Delaunay triangulation, there is no guarantee that edges
connecting boundary points will be preserved. In other words, the triangulation may not
be boundary-conforming. It is possible to carry out a check on a triangulation to detect
all possible missing boundary edges, and, by inserting new nodes at the mid-points of
missing boundary edges, boundary-conforming triangulations can be produced.
Point insertion at triangle circumcentres
New points to be inserted should not be too close to existing grid nodes. Insertion at
the circumcentre of an existing triangle at least results in the point being equidistant
from the three vertices. This strategy thus involves insertion of a new point at the
circumcentre of a triangle, followed by re-triangulation of the whole domain. The only
remaining decisions to be made are which triangles to select for the insertion of new
points. The plan here is to devise a set of rules for identifying ‘unsuitable’ triangles
in the existing triangulation. These will be referred to as forming triangles. Points will