Computer Aided Engineering Design

374 COMPUTER AIDED ENGINEERING DESIGN

here. The algorithm starts by forming a super-triangle that encompasses all the given (boundary)
points of the domain. Initially, the super-triangle is flagged as incomplete and the algorithm proceeds
by incrementally inserting new points^1 in the existing triangulation. A search is made for all triangles
whose circumcircles contain the new point. Such triangles are deleted to give an insertion polygon
and a new set of triangles is formed locally with the inserted point. This process is continued until
point insertion is accomplished and thereafter all triangles having the vertices of the super-triangle
are deleted. Figures A1.6 depict the implementation of the Watson’s algorithm.

Figure A1.6 Watson’s algorithm: intermediate steps of point insertion, local deletion of triangles to

form the insertion polygon and new local triangulation

In three dimensions, a super tetrahedron may initially be formed to encompass all boundary nodes.
At an intermediate step, a point may be generated in space and checked whether it lies within the
circumspheres of the existing tetrahedra. Such tetrahedra may be deleted to result in an insertion
polyhedron within which new tetrahedral elements may be formed.

A1.2.4 Quadtree Approach
For a two dimensional domain approximated using polygonal discretization, a quadtree grid is
constructed as shown in Figure A1.7 (a) in the following manner.

1. A square cell of minimum size is formed to contain all contour points


2. The quadtree approach consists of cell splitting involving each cell (parent) to be divided into four
   (children) cells (Section 9.6.1).

(^1) Point insertion itself may be iterative to ensure that the resultant triangles formed are almost regular.
(a) Intermediate triangulation (b) Point insertion (c) Triangles identified to be deleted
(d) Insertion polygon (e) New triangulation