Akima II

The Akima 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

Hiroshi Akima

References

"Algorithm 761: Scattered-Data Surface Fitting that has the Accuracy of a Cubic Polynomial", ACM Transactions on Mathematical Software, Vol. 22, No. 3, Sept. 1996, p362-371.

Description

For the Akima II algorithm, the late Hiroshi Akima’s ACM 761 procedure is implemented. This algorithm uses a fixed number of nine for the count of neighboring nodes for the estimation of partial derivatives. As such this algorithm requires at least ten input data points and there are no user adjustments. The algorithm uses Robert Renka's ACM 751 triangulation routines for the Delaunay triangulation. As with the Akima I procedure, the interpolant for each triangle is a 21 coefficient C1 (once continuously differentiable) Hermite bivariate quintic polynomial. Stable extrapolations are also produced.

Revisions to Algorithm

Corrections to 761 were implemented. These will be published by Robert Renka and Ron Brown as a "Remark on Algorithm 761". These include a correction that extracts all boundary edges in thin triangle removal, a correction that scales the thin triangle removal criterion, and the use of algorithm 752's cubic local gradient estimation procedure whenever Akima's gradient algorithm fails to achieve cubic accuracy at a node. The data are intrinsically scaled to a unit square. Routines were also added which compute exact analytic partial derivatives.

Interpolation

This algorithm is based upon quintic Hermite polynomials on triangles. There is one polynomial for each triangle, whose coefficients are determined by the partial derivatives at the nodes of the triangle mesh. Five partial derivatives are computed at each node within the convex hull boundary of the data. The interpolant consists of 21 coefficients for every triangle, 18 values at the nodes with 3 additional conditions that assure continuity of first partial derivatives across triangle edges. With 5 partial derivatives per node, 15 total partial derivatives are used per triangle. The gradient computation scheme begins with Akima's bivariate cubic polynomial interpolation to a point and its nine nearest neighbors. If this is unstable, Renka's cubic local gradient algorithm is implemented, and 14 or more points are used to compute the gradients. In the absence of sufficient points, the algorithm's fallback of bivariate quadratic or planar interpolation is used for the gradients. The algorithm uses a two-tiered weighting scheme for the gradients.

Extrapolation

The algorithm directly provides for extrapolation and maintains a C1 boundary at the transition to the extrapolation regions. The algorithm uses three different lower coefficient count extrapolants to produce stable extrapolations. For extrapolations, only the first two partial derivatives are used at the boundary nodes.

Estimated Partial Derivatives

Full analytic derivatives are available (once with respect to x, to y, twice with respect to x, to y, and with respect to both x and y). These are used for graphing the partial derivative surfaces and for partial derivatives computed in the Evaluation procedure. The first order partials will be continuous, but not smooth. The higher order partials will not be continuous.

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

With the various modifications, this algorithm tended to be the most accurate of the scattered data procedures. The Akima II procedure was particularly effective with the simpler surfaces. This is the only triangulation based algorithm that offers thin triangle removal at the boundary edges, and there is evidence that this results in improved extrapolations. The algorithm is limited in the sense of requiring a ten point minimum data set. As with all triangulation algorithms, the limitation remains where the Delaunay triangulation is often not unique and varies depending on the order of the input data. The Akima II procedure uses a local fit to compute gradients, and this can be a drawback with surfaces that fare better with a global gradient procedure. An Akima-type quintic interpolant which uses a global gradient method is available with the C1 form of the Preusser option.

Algorithm Adjustments

This algorithm has no user adjustments.