Interpolation with Finite Splines

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.

Line Segment Interpolation

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.

Fig. 1: Line segment interpolation 1
Fig. 2: Line segment interpolation 2
Fig. 3: Line segment interpolation 3

Cubic Spline Interpolation

Cubic splines are smooth by all means. In certain cases this feature leads to possibly unwanted overshooting.

Fig. 4: Cubic spline interpolation 1
Fig. 5: Cubic spline interpolation 2
Fig. 6: Cubic spline interpolation 3

Finite Spline Interpolation

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.

Fig. 7: Finite spline interpolation 1
Fig. 8: Finite spline interpolation 2
Fig. 9: Finite spline interpolation 3

Additional Features

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).

Fig. 10: Smooth transition
Fig. 11: Angular transition
Fig. 12: Splitted curve

Mathematical Section

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

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:

Interactive Fig. 1: Parametric Bézier function

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:

Interactive Fig. 2: Explicit Bézier function

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:

Interactive Fig. 3: Final curve segment

Control Point Initialization

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 Fig. 4: Iterative adaption algorithm

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.

Step 1 - Angular data point at the beginning

A simple average calculation is applied:

Step 2 - Smooth transition (finite splines)

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.

Step 3 - Angular transition

In this case the following average calculations are applied:

Step 4 - Smooth transition (finite splines)

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).

Step 5 - Smooth data point at the end (finite splines)

In this case we apply:

Steps 2 and 4 - Smooth transitions (cubic splines)

The calculation of the slope in the cubic spline case is different:

There is no differentiation between internal and external data points here.

Step 5 - Smooth data point at the end (cubic splines)

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:

The DeCasteljau Algorithm

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).

Interactive Fig. 5: DeCasteljau algorithm

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:

Usage Examples

Color Gradient

My software UnioGraph uses color gradients with either line segment or finite spline interpolation as desired.

Fig. 13: Line segment interpolation
Fig. 14: Finite spline interpolation

Image Gradation

In the project HspGradator the presented interpolation techniques are used for image gradation.

Project

The IcLibDemo project was created with Visual Studio Community 2022 using C++ and MFC. Its purpose is the demonstration of the different interpolation techniques.

Libraries

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.

Handling

Fig. 15: IcLibDemo

Download

Download IcLibDemo (64-Bit executable file)

GitHub

View project on GitHub

License

IcLibDemo is distributed under the MIT software license.

Literature


Powered by CodeCogs

Copyright © 2020-2024 Adrian Maurer. All Rights reserved.