Natural neighbor interpolation
200px|thumb|right|Natural neighbor interpolation with Sibson weights. The area of the green circles are the interpolating weights, wi. The purple-shaded region is the new Voronoi cell, after inserting the point to be interpolated (black dot). The weights represent the intersection areas of the purple-cell with each of the seven surrounding cells. Natural neighbor interpolation is a method of spatial interpolation, developed by Robin Sibson.[1] The method is based on Voronoi tessellation of a discrete set of spatial points. This has advantages over simpler methods of interpolation, such as nearest-neighbor interpolation, in that it provides a smoother approximation to the underlying "true" function.
The basic equation is:
- [math]\displaystyle{ G(x)=\sum^n_{i=1}{w_i(x)f(x_i)} }[/math]
where [math]\displaystyle{ G(x) }[/math] is the estimate at [math]\displaystyle{ x }[/math], [math]\displaystyle{ w_i }[/math] are the weights and [math]\displaystyle{ f(x_i) }[/math] are the known data at [math]\displaystyle{ (x_i) }[/math]. The weights, [math]\displaystyle{ w_i }[/math], are calculated by finding how much of each of the surrounding areas is "stolen" when inserting [math]\displaystyle{ x }[/math] into the tessellation.
- Sibson weights
- [math]\displaystyle{ w_i(\mathbf{x})=\frac{A(\mathbf{x}_i)}{A(\mathbf{x})} }[/math]
where A(x) is the volume of the new cell centered in x, and A(xi) is the volume of the intersection between the new cell centered in x and the old cell centered in xi.
200px|thumb|right|Natural neighbor interpolation with Laplace weights. The interface l(xi) between the cells linked to x and xi is in blue, while the distance d(xi) between x and xi is in red.
- Laplace weights[2][3]
- [math]\displaystyle{ w_i(\mathbf{x})=\frac{\frac{l(\mathbf{x}_i)}{d(\mathbf{x}_i)}}{\sum_{k=1}^n \frac{l(\mathbf{x}_k)}{d(\mathbf{x}_k)}} }[/math]
where l(xi) is the measure of the interface between the cells linked to x and xi in the Voronoi diagram (length in 2D, surface in 3D) and d(xi), the distance between x and xi.
See also
References
- ↑ Sibson, R. (1981). "A brief description of natural neighbor interpolation (Chapter 2)". in V. Barnett. Interpreting Multivariate Data. Chichester: John Wiley. pp. 21–36.
- ↑ N.H. Christ; R. Friedberg, R.; T.D. Lee (1982). "Weights of links and plaquettes in a random lattice". Nuclear Physics B 210 (3): 337-346.
- ↑ V.V. Belikov; V.D. Ivanov; V.K. Kontorovich; S.A. Korytnik; A.Y. Semenov (1997). "The non-Sibsonian interpolation: A new method of interpolation of the values of a function on an arbitrary set of points". Computational mathematics and mathematical physics 37 (1): 9-15.
External links
- Natural Neighbor Interpolation
- Implementation notes for natural neighbor, and comparison to other interpolation methods
- Interactive Voronoi diagram and natural neighbor interpolation visualization
- Fast, discrete natural neighbor interpolation in 3D on the CPU
 |  |
