Mathematics isn’t my forte. That’s why each time I have to implement some form of **interpolation**, I feel a headache coming up. Even simple linear interpolation has been bugging me, as it’s the **same thing over and over again**. One of the beauties of software development is you can write something once, and as long as it works, you don’t have to worry about it anymore. Why then, have I already implemented interpolation for around 5 different data types? My latest need for interpolation, I finally decided to put some effort into this bugger and **solve it once and for all**.

Armed with a recently discovered library which allows usage of generics for calculations in C#, I managed to come up with the following classes.

Implementations of *AbstractInterpolation *decide on the **type of interpolation** between certain **key points**. How key points should be interpreted is decided by the implementation of *AbstractKeyPointCollection*. The difference between the two implementations will be demonstrated later. In order to know **what to interpolate **(the *TValue *template parameter), a trivial implementation of *AbstractTypeInterpolationProvider* is required for the type which needs to be interpolated. All classes have a base class *AbstractBasicArithmetic*, which allows to do **basic arithmetic operations** on the specified template type *TMath*. This type determines the value type to use, and return for the calculations of the interpolation. They are done through a ‘*Calculator*‘ object, as specified in the generic calculations article. Normally you have to pass this calculator object yourself, but I created a *CalculatorFactory* which creates the corresponding correct calculator for known value types like *double*.

Perhaps, to better understand the design, a code sample is easier **to demonstrate**. Consider the desired result pictured in the following image. Of course to achieve drawing simple lines, better solutions exist, but for demonstration purposes, this works really well. The subsequent code sets up some points to interpolate between, and the interpolation which will be used.

CumulativeKeyPointCollection<Point, double> keyPoints = new CumulativeKeyPointCollection<Point, double>( new PointInterpolationProvider() ); keyPoints.Add( new Point( 50, 50 ) ); keyPoints.Add( new Point( 100, 100 ) ); ... keyPoints.Add( new Point( 300, 330 ) ); LinearInterpolation<Point, double> linear = new LinearInterpolation<Point, double>( keyPoints );

*CumulativeKeyPointCollection* is chosen instead of *AbsoluteKeyPointCollection*, because every key point added to the collection ‘continues’ on the previous point. The line needs to go through the points** in the order** in which they were added. When using *AbsoluteKeyPointCollection*, every key point has an **absolute position**. It doesn’t matter in which order the key points are added. E.g. Interpolating between known locations at specified times, where time is then used as the absolute position.

Next, some **interpolated points** are calculated as follows.

List<Point> interpolatedPoints = new List<Point>(); double curPercentage = 0; while ( curPercentage < 1 ) { interpolatedPoints.Add( linear.Interpolate( curPercentage ) ); curPercentage += 0.001; }

And that’s how **easy** interpolation can be! To achieve the result as pictured earlier, I just draw line segments between all the calculated points, and draw rectangles on top of the key points. All that remains for the code to work, is the **type provider** for *Point* which was passed to the key point collection. As you can see, that’s just a simple implementation of *AbstractTypeInterpolationProvider*.

/// <summary> /// Allows AbstractInterpolation to interpolate over a list of points. /// </summary> public class PointInterpolationProvider : AbstractTypeInterpolationProvider<Point, double> { /// <summary> /// Create a new provider to allow AbstractInterpolation to interpolate /// between a list of points. /// </summary> public PointInterpolationProvider() : base( 2 ) // The amount of dimensions this type has. { } protected override double GetDimensionValue( Point value, int dimension ) { switch ( dimension ) { case 0: return value.X; case 1: return value.Y; default: throw new NotSupportedException( "Unsupported dimension while doing interpolation on type " + typeof(Point) + "." ); } } public override double RelativePosition( Point from, Point to ) { // Pythagoras to get distance. return Math.Sqrt( Math.Pow( to.X - from.X, 2 ) + Math.Pow( to.Y + from.Y, 2 ) ); } public override Point CreateInstance( double[] interpolated ) { return new Point( interpolated[ 0 ], interpolated[ 1 ] ); } }

To show the **flexibility of this approach**, cardinal spline interpolation is possible by just changing the used *LinearInterpolation* class to *CardinalSplineInterpolation*.

CardinalSplineInterpolation spline = new CardinalSplineInterpolation( keyPoints );

Every time I need to implement something a bit more **mathematically challenging**, and search for help, I seem to end up on web pages created during the Middle Ages of the internet. Aren’t there any reuseable libraries out there which support e.g. interpolation out of the box on the actual types you want to perform it on? Like *Point* in the before given sample. I experience that so many libraries implement concrete implementations instead of **generic solutions**. For the interpolation to work I had to implement a **generic binary search algorithm** because *SortedList* (used to store the key points) didn’t support a binary search out of the box. To indicate intervals of values I had to create a **generic Interval class**, which I immediately could use in other source files as well. All this, of course brings some overhead with it. Instead of Donald Knuth‘s famous “

*premature optimization is the root of all evil*” quote, I find Bill Harlan’s succinct expression even better.

It is easier to optimize correct code than to correct optimized code. – Bill Harlan

Source code can be found as part of my FCL Extension library in the *Whathecode.System* assembly and namespace *Whathecode.System.Arithmetic.Interpolation*.

## One thought on “Interpolation no more”