nag_2d_triangulate (e01eac) creates a Thiessen triangulation with a given set of twodimensional data points as nodes. This triangulation will be as equiangular as possible (
Cline and Renka (1984)). See
Renka and Cline (1984) for more detailed information on the algorithm, a development of that by
Lawson (1977). The code is derived from
Renka (1984).
The computed triangulation is returned in a form suitable for passing to
nag_2d_triang_bary_eval (e01ebc) which, for a set of nodal function values, computes interpolated values at a set of points.
Cline A K and Renka R L (1984) A storageefficient method for construction of a Thiessen triangulation Rocky Mountain J. Math. 14 119–139
Renka R L (1984) Algorithm 624: triangulation and interpolation of arbitrarily distributed points in the plane ACM Trans. Math. Software 10 440–442
Not applicable.
The time taken for a call of
nag_2d_triangulate (e01eac) is approximately proportional to the number of data points,
$n$. The function is more efficient if, before entry, the
$\left(x,y\right)$ pairs are arranged in
x and
y such that the
$x$ values are in ascending order.
The triangulation is encoded in
triang as follows:
 set ${j}_{0}=0$; for each node, $k=1,2,\dots ,n$, (using the ordering inferred from x and y)

${i}_{k}={j}_{k1}+1$

${j}_{k}={\mathbf{triang}}\left[6\times {\mathbf{n}}+k1\right]$
 ${\mathbf{triang}}\left[\mathit{j}1\right]$, for $\mathit{j}={i}_{k},\dots ,{\mathit{j}}_{k}$, contains the list of nodes to which node $k$ is connected. If ${\mathbf{triang}}\left[{j}_{k}1\right]=0$ then node $k$ is on the boundary of the mesh.
In this example,
nag_2d_triangulate (e01eac) creates a triangulation from a set of data points.
nag_2d_triang_bary_eval (e01ebc) then evaluates the interpolant at a sample of points using this triangulation. Note that this example is not typical of a realistic problem: the number of data points would normally be larger, so that interpolants can be more accurately evaluated at the fine triangulated grid.