Watson

The Watson algorithm is part of the Estimate Scattered Data option in the Non-Parametric menu. It is also offered in the Interpolate Uniform Grid option.

Author

David Watson
P.O. Box 734
Claremont, WA 6010
Australia
E-mail: watson@iinet.com.au
Web page: http://members.iinet.net.au/~watson/nngridr.html

References

"nngridr: An Implementation of Natural Neighbor Interpolation", David Watson, P.O. Box 734, Claremont, WA 6010, Australia, 1994, 170 page book available directly from author.

Description

The natural neighbor algorithm uses a circular areal-based procedure for interpolation. Unlike Delaunay triangles where there may be more than one way to assign the triangles to the data, natural neighbor circles form a unique arrangement. The basic algorithm (with zero tension) is best thought of as a taut rubber sheet connecting all of the points. In this instance, the interpolant is C1 everywhere except at the data nodes where discontinuities exist. A C1 (once continuously differentiable) interpolant will occur when a tension value of one or greater is set. In this instance, gradient information is used to blend out the discontinuity at the nodes. The interpolant is planar and utilizes a linear weighted average of the natural neighbor function values. The C0 interpolant and lower tensions of the C1 interpolant may be of value in the accurate integration of topographical data.

Revisions to Algorithm

The data are automatically scaled to a unit cube. Tensions of 1 through 5 automatically set the tautness factors in the algorithm to (3,9), (2,4), (1.5,2.25), (1.25,1.5625), and (1,1). The data perturbation introduced to insure the uniqueness of natural neighbor circles has been decreased in magnitude to reproduce the precision of input values to 7-8 digits.

Interpolation

The natural neighbor relationships of data are specified by the shared natural neighbor circles. The Watson algorithm uses a simple weighted average of the z values of the natural neighbors of the interpolation point. This type of linear interpolation in natural neighbor coordinates is the equivalent of planar interpolation in rectangular coordinates. No gradient information is used for the non-tension interpolant. For the tension interpolant, natural neighbor gradients are computed using the natural neighbors of a data point, but not the data point itself. A compound exponential blending function is used to add the influence of the gradients and render the interpolant C1 at the nodes. The blending function does not use the tension directly, modifying it in accord with an outlier or roughness index. For data fitted well by smooth functions, the highest tension setting is likely to produce the greatest accuracy.

Extrapolation

The algorithm uses a large triangle which encompasses the whole of the data. Artificial data are created at these vertices by least-squares fitting of a plane to the entirety of the data. Extrapolation is then accomplished using these vertices. This is a highly conservative form of extrapolation that is not likely to be at all accurate, although the wild fluctuations that often occur within extrapolation are avoided.

Estimated Partial Derivatives

The five partial derivatives available within TableCurve 3D are computed using numeric derivatives. These should be regarded as having questionable accuracy.

Estimated Volumes

The primary method is to interpolate a uniform grid of 10,000 points and to evaluate the double integral using a bicubic B-spline integration procedure. The error reported in the Evaluation procedure will be the fractional difference with a similar 2,500 node integration. A repeat evaluation with the same limits will use an actual double integration procedure using the actual interpolant. A very fast double Gaussian quadrature procedure is first attempted to 1E-5 precision. If this is unsuccessful, a double adaptive quadrature procedure is then used.

Considerations

This algorithm has one of the most sophisticated neighbor selection procedures available, and yet one of the weakest interpolants. Accuracy tests suggest that this procedure is likely to be the least accurate of the algorithms. The selection of neighbors is fully automatic (no neighbor counts or radii are specified). The uniqueness of the neighbor circles, however, is a property of an artificial perturbation of input data and as such, for data on a regular grid, neighbors are partitioned by a random number generator. This is unlikely to be any better than the triangulation algorithms where this partitioning occurs as a consequence of data input order. The interpolation and extrapolation are linear which may be a drawback if there is a need to model surface trends between nodes that require a higher order interpolant. The C1 property is available, however, via a variable tension. This is the slowest of the scattered data algorithms by an appreciable margin. For instances where rounding at the nodes is undesirable, this algorithm with zero tension is the only option offered by TableCurve 3D.

Natural Neighbors

The theory behind natural neighbors is an interesting one. For more information, individuals should directly contact David Watson or visit his web page. He personally published the book referenced above. It contains the C-source for his algorithm as well as a detailed description of the algorithm and the natural neighbor concept.

Algorithm Adjustments

This algorithm has two user adjustments. When C is set to 0, the tension is also forced to 0, and the non-gradient-adjusted procedure is used. When C is set to 1, tensions from 1 to 5 are available. The higher the tension, the greater will be the rounding at the nodes and the distribution of the gradient's influence across the surrounding region. Accuracy was found to generally improve with tension.