Interpolation

Having a triangulation is nice, often we just need the to subdivide some points into some planar triangles. There are other algorithms doing that faster than delaunay triangulations. The real strength of the delaunay triangulation is that its triangles tend to be "well formed" for interpolation tasks, that is, the resulting grid will have fewer sharp and stretched triangles which can distort the interpolated values.

Even more, delaunay triangulations and their dual graph, the voronoi diagram, introduce the concept of natural neighbors. These make advanced interpolation strategies possible which are - in contrast to traditional barycentric interpolation - smooth (C¹) at the triangulations edges.

What is interpolation

Imaging you're coming back from a field trip and collected data like temperature, air pressure or terrain height. You know where every measurement was taken. Now we are interested in an estimate about the temperature, air pressure or terrain height at some other point where we have not taken a measurement. To do that, we expand the measurements to form a continuous function within their convex hull.
In contrast to other interpolation methods, we impose no special structure upon the measurements (e.g., the measured points must not lie on a grid). The interpolation, especially natural neighbor interpolation, gives useful results even for irregularly sampled points.

Interpolation Methods

Spade offers various interpolation methods:

• Barycentic interpolation
• Natural neighbor interpolation
• Sibson's C¹ interpolation
• Farin's C¹ interpolation

In the following example, we will interpolate the heights of the points in the triangulation.
Note that interpolation outside of the convex hull is rather atrocious at the moment, it might be improved in future releases.

Barycentric interpolation

Barycentric interpolation is the fastest and most basic interpolation method. It its $C^\infty$ everywhere besides on the triangulation's points and edges.

Sibson's $C^0$ interpolation

This interpolation is $C^0$ at the data points and $C^1$ everywhere else.

Sibson's $C^1$ interpolation

This interpolation is $C^1$ at all sites. For each data point, a gradient must be given that will be approximated.

Farin's $C^1$ interpolation

This interpolation is similar to sibson's $C^1$ interpolation. Again, we must define a gradient for each data point.