Interpolation method that does never overshoot

Question

To implement a system that will control hardware, I need an interpolation between points on a graph that does never overshoot. By overshooting I mean that between two points there may be no y-result that has a higher value than either of thew two points.

First I thought that "monotone cubic interpolation" might be what I need, however after implementation I found that this isn't always the case. After researching, I found that this only reduces overshooting, doesn't prevent it entirely. That can also be seen here, I think: Implementation of Monotone Cubic Interpolation )

So what other algorithms/formulas could fulfill this requirement?

Answer 1

One option is use a monotone cubic interpolation but always check the values of the points on both sides, and if the value exceeds one of the two y values, just go with that y value instead.

Answer 2

If you can do without the 'strict' interpolation criterion (saying that the curve must pass precisely through the knot points), you can use a b-spline without prefiltering - simply use the knot points you have as the spline's coefficients. The b-spline is bound to the convex hull of it's coefficients, so it can't overshoot the range if it's coefficients aren't ever out-of-bounds. But omitting the prefilter will 'spoil' the interpolation criterion, and the resulting curve will not pass exactly through your data points - it will appear slightly 'smoothed'. Oftentimes, though, this is quite acceptable, and it will never overshoot.

Answer 3

you want "smoothstep" or "smootherstep" you can derive them from differential equations or function intuition, but basically these shape linear interpolation so that the derivative is 0 at the ends, and concatenating these curves results in continuous first derivatives for smoothstep, and both first and second for smootherstep.

linear: lerp(a, b, t)

smoothstep: lerp(a, b, 3t^2 - 2t^3)

smootherstep: lerp(a, b, 6t^5 - 16t^4 + 10t^3)

lerp being a shorthand for a + (b-a)*t

these do lose some of the nice visual properties of the cubic interpolation - they only sample 2 points, not 4, but they does meet the criteria you specify, never overshooting and being continuous and smooth to first or second order.