Natgrid Introduction


About Natgrid

Natgrid is a package in the ngmath library of Fortran subroutines and C functions that implements a natural neighbor interpolation method. The input for the interpolation is a set of randomly-spaced two-dimensional coordinates with functional values at those coordinates; the output is a set of interpolated function values at coordinates in a user-specified rectangular grid. The coordinates in the output grid must be monotone increasing in each coordinate direction, but need not be uniformly spaced. It is also possible to interpolate at a single point. See the comparative analysis of the ngmath packages for details on which ngmath package is most appropriate for your problem.

Functionally equivalent Fortran and C interfaces are provided in both single and double precision versions.

Natgrid is based on the work of Dr. Dave Watson and his nngridr package. Dr. Watson is well known in the field of interpolation. He has published many articles and two books in the area. See the references module for further information. Dr. Watson has our greatest gratitude for allowing us to incorporate segments of his code in our package. Information on how to obtain Dr. Watson's original nngridr code, as well as his accompanying book, can be obtained from URL http://www.iinet.com.au/~watson/nngridr.html.

General background on interpolation methods

Computational interpolation methods can be divided into two basic classes: fitted function methods and weighted average methods.

The fitted function methods fit an algebraic surface to the known data and then pick the interpolated values from the fitted surface. The weighted average methods calculate interpolated values as weighted averages of known values.

Among the weighted average methods, the simplest are known as the inverse distance weighted average methods. These methods are implemented by calculating weights for all input coordinates such that the weights are inversely proportional to the distance an input coordinate is from the point where an interpolated value is desired. The sum of the weights is normalized to unity and an interpolated value is the sum of the products of the functional values and the calculated weights.

The interpolation method used in Natgrid

Natgrid uses a weighted average method that is much more sophisticated than the inverse distance weighted average methods mentioned above. The method used in Natgrid is known as natural neighbor interpolation. Natural neighbor interpolation was introduced by R. Sibson in the early 1980s.

One distinguishing quality of natural neighbor interpolation is the way in which a set of neighboring points (the natural neighbors) is selected to use for interpolating at a given point. The natural neighbor selection process avoids the problems common to methods based on choosing a fixed number of neighboring points, or all points within a fixed distance.

Another distinguishing quality of natural neighbor interpolation is the way that the weights are calculated for the functional values at the natural neighbor coordinates. These weights are based on proportionate areas, rather than distances.

The method of finding the natural neighbors and calculating areas-based weights to produce interpolated values is called natural neighbor linear interpolation. This produces an interpolated surface that has a continuous slope at all points, except at the original input points. The result of natural neighbor linear interpolation can be visualized as producing a snugly fit sheet stretched over all of the input data.

The interpolation method in Natgrid also allows for natural neighbor linear interpolation augmented by blending in gradient estimates. This latter is referred to as natural neighbor nonlinear interpolation. Natural neighbor nonlinear interpolation produces an interpolated surface that has a continuous slope at all locations; two tautness parameters can be set by the user to control the apparent smoothness of the output surface.

If you are interested in the details of the interpolation method used in Natgrid, you will want to buy Dr. Watson's book mentioned above.

Learning how to use Natgrid

You should now proceed to the module on learning how to use Natgrid.
home | contents | defs | params | procedures | exmpls | index