Shgrid Introduction

About Shgrid

Shgrid is a software package in the ngmath library that implements a modified Shepard's algorithm for interpolating random data in 3-space. Shgrid also provides functionality for efficiently finding the nearest point, or points, to a given point in 3-space.

See the comparative analysis of the ngmath packages for details on which ngmath package is most appropriate for your problem.

The output from Shgrid interpolation is a set of values at coordinates on a user-specified grid (which may be a single point).

Functionally equivalent Fortran, C, and NCL interfaces are provided.

Shgrid is based on the work of Robert Renka and his package QSHEP3D. This package is used here with the permission of Dr. Renka. The user entry point names have been changed from those used by Dr. Renka. Also, C and NCL interfaces have been added.

Dr. Renka's articles were published in the ACM Transactions on Mathematical Software, Vol. 14, No 2, June 1988. The original Fortran package QSHEP3D is available from netlib as algorithm number 661.

General background on interpolation and approximation methods

Computational interpolation and approximation 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 or approximated values from the fitted surface. The weighted average methods calculate interpolated or approximated values as weighted averages of known values.

The interpolation method used in Shgrid

Shgrid constructs a once-continuously differentiable function that interpolstes the original data. This function is constructed as follows. First, for each input point a bivariate quadratic is computed that interpolates the functional value at the data point and is a least squares fit to neighboring data values. How close the bivariate quadratic comes to functional values is attenuated by an inverse distance weighting. That is, the calculated bivariate quadratic will fit functional values at nearby points better than at farther points. After the bivariate quatratics are calculated, the interpolating function is calculated as a weighted average of the bivariate quadratics.

There are three control paramters that govern the bahavior of the algorithm. One specifies the number of data points to be used in computing the least squares fits for the local bivariate quadratics, these data points being the ones nearest the input point for which the quadratic is being computed. Another specifies the number of input data points that will be used in calculating the weights for the bivariate quadratics to produce the final function, the input data points used being the ones nearest the point at which interpolation is desired. A third controls the granularity of the sub-grids used in effeciently computing nearest neighbors.

Appropriate defaults are chosen for each of the control parameters. Details on the control parameters are found in the parameters module.

Learning how to use Shgrid

There are entries in the Shgrid package for: interpolating 3-dimensional random data and for finding the nearest point, or points, to a given point in 3-spacd. Details on these entries can be found in the Overview of Shgrid procedures module.