Next: Delaunay Triangulation Up: Advancing Front Triangulation Previous: New point insertion

Determination of the trial point

The edge of the initial front closest to the mid-point P of the base edge is found. A normal is drawn through the mid-point of that edge and the closest edge of the initial front that it intersects is determined (Figure 3.4).

**Figure 3.4:** Direct graded triangulation
$\begin{figure} \centerline{ \psfig {figure=figures/direct_gradation.eps,angle=-90,height=7cm,width=10cm} }\end{figure}$

If the distance of point P from mid-point of both the edges is D₁ and D₂ respectively and if L₁ and L₂ are the respective edge lengths then the required length of the new edges is calculated as

$\begin{displaymath} L = \frac{D_1 L_2 + D_2 L_1}{D_1+D_2} \end{displaymath}$

Triangulation using this method for selection of trial point is termed as direct graded triangulation which is implemented here in IITZeus (Figure 3.5). This algorithm requires many calculations and hence slows down the triangulation slightly. [Sha96]

**Figure 3.5:** Advancing front triangulation - an example
$\begin{figure} \centerline{ \psfig {figure=advfrnt/iitzeus.ps,angle=-90,height=9cm,width=10cm} }\end{figure}$

Anirudh Modi
1/16/1998