Polynomial interpolation

Click to add points

You can break it by choosing two points on the same virtical line, or picking too many points.

How it works

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 for

Efficiency

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 :)