Click to add points
You can break it by choosing two points on the same virtical line, or picking too many points.
Say you have points
[(1,2), (3,2), (4,5)]
And say you want to find a quadratic which goes through these points.
This is the same as the system of equations
a(1^2) + b(1) + c = 2 a(3^2) + b(3) + c = 2 a(4^2) + b(4) + c = 5
# each row is [1, x, x^2] for each x in points # (backwards order makes evaluation easier in code) A = [[1 1 1] [1 3 9] [1 4 16]] b = [2, 2, 5] # what we want (y values for points) x = [a, b, c] # unknowns, what we're solving forThen you can use elimination to solve
Ax = b, as I've done here.
There are much more sophisticated techniques like the Fast Fourier transform which is
O(n log n), while elimination is
I'll be implementing the FFT later, but for now, I've had my interpolation fix :)