Page 210 - Basic Structured Grid Generation

Unstructured grid generation 199

P
E N A C
Q
B
D
Fig. 8.12 Constructing new points in a doubly-connected region.

circumcentre X we can then define the parameter α = R/f (X). New grid-points may
now be inserted at triangles having the largest value of α. After a number of iterations
it should be possible to arrive at a grid in which the maximum value of α for any
triangle is less than or equal to unity, which means that all triangles have reached their
target size.

Voronoi-segment point insertion method
An alternative point insertion strategy, as proposed by Rebay, is to place a new point
along a segment of a Voronoi polygon inside a triangle instead of at its circumcentre.
The locations at which new points are inserted in the circumcentre approach described
above are fixed (at the circumcentres of the chosen triangle), and the required size
of the grid cells (triangles) is achieved after a number of iterations. In the Voronoi-
segment approach, however, one can in principle aim to produce grid cells of the final
specified size as soon as the procedure is invoked.
For any given Delaunay triangulation of the domain, the triangles are divided into
external triangles, which have at least one side consisting of a boundary segment, and
internal triangles, which do not. (An initial triangulation based on boundary points
would consist of external triangles only.) The internal triangles are divided into so-
called accepted and non-accepted triangles, accepted triangles being those defined as
having circumradius less than 1.5 times the user-specified target value given by local
values of the function f(X) discussed in the previous section. The remaining triangles
are non-accepted.
The algorithm starts by considering non-accepted triangles which have an edge in
common with an accepted triangle and choosing the one with largest circumradius.
Figure 8.13 shows a typical situation, in which the triangle ABD is non-accepted, with
circumradius R ABD , and ABC an accepted triangle. The common edge AB is called
an active edge. The Voronoi segment for the two triangles is the line EF connecting
the circumcentres E and F, which is the perpendicular bisector of AB, the point of
intersection being M. The idea now is to choose a new point X somewhere on the
segment EF such that the triangle ABD will be replaced by an accepted triangle ABX,
with a new Delaunay triangulation. The local target circumradius may be taken as the
value of f(X) at M, which we denote by f M .