Interpolating Scattered 3-D Data

The problem that we’re trying to solve here is to interpolate from a large number of measurements of water depths around Deep Creek Lake and place them on a regular grid. The existing measured points are sometimes spaced very closely together and sometimes far apart but cannot be placed directly on a regular grid. A regular grid is needed to create contour lines. The measurement set constitutes a scattered data point set.

The purpose for interpolating is to produce a regularly space data set from which smooth contours can be drawn to show the bathymetry of the lake or of an area of the lake, such as a cove, and from which other values can be inferred such is water depths at locations where there are boat slips.

There are many interpolation methods for 3-D scattered data from which regular grid data can be derived. Ref. 1 is a bibliography of articles on the subject matter.

I have collected many more references that appear to be able to handle our problem. Unfortunately I’m restricted to the methodologies that are available in R, because I do all my work with R.

An excellent discussion of various types of interpolation schemes is provide Ref. 2.

Another good article is provided here Ref. 3.

Here are the methods that I find in R:

Triangulation (or Tetrahedrization) Based Methods

The interpolation methods belonging to this category operate in two steps: First, the scattered point set is triangulated 􏰋in the 2D case􏰀 or tetrahedrized 􏰋in the 3D case􏰀; and then, an interpolation scheme is used within each triangle 􏰋or tetrahedron􏰀. These methods are therefore always local.

Inverse Distance Weighted Methods

One of the most commonly used techniques for interpolation of scattered points is inverse distance weighted interpolation. Inverse distance weighted methods are also known as ‘‘Shepard methods’’ after the name of the first contributor in this field. These methods are basically global, i.e., they use all of the data points to calculate each interpolated value. Their basic assumption is that the interpolated values should be influenced more by nearby points and less by the more distant points. The interpolation value at each new point P is a weighted average of the values of the scattered points, and the weight assigned to each scatter point diminishes as the distance from the interpolation point to the scatter point increases. There are many different ways for choosing these weights.

Radial Basis Function Methods

Radial basis function methods are another example of global interpolation methods for scattered points. The initial ideas, dating from the late 1960’s, are due to Hardy. Basically, these methods can be characterized as follows: For each point \((x_i ,y_i)\) of the data set simply choose some function \(h_i(x,y)\), and then determine coefficients \(a_i\) so that \(f(x,y)􏰒􏰉_i a_i h_i(x,y)\) interpolates the data. Appropriate choices of functions \(h_i(x,y)\) are not easy to make. For example, polynomial functions give a very bad interpolating surface with many overshoots and ripples between the given data points; and even those functions that are known to work well are not always easy to justify mathematically. The most useful functions \(h_i(x,y)\) are radial functions of one variable, \(h(r)\), so that the basis function associated with each data point ( \(x_i\) , \(y_i\) ) is of the form \(h_i(x,y)\)\(􏰒h(d_i)\) , where \(d_i\) is the distance between 􏰋\()(x,y􏰀)\) to \((x_i\) ,\(y_i)\) . This explains the name of this method family.

Interpolation is the process of using points with known values or sample points to estimate values at other unknown points. It can be used to predict unknown values for any geographic point data, such as elevation, rainfall, chemical concentrations, noise levels, and so on.

For our case is to interpret water depth measurements of the lake and create bathymetric maps from the existing point set.

The type of interpolation methods can be divided in many different ways. For our puroses there are two basic approaches that can be defined, namely ‘global’ and ’local’.

In the global approach all of the existing data are fitted to a surface of some kind from which the points on a regular matrix can be computed.

In the local approach, a subset of the point dataset is used to compute the point value at a matrix cell. The subset is typically around the matrix cell and the interpolation methodology dictates how many of those points to consider and how to evaluate them.

Because we have a large number of data points, a global approach may be too time consuming on a computer. A local approached may be better.

In this note we’ll examine a couple of local approaches, assuming we can make them work in R.

Natural Neighbor Interpolation Methods

The last family of scattered data interpolation methods we describe here, is known as natural neighbor interpolation. This interpolation approach is local, and is based on the Voronoi tesselation of the given scattered point set — which is the geometric dual structure of the Delaunay triangulation 􏰋or tetrahedrization􏰀. The Voronoi tesselation partitions the plane 􏰋or space􏰀 into an exhaustive and disjoint set of tiles 􏰋polygons or, respectively, polytopes􏰀, each tile \(T_i\) enclosing one point \(x_i\) of the given point set. The tile \(T_i\) is defined as the area 􏰋or volume􏰀 that is closer to the scatter point \(x_i\) than to any other scatter point.

Multiple B-Spline Approximation

This method is commonly called the MBA (Multiple B-Spline Approximation) method. References Ref. 4 and Ref. 5 are excellent papers that describe this method in detail.

The MBA method is accessible via R. It has shown to provide pleasing results, although I understand only a little of the mathematical background behind it.

Starting with some basic understanding of spline interpolation, please note the article in Ref. 6.

The above mentioned paper presents an overview of the methods of interpolation emphasizing the cubic spline interpolation method, which is widely used in numerous real-world applications. The paper presents the definition of cubic spline interpolation and properties of different types of cubic splines. The MBA method mentioned above is based on this fundamental knowhow.

References

­1. Types of Interpolation
2. Interpolation Methods
3. Scattered Data Interpolation
4. A Study of Cubic Spline Interpolation.
5. Classification of Interpolation Techniques.
6. Data Interpolation with Radial Basis Functions (RBFs) 7.