Interpolation is the determination of a mathematical function which passes through a set of given data points. This function can be used to calculate the intermediate values between the data points. Frequently used interpolation curve types like line segments or cubic splines are supplemented here by a new type: the finite splines. In the mathematical section, I will show an iterative algorithm which specifies the coefficients of the curves, as well as the formula for the calculation of the function value. These algorithms are available in a library. The usage of this library is demonstrated in the open source project IcLibDemo which is hosted on GitHub.
This is the most simple form of interpolation. The data points are connected with straight lines. In some cases the line segment interpolation is good enough, in other cases the angular transitions at the data points are undesirable.
Cubic splines are smooth by all means. In certain cases this feature leads to possibly unwanted overshooting.
Finite splines have the characteristic feature to be as smooth as possible, as long as their curve segments take course inside the vertical range of their two data points. These curves take an intermediate position between line segments and cubic splines. Finite splines are ideal for the definition of smooth curves which have to lie strictly within a confined area.
The transition at each data point can be defined as either smooth or angular. This feature can be used to define additional tips or angles at any data point (Figures 10 and 11). If two data points share the same horizontal position, the curve is splitted up (Figure 12).
The mathematical formulas in this section use position vectors (lower case) which correspond to the points in the figures (upper case). O denotes the point of origin. That is:
The vectors consist of the components x and y:
The curve segment joins two adjacent data points. A curve which contains n data points, therefore consists of n - 1 curve segments. Mathematically, these segments are explicit cubic Bézier functions. The course of this curves is determined by four control points. The two outer control points form the beginning and the end of the curve. The two inner control points define the curvature and usually do not touch the curve. The following paragraphs show the development of the curve segment starting from the well-known parametric Bézier curve.
Usually Bézier curves are applied in their parametric form. In this case, the coordinates of the curve are calculated in dependence on a variable t using two different formulas, one for the x and the other for the y coordinate. This is the mathematical definition:
The Interactive Figure 1 shows the parametric Bézier curve, you can move all the control points in any direction. The curve can be set in any part of the area, it can also be twisted or crossed:
The parametric function is simplified to an explicit function by omitting the first part:
The Interactive Figure 2 shows the explicit Bézier curve. You can move the control points in vertical direction only:
Finally we want to be able to set the explicit Bézier function above any range of the x-axis, as long as dx > ax. For that purpose the variable x is mapped into the range defined by the first and the last control point. The following modulation is applied to the variable x before it's used in the explicit Bézier function:
The Interactive Figure 3 shows the final curve segment. You can move the outer control points in any direction, but you can move the inner control points in vertical direction only. The horizontal positions of the inner control points are dependent on the horizontal positions of the outer control points:
First of all, we have to create the necessary number of curve segments and initialize their control points. The outer control points correspond to the data points, while the inner control points are equally distributed among them. This starting position equals the line segment interpolation. At this stage, the outer control points and the horizontal positions of the inner control points are already definitively fixed.
If smooth transitions are desired, the vertical positions of the inner control points have to be defined so they form tangents at the respective data point transitions. This is the task of the iterative adaption algorithm (Interactive Figure 4).
Interactive Figure 4 shows the progress of the algorithm during the first three iterations. Here follows a detailed explanation of what's happening mathematically in the single steps. First the formulas for the finite spline case are given. The cubic spline case differs in the steps 2, 4 and 5, these formulas are shown at the end of the section. The Interactive Figure 4 shows only the finite spline case.
A simple average calculation is applied:
First the vectors m and n are calculated:
In the next step the slope s of the tangent is calculated.
An important feature of the finite splines is the differentiation between internal and external data points. An external data point forms a tip or a valley, while an internal data point doesn't. The condition in the above formula seperates the two cases. In this step we have to deal with an internal data point, this means that the first part of the conditionalized formula is applied.
Now a tangent at the point D with the slope s is created. The intersections of the tangent with the lines c and e are the vertical positions we are looking for.
In this case the following average calculations are applied:
the same formulas as in step 2 are applied. But now we have to deal with an external data point (a valley). This means that the resulting slope s is always zero (the second part of the condition is true).
In this case we apply:
The calculation of the slope in the cubic spline case is different:
There is no differentiation between internal and external data points here.
Cubic splines don't support smooth data point at the end (and at the beginning). This means that the angular definitions don't have any effect, so the following formula is applied in any case:
Once the control points are defined, the interpolation curve is ready to use. Now we can calculate an y value for any x value on the abscissa, as long as a curve segment is present at the corresponding horizontal position. The formula used for this purpose is based on the DeCasteljau algorithm. Interactive Figure 5 shows how this algorithm works (click and drag with the mouse to change the variable x).
The geometrical construction of the searched point in dependence on a variable x proceeds as follows:
This construction can be expressed algebraically:
This expression is simplified to the already known cubic polynom:
To speed up the calculation the corresponding Horner scheme can be used:
My software UnioGraph uses color gradients with either line segment or finite spline interpolation as desired.
In the project HspGradator the presented interpolation techniques are used for image gradation.
The IcLibDemo project was created with Visual Studio Community 2022 using C++ and MFC. Its purpose is the demonstration of the different interpolation techniques.
The IcLibDemo project introduces the C++ template libraries Point.h and InterpolationCurve.h.
All classes and functions use the namespace ama.
Point.h contains the generic data structure ama::Point and user defined operators for arithmetic operations with this type.
InterpolationCurve.h contains the generic data structures ama::DataPoint and ama::InterpolationCurve. The templates must be instantiated with a floating point type.
In the IcLibDemo project the ama::InterpolationCurve class is instantiated with the data type double.
Download IcLibDemo (64-Bit executable file)
IcLibDemo is distributed under the MIT software license.
Copyright © 2020-2024 Adrian Maurer. All Rights reserved.