Additional Mathematical Explanation of Linear Interpolation

Delaunay triangulation is a method of dividing a two-dimensional space into triangles whereby the vertices of the triangles are the given data points. This is based on the following assumptions:

• The triangles do not overlap (no intersection) and are therefore unique.

• The union set of the triangles returns the original dataset.

• Circumcircle criteria (the circumcircle of the triangles does not contain any other point from the triangle).

Delaunay triangulation can also be applied to a three-dimensional space: Tetrahedrons are formed instead of triangles, and instead of the circumcircles of each triangle being analyzed, a sphere around the tetrahedron is analyzed.

A number of algorithms can be used to create a Delaunay triangulation. The algorithm used for linear interpolation was proposed by Bowyer and Watson.

The algorithm includes a step-by-step procedure:

1. Add a point to the existing triangulation.

2. Find the nearest point in the existing triangulation, and all of the triangles where this nearest point is a vertex.

3. Find all triangles whose circumcircle contains the new point.

4. Delete all triangles whose circumcircle contains the new point. A convex hull is the result.

5. Join the new point to all vertices on the boundary of the hull.

The system has to find the simplex that contains the required point before it starts the interpolation. This procedure is depicted in the figure below:

In the figure above, vectors ab and ac form the coordinate system of the triangle. To find out whether point p is inside or outside the triangle, the system first calculates x and y from the linear equation system ap = x ab + y ac.

Point p is inside the triangle if the following conditions are met:

• Both x and y are greater than zero.

• The sum of x and y is less than one.

If point p is outside the triangle, the system uses parametersx and y to decide which triangle to analyze in the next step. For example, if x>0 and y>0 and x+y>1, then point p is on the right side of edge bc. Therefore, the next triangle to be analyzed must also have edge bc.

Using the values calculated from parameters x and y the system interpolates the required function value by means of the following equation:

F(x) = F(a) + x*(F(b) – F(a)) + y * (F(c) – F(a))

After triangulation has been completed, the system forms the convex hull for extrapolation as follows:

Identify all of the sides of the triangles (faces of the tetrahedrons) that belong to a simplex. The sides (faces) form the triangular mesh of the hull.

If side bc is inside the convex hull and the required point is to the right of bc, this point is then outside the triangular mesh. To find the function value for the required point, the system uses the function value of the nearest point on the convex hull. The nearest point is found as follows:

1. Take a side that is part of the convex hull (for example, bc) and calculate the point on the side that is the shortest distance away from the required point. This is either one of the vertices or a point between the vertices.

   • If the nearest point is a point between the vertices, this is the general nearest point because the hull is convex.

   • If the nearest point is one of the vertices, the system uses the side next to this vertex to calculate the shortest distance to the required point.

2. If the system does not find a shorter distance, then that point is the nearest point.