I am looking for a fast algorithm to remove keyframes based on a maximum error. So if a keyframe is near enough to what can be interpolated from the other keyframes, then that keyframe should be removed. I am using linear interpolation only, so this should be relatively simple to do.

For example, let's say I have these keyframes, with their times and values:

0s 10

0.4s 11.1

0.8s 12

2.0s 20

2.9s 38

3.0s 40

In this example I can remove the key at 2.9s, because interpolating the keys at 2.0s and 3.0s would give the exact same value. Depending on the error threshold I might also be able to delete the key at 0.4s, since removing that one gives an error of only 0.1.

I need an algorithm that can handle several floating point data types, like floats, 2D positions and colours (rgba, so 4D).

Of course I managed to come up with simple brute force algorithms for this, but I would like to use something more efficient. I add a lot of keys in real-time over time and ideally the algorithm would do a small amount of work every time a keyframe is added, instead of doing a lot of work at the end, since otherwise I would get hickups whenever I need to finish a block of keyframes.

I tried searching for algorithms for this, but I mostly found info about things like MPEG keyframes and tools in Blender.

Thanks in advance!