In
numerical analysis
Numerical analysis is the study of algorithms that use numerical approximation (as opposed to symbolic computation, symbolic manipulations) for the problems of mathematical analysis (as distinguished from discrete mathematics). It is the study of ...
, multivariate interpolation is
interpolation
In the mathematical field of numerical analysis, interpolation is a type of estimation, a method of constructing (finding) new data points based on the range of a discrete set of known data points.
In engineering and science, one often has a n ...
on functions of more than one variable; when the variates are
spatial coordinates, it is also known as spatial interpolation.
The function to be interpolated is known at given points
and the interpolation problem consists of yielding values at arbitrary points
.
Multivariate interpolation is particularly important in
geostatistics
Geostatistics is a branch of statistics focusing on spatial or spatiotemporal datasets. Developed originally to predict probability distributions of ore grades for mining operations, it is currently applied in diverse disciplines including petro ...
, where it is used to create a
digital elevation model
A digital elevation model (DEM) or digital surface model (DSM) is a 3D computer graphics representation of elevation data to represent terrain or overlaying objects, commonly of a planet, moon, or asteroid. A "global DEM" refers to a discrete gl ...
from a set of points on the Earth's surface (for example, spot heights in a
topographic survey
Surveying or land surveying is the technique, profession, art, and science of determining the terrestrial two-dimensional or three-dimensional positions of points and the distances and angles between them. A land surveying professional is ca ...
or depths in a
hydrographic survey
Hydrographic survey is the science of measurement and description of features which affect maritime navigation, marine construction, dredging, offshore oil exploration/offshore oil drilling and related activities. Strong emphasis is placed ...
).
Regular grid
For function values known on a
regular grid
A regular grid is a tessellation of ''n''-dimensional Euclidean space by congruent parallelotopes (e.g. bricks).
Its opposite is irregular grid.
Grids of this type appear on graph paper and may be used in finite element analysis, finite volume ...
(having predetermined, not necessarily uniform, spacing), the following methods are available.
Any dimension
*
Nearest-neighbor interpolation
Nearest-neighbor interpolation (also known as proximal interpolation or, in some contexts, point sampling) is a simple method of multivariate interpolation in one or more dimensions.
Interpolation is the problem of approximating the value of ...
* n-linear interpolation (see
bi-
Numeral or number prefixes are prefixes derived from numerals or occasionally other numbers. In English and many other languages, they are used to coin numerous series of words. For example:
* unicycle, bicycle, tricycle (1-cycle, 2-cycle, 3-cy ...
and
trilinear interpolation
Trilinear interpolation is a method of multivariate interpolation on a 3-dimensional regular grid. It approximates the value of a function at an intermediate point (x, y, z) within the local axial rectangular prism linearly, using function data ...
and
multilinear polynomial In algebra, a multilinear polynomial is a multivariate polynomial that is linear (meaning affine) in each of its variables separately, but not necessarily simultaneously. It is a polynomial in which no variable occurs to a power of 2 or higher; tha ...
)
* n-cubic interpolation (see
bi-
Numeral or number prefixes are prefixes derived from numerals or occasionally other numbers. In English and many other languages, they are used to coin numerous series of words. For example:
* unicycle, bicycle, tricycle (1-cycle, 2-cycle, 3-cy ...
and
tricubic interpolation
In the mathematical subfield numerical analysis, tricubic interpolation is a method for obtaining values at arbitrary points in 3D space of a function defined on a regular grid. The approach involves approximating the function locally by an expre ...
)
*
Kriging
In statistics, originally in geostatistics, kriging or Kriging, also known as Gaussian process regression, is a method of interpolation based on Gaussian process governed by prior covariances. Under suitable assumptions of the prior, kriging giv ...
*
Inverse distance weighting
Inverse distance weighting (IDW) is a type of deterministic method for multivariate interpolation with a known scattered set of points. The assigned values to unknown points are calculated with a weighted average of the values available at the kn ...
*
Natural neighbor interpolation
image:Natural-neighbors-coefficients-example.png, 200px, Natural neighbor interpolation with Sibson weights. The area of the green circles are the interpolating weights, ''w'i''. The purple-shaded region is the new Voronoi cell, after inserting ...
*
Spline interpolation
In the mathematical field of numerical analysis, spline interpolation is a form of interpolation where the interpolant is a special type of piecewise polynomial called a spline. That is, instead of fitting a single, high-degree polynomial to all ...
*
Radial basis function interpolation Radial basis function (RBF) interpolation is an advanced method in approximation theory for constructing Order of accuracy, high-order accurate interpolation, interpolants of unstructured data, possibly in high-dimensional spaces. The interpolant ta ...
2 dimensions
*
Barnes interpolation
*
Bilinear interpolation
In mathematics, bilinear interpolation is a method for interpolating functions of two variables (e.g., ''x'' and ''y'') using repeated linear interpolation. It is usually applied to functions sampled on a 2D rectilinear grid, though it can be ...
*
Bicubic interpolation
*
Bézier surface
Bézier surfaces are a species of mathematical spline used in computer graphics, computer-aided design, and finite element modeling.
As with Bézier curves, a Bézier surface is defined by a set of control points. Similar to interpolation in man ...
*
Lanczos resampling
filtering and Lanczos resampling are two applications of a mathematical formula. It can be used as a low-pass filter or used to smoothly interpolate the value of a digital signal between its samples. In the latter case it maps each sample of t ...
*
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
Bitmap resampling is the application of 2D multivariate interpolation in
image processing
An image is a visual representation of something. It can be two-dimensional, three-dimensional, or somehow otherwise feed into the visual system to convey information. An image can be an artifact, such as a photograph or other two-dimensiona ...
.
Three of the methods applied on the same dataset, from 25 values located at the black dots. The colours represent the interpolated values.
See also
Padua points In polynomial interpolation of two variables, the Padua points are the first known example (and up to now the only one) of a unisolvent point set (that is, the interpolating polynomial is unique) with ''minimal growth'' of their Lebesgue constant ...
, for
polynomial interpolation
In numerical analysis, polynomial interpolation is the interpolation of a given data set by the polynomial of lowest possible degree that passes through the points of the dataset.
Given a set of data points (x_0,y_0), \ldots, (x_n,y_n), with no ...
in two variables.
3 dimensions
*
Trilinear interpolation
Trilinear interpolation is a method of multivariate interpolation on a 3-dimensional regular grid. It approximates the value of a function at an intermediate point (x, y, z) within the local axial rectangular prism linearly, using function data ...
*
Tricubic interpolation
In the mathematical subfield numerical analysis, tricubic interpolation is a method for obtaining values at arbitrary points in 3D space of a function defined on a regular grid. The approach involves approximating the function locally by an expre ...
See also
bitmap resampling.
Tensor product splines for ''N'' dimensions
Catmull-Rom splines can be easily generalized to any number of dimensions.
The
cubic Hermite spline
In numerical analysis, a cubic Hermite spline or cubic Hermite interpolator is a spline where each piece is a third-degree polynomial specified in Hermite form, that is, by its values and first derivatives at the end points of the correspondi ...
article will remind you that
for some 4-vector
which is a function of ''x'' alone, where
is the value at
of the function to be interpolated.
Rewrite this approximation as
:
This formula can be directly generalized to N dimensions:
Two hierarchies of spline interpolations. Practical algorithms for multivariate higher order splines
/ref>
:
Note that similar generalizations can be made for other types of spline interpolations, including Hermite splines.
In regards to efficiency, the general formula can in fact be computed as a composition of successive -type operations for any type of tensor product splines, as explained in the tricubic interpolation
In the mathematical subfield numerical analysis, tricubic interpolation is a method for obtaining values at arbitrary points in 3D space of a function defined on a regular grid. The approach involves approximating the function locally by an expre ...
article.
However, the fact remains that if there are terms in the 1-dimensional -like summation, then there will be terms in the -dimensional summation.
Irregular grid (scattered data)
Schemes defined for scattered data on an irregular grid
An unstructured grid or irregular grid is a tessellation of a part of the Euclidean plane or Euclidean space by simple shapes, such as triangles or tetrahedra, in an irregular pattern. Grids of this type may be used in finite element analysis w ...
are more general.
They should all work on a regular grid, typically reducing to another known method.
* Nearest-neighbor interpolation
Nearest-neighbor interpolation (also known as proximal interpolation or, in some contexts, point sampling) is a simple method of multivariate interpolation in one or more dimensions.
Interpolation is the problem of approximating the value of ...
* Triangulated irregular network
In computer graphics, a triangulated irregular network (TIN) is a representation of a continuous surface consisting entirely of triangular facets (a triangle mesh), used mainly as Discrete Global Grid in primary elevation modeling.
The vertic ...
-based natural neighbor
image:Natural-neighbors-coefficients-example.png, 200px, Natural neighbor interpolation with Sibson weights. The area of the green circles are the interpolating weights, ''w'i''. The purple-shaded region is the new Voronoi cell, after inserting ...
* Triangulated irregular network
In computer graphics, a triangulated irregular network (TIN) is a representation of a continuous surface consisting entirely of triangular facets (a triangle mesh), used mainly as Discrete Global Grid in primary elevation modeling.
The vertic ...
-based linear interpolation
In mathematics, linear interpolation is a method of curve fitting using linear polynomials to construct new data points within the range of a discrete set of known data points.
Linear interpolation between two known points
If the two known poin ...
(a type of piecewise linear function)
** n-simplex
In geometry, a simplex (plural: simplexes or simplices) is a generalization of the notion of a triangle or tetrahedron to arbitrary dimensions. The simplex is so-named because it represents the simplest possible polytope in any given dimension. ...
(e.g. tetrahedron) interpolation (see barycentric coordinate system
In geometry, a barycentric coordinate system is a coordinate system in which the location of a point is specified by reference to a simplex (a triangle for points in a plane, a tetrahedron for points in three-dimensional space, etc.). The ba ...
)
* Inverse distance weighting
Inverse distance weighting (IDW) is a type of deterministic method for multivariate interpolation with a known scattered set of points. The assigned values to unknown points are calculated with a weighted average of the values available at the kn ...
* Kriging
In statistics, originally in geostatistics, kriging or Kriging, also known as Gaussian process regression, is a method of interpolation based on Gaussian process governed by prior covariances. Under suitable assumptions of the prior, kriging giv ...
* Gradient-enhanced kriging
Gradient-enhanced kriging (GEK) is a surrogate modeling technique used in engineering. A surrogate model (alternatively known as a metamodel, response surface or emulator) is a prediction of the output of an expensive computer code.
This predi ...
(GEK)
* Thin plate spline Thin plate splines (TPS) are a spline-based technique for data interpolation and smoothing. They were introduced to geometric design by Duchon. They are an important special case of a polyharmonic spline. Robust Point Matching (RPM) is a common e ...
* Polyharmonic spline In applied mathematics, polyharmonic splines are used for function approximation and data interpolation. They are very useful for interpolating and fitting scattered data in many dimensions. Special cases include thin plate splines and natural cu ...
(the thin-plate-spline is a special case of a polyharmonic spline)
* Radial basis function A radial basis function (RBF) is a real-valued function \varphi whose value depends only on the distance between the input and some fixed point, either the origin, so that \varphi(\mathbf) = \hat\varphi(\left\, \mathbf\right\, ), or some other fixed ...
(Polyharmonic spline In applied mathematics, polyharmonic splines are used for function approximation and data interpolation. They are very useful for interpolating and fitting scattered data in many dimensions. Special cases include thin plate splines and natural cu ...
s are a special case of radial basis functions with low degree polynomial terms)
* Least-squares spline
* Natural neighbour interpolation
{{anchor, Gridding''Gridding'' is the process of converting irregularly spaced data to a regular grid (gridded data).
See also
*Smoothing
In statistics and image processing, to smooth a data set is to create an approximating function that attempts to capture important patterns in the data, while leaving out noise or other fine-scale structures/rapid phenomena. In smoothing, the dat ...
* Surface fitting
Notes
External links
Example C++ code for several 1D, 2D and 3D spline interpolations (including Catmull-Rom splines).
Multi-dimensional Hermite Interpolation and Approximation
Prof. Chandrajit Bajaja, Purdue University
Purdue University is a public land-grant research university in West Lafayette, Indiana, and the flagship campus of the Purdue University system. The university was founded in 1869 after Lafayette businessman John Purdue donated land and money ...
Python library containing 3D and 4D spline interpolation methods.
Interpolation