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 O(n^3)
.
I'll be implementing the FFT later, but for now, I've had my interpolation fix :)