Interpolation: Triangulation

The triangulation method uses Renka's algorithm (Renka, 1984) to carry out a Delaunay triangulation (Okabe et al., 1992) of the observation points. The purpose is to identify a neighborhood of nearby observation points to be used in the interpolation.

Two options are available to perform the interpolation. The simplest method is a linear interpolation of the vertices of the triangulation. In this case, the barycentric coordinates of the point are used to take a weighted average of the three observation values (associated with the three vertices of the triangle). The resulting interpolation function is continuous, but not differentiable across an edge.

The second triangulation method uses a polynomial fit within each triangle in the triangulation (Renka, 1984). This method involves an intermediate step of fitting a cubic spline on each edge of the triangulation. The interior values are taken as weighted averages of the edge values, based upon the barycentric coordinates of a point. In the intermediate step of fitting the spline, approximations to the gradient at each point must be computed. The user has the option to specify which of two gradient estimation methods is to be used. The local method uses only a few neighboring points, while the global method uses all points. The latter method may not be possible if the number of points is larger than a few hundred.


References

Brown, J. L. (1994), Natural neighbor interpolation on the sphere, in Wavelets, Images, and Surface Fitting, P.-J. Laurent, A. Le Mehaute, and L. L. Schumaker eds., A K Peters, Wellesley, MA, 67-74.

Okabe, A., B. Boots, and K. Sugihara (1992) Spatial Tessellations, Wiley, 532 pp.

Renka, R. J. (1984), Interpolation of data on the surface of a sphere, ACM Transactions on Mathematical Software, 10, 417-436.

Watson, D. F. (1992) Contouring: A Guide to the Analysis and Display of Spatial Data, Pergamon Press, 321 pp.