Renka II¶
The Renka II 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
Robert Renka
Dept. of Computer Sciences
University of North Texas
Denton, TX 76203-6886
E-mail:renka@cs.unt.edu
Web page: http://www.cs.unt.edu/home/renka/
References
"Multivariate Interpolation of Large Sets of Scattered Data", ACM Transactions on Mathematical Software, Vol. 14, no. 2, June 1988, p139-148.
"Algorithm 660: QSHEP2D: Quadratic Shepard Method for Bivariate Interpolation of Scattered Data", ACM Transactions on Mathematical Software, Vol. 14, no. 2, June 1988, p149-150.
"CSHEP2D: Cubic Shepard Method for Bivariate Interpolation of Scattered Data", Submitted to ACM TOMS.
Description
The Renka II procedure is a nearest neighbor weighted least-squares C2 (twice continuously differentiable) or C1 (once continuously differentiable) procedure that is free from the limitations of triangulation based algorithms. The nodal functions are ten parameter cubic or six parameter quadratic polynomials whose coefficients are determined by least-squares fitting of an adjustable number of nearest neighbor data points. The algorithm also offers an adjustment of the number of nodes which define the radii of influence for the weights. The method is known as "modified cubic Shepard" or "modified quadratic Shepard" procedure. Although slower than triangulation-based procedures, this algorithm generally offers equal or greater accuracy in interpolation. By using higher data point counts some very stable extrapolations are possible.
Revisions to Algorithm
The number of nodes which define the radii of influence for the weights is automatically set by TableCurve 3D to a value approximately 50% greater than the local data count. The data are also intrinsically scaled to a unit square.
Interpolation
The interpolation scheme is a modified Shepard method. The interpolant is weighted sum of bivariate quadratic or cubic nodal functions. The coefficients for each of the nodal functions are obtained by a weighted least squares fit to the closest n nearest neighbor data points. As such, the radius of influence for the least-squares fit is fixed for each node, but varies across nodes. The nearest neighbor determination is based on an efficient cell-based scheme. The radius of influence for the weights also varies with node as is needed to satisfy this second nodal count which TableCurve 3D fixes at approximately 1.5x the count of nodes set for the least-squares fit.
Extrapolation
For a nearest neighbor procedure, extrapolation and interpolation are indistinguishable.
Estimated Partial Derivatives
All partial derivatives are computed analytically for the C2 cubic procedure. For the C1 quadratic, the first order partial derivatives are computed directly by this algorithm and the second order derivatives and the derivative with respect to both x and y are computed via a numeric differentiation procedure. The C2 procedure offers smooth and accurate first order partial derivatives.
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
The Renka II algorithm is a well crafted nearest neighbor least-squares estimation procedure. The procedure can vary from a global method to a very local one, depending on the nodal count used for the fitting. Accuracy tests suggested it to be an excellent algorithm for particularly difficult surfaces containing multiple features.
Algorithm Adjustments
The only user adjustments for this algorithm are the C1 or C2 algorithm and the count of nearest neighbor data points. The TableCurve 3D default neighbor count is 13 (C1) or 17 (C2). With these values, the node count for the radii of weighting is automatically set at 19 (C1) or 30 (C2). This number of nodes which define the radii of influence for the weights is automatically set to a value approximately 50% greater than the local data count.In the Interpolate Uniform Grid option, the nearest neighbor count is fixed at 13 (C1) or 17 (C2), or the data count, whichever is smaller.