Voronoi interpolation

The Voronoi interpolation ( English natural neighbor interpolation "interpolation by natural neighbors"), also called Sibson interpolation , is an interpolation method that works with Voronoi diagrams .

principle

There are points in a metric space and the values ​​assigned to them. An additional point is added to the space. Its value should be interpolated from the surrounding points.

To do this, the Voronoi diagram is first generated from the given points (see Fig. 1). Then the additional point with its Voronoi cell is inserted (see Fig. 2).

Fig. 1. Voronoi diagram. The edges are exactly halfway between two points.		Fig. 2. The new cell (red) is inserted. The areas of overlap with the old cells (orange) serve as weighting factors.

The value of the new point is now obtained by using the area of ​​the intersections with the neighboring cells in relation to the total area of ​​the new cell as weighting factors for the interpolation. In the example above this would be:

${\displaystyle n={\frac {A(A\cap N)}{A(N)}}\cdot a+{\frac {A(B\cap N)}{A(N)}}\cdot b+{\frac {A(C\cap N)}{A(N)}}\cdot c+{\frac {A(D\cap N)}{A(N)}}\cdot d}$

where A (N) indicates the area of ​​an area N, and a, b, c and d stand for the given function values.

application

The Voronoi interpolation can in principle be used anywhere where values ​​are to be interpolated in a metric space.

A triangular mesh simulates the surface of a three-dimensional object. Delaunay triangulation creates triangular networks with properties that are particularly favorable for computer graphics.

Because Voronoi diagrams are closely related to Delaunay triangulation , Voronoi interpolation is particularly suitable in 3D computer graphics. It can be used there to refine an existing triangle mesh by adding new points.