for implementing 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?

Huge thanks in advance!

  • 3
    $\begingroup$ Linear interpolation doesn't overshoot. If that doesn't work, please list what additional criteria you need to satisfy. $\endgroup$ – Bungo Sep 3 '18 at 2:02
  • $\begingroup$ @Bungo You are right! An additional criteria is needed. Hm, I'm not a matimatician, so simply put I want a curve that's as smooth as possible and also monotone between two points. Maybe the following definition makes sense: The second derivation on the curve shall be overall minimal. Linear interpolation has a very high second derivation at every point where direction changes. $\endgroup$ – DragonGamer Sep 3 '18 at 2:24
  • 1
    $\begingroup$ The monotone cubic interpolation that I'm familiar with (the Fritsch-Carlson method) is guaranteed not to overshoot the data. If your implementation does overshoot, either you have implemented something that is not truly monotone, or there is a bug in your implementation. $\endgroup$ – user856 Sep 3 '18 at 4:16
  • $\begingroup$ There is a method called Barycentric Lagrange interpolation. There are plenty of libraries available for it. $\endgroup$ – user3417 Sep 3 '18 at 21:00
  • 1
    $\begingroup$ Indeed there was a dumb implementation mistake x.x Oh well, sorry for wasting your all time! Barycentric Lagrange interpolation sounds interesting too though. $\endgroup$ – DragonGamer Sep 3 '18 at 21:19

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.

  • 1
    $\begingroup$ Thank you for the response. Unfortunately that results in quite a "corner" at the point where it would start to overshoot. "Bungo" u there is right though, I need to specify an idditional criteria. One moment. $\endgroup$ – DragonGamer Sep 3 '18 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.