Skip to content

Review: A Two-Dimensional Interpolation Function for Irregularly-Spaced Data

Citation

  • Shepard, D. (1968). A two-dimensional interpolation function for irregularly-spaced data. Proceedings of the 23rd ACM National Conference, 517–524.
  • DOI

Abstract

A method is described for interpolating a smooth, continuous surface \( z = f(x, y) \) through a finite set of irregularly-spaced data points \( (x_i, y_i, z_i) \). The interpolated value at a point is a weighted average of the data values, with a weight that decreases with distance, so that the surface passes exactly through the data, is continuous and differentiable, and is inexpensive to compute. Refinements restrict the average to nearby points for efficiency, add direction and slope terms to improve the shape, and allow barriers that introduce deliberate discontinuities.

Shepard addresses a problem that recurs whenever data are collected at scattered locations: how to draw a continuous surface through \( N \) irregularly-spaced triplets \( (x_i, y_i, z_i) \) that passes exactly through the data, is smooth, and is cheap enough to evaluate on a fine grid for contouring.

The core idea is a distance-weighted average. For a query point \( P \) at distances \( d_i \) from the data points \( D_i \),

\[f(P) = \frac{\sum_i d_i^{-u}\, z_i}{\sum_i d_i^{-u}}\]

As \( P \) approaches a data point, that point's weight grows without bound while the others stay finite, so \( f(P) \to z_i \) and the surface interpolates the data exactly. The exponent \( u \) controls the shape: \( u > 1 \) makes the surface differentiable, and \( u = 2 \) is both differentiable and the cheapest to compute, since \( d_i^{-2} = 1/[(x - x_i)^2 + (y - y_i)^2] \) avoids a square root.

Pure inverse-distance weighting has two practical faults: every data point contributes to every evaluation, and distant points influence the surface as if they were near. Shepard's remedy, the part Hifuku uses, is to restrict the average to nearby points through a compactly supported weight. A search radius \( r' \) is chosen so that a neighborhood holds about seven data points on average, \( \pi r'^2 = 7 A / N \) for data area \( A \), and the weight

\[s(d) = \begin{cases} 1/d & 0 < d \le r'/3 \\ \dfrac{27}{4 r'}\left(\dfrac{d}{r'} - 1\right)^2 & r'/3 < d \le r' \\ 0 & d > r' \end{cases}\]

is continuously differentiable and falls to zero at \( r' \), so points beyond the radius drop out with no discontinuity. Shepard also develops direction (shadowing) and slope terms and a barrier mechanism; those are refinements Hifuku does not use.

Relevance to Hifuku

Hifuku renders the elevation surface of an archive by Shepard interpolation. The elites are scattered points on the chart, each carrying a measured log-likelihood, and EliteArchive.surface interpolates them onto a regular grid through the shepard_grid utility. The implementation uses the compactly supported weight \( s(d) \) above (squared, as Shepard's improved function \( f_2 \) prescribes) and the seven-points-per- neighborhood radius \( \pi r'^2 = 7 A / N \), and it masks the grid beyond the support radius, where no elite constrains the value. The weight and the radius rule are verified in docs/theory/algebra/shepard1968-weight.py.

Interpolation here is only a rendering step. The elevation of the map is the measured log-likelihood at the elites; Shepard interpolation fills the space between them for a smooth surface and invents no elevation of its own.