Interpolation is a very common operation in computing and especially video processing (my background for the last 7 years). In this article I’m going to go over a C++ implementation we used at my last job (reconstructed from memory since I no longer work there).

This group of functions follows the form: T interpolate(T const &a, T const &b, double pct). a and b are the two objects we are interpolating, and pct ranges from 0.0 to 1.0.

The first thing you would need to interpolate are floating point numbers. I’m going to use some templating and type_traits, but if you’re not familiar with them I’ll give simplified explanations as well.

Scalar Types

Floating Point Interpolation

template <typename T, // For any type...
          std::enable_if_t<std::is_floating_point_v<T>, bool> = true> // well only types that are floating point
T  interpolate(T const &a, T const &b, double pct)
{
    return a + pct * (b - a);
}

This is straight from the mathematical definition of linear interpolation. In fact, if you have C++20 or later, you can use the standard version of this function.

Integral Interpolation

We didn’t use the standard version for integral interpolation for two reasons: 1) it didn’t exist at the time and 2) we wanted rounding in the results. So here’s the integral implementation:

template <typename T, // For any type..
          std::enable_if_t<std::is_integral_v<T>, bool> = true> // Well only integral types
T  interpolate(T const &a, T const &b, double pct)
{
    double A = a;
    double B = b;
    return A + pct * (B - A) + 0.5;
}

It’s basically the same as the floating point version. We convert to double so we can hold on to the remainder, add 0.5 for rounding and then convert back to the integral type.
(This implements the rounding you learned in elementary school: add 0.5 and truncate, for short.)

Non scalar types

So how do you interpolate complex types like x,y pairs or rectangles? Easily!

Points

Say you have a point class like this

struct Point {
    int32_t x
    int32_t y;
};

Interpolating between two points is as simple as interpolating x and y independently:

Point  interpolate(Point const &a, Point const &b, double pct)
{
    return {
        interpolate(a.x, b.x, pct),
        interpolate(a.y, b.y, pct)
    };
}

This implementation uses the “scalar interpolate” functions introduced earlier.

Rectangles

Interpolating a rectangle is also easy:

class Rectangle {
    int32_t x;
    int32_t y;
    int32_t w;
    int32_t h;
}
Rectangle  interpolate(Rectangle const &a, Rectangle const &b, double pct)
{
    return {
        interpolate(a.x, b.x, pct),
        interpolate(a.y, b.y, pct),
        interpolate(a.w, b.w, pct),
        interpolate(a.h, b.h, pct),
    };
}

This is actually exactly how we did interpolation of rectangles for a long time. However, there’s a slight bug - for some interpolations you get “jitter” where the right and bottom edges of the rectangle actually move “backwards”. The fix is simple though: instead of interpolating the width and height you interpolate the bottom-right corner of the rectangle.
(Side note: storing a Rectangle as top-left position + size is equivalent to storing the top-left position and the bottom-right position. It’s trivial to convert between those styles.)
Code for that algorithm is left as an exercise to the reader.

Complex Objects

What about an object that represents different properties of a video zone? Easy peasy, just interpolate each member variable.

You can even interpolate std::arrays and std::vectors:

template <typename T, std::size_t N>
std::array<T,N>  interpolate(std::array<T> const &a, std::array<T> const &b, double pct)
{
    std::array<T,N> ret;
    for (std::size_t i = 0 ; i < N ; i++){
        ret[i] = interpolate(a[i], b[i], pct);
    }
    return ret;
}

std::vector is basically the same, but you have to decide what to do when they are different lengths. In our use case, we made that an error.

You can even interpolate std::map: for keys that exist in both maps, you interpolate between the two values and take the result. For keys that only exist in one map but not the other, you have a choice what to do (take or drop the value, possibly depending on the value of pct). I believe our use case always took the value, regardless of which map it came from or the value of pct.

Optionals can be interpolated, and the use case is niche but I’ll get to it in a future post. For now, here is the implementation:

template <typename T>
std::optional<T>  interpolate(std::optional<T> const &a, std::optional<T> const &b, double pct)
{
    if (!a && !b)  return std::nullopt; // Nothing to interpolate between, so return nothing.
    if (a && b)  return interpolate(*a, *b, pct); // Two things to interpolate, so interpolate the values
    if (!a && b)  return b;
    if (a && !b)  return a;
}

Those last two case are where you have a choice again. I believe we ended up just taking the value that was present.

Conclusion

In the end, this overload set is pretty powerful. Given two objects of the same type, interpolate between them, cascading down into subobjects. Just about anything can be interpolated this way, and I believe the results are meaningful in some context.