# Curved line through points

I would like to be able to do something like this in c++.

How can I go about creating a nice curved line like this through a list of points?

Can anyone please point me in the direction of the relevant maths?

Edit 1:

Here is another example of what I would like from the output.

I need to be able to calculate Y for any given X...

Edit 2:

Please don't just post existing APIs, chances are they will be useless on an MCU. I would prefer reading the maths...

-
Look up "cubic spline" –  user22805 Sep 12 '12 at 0:46
In addition to cubic splines and splines in general, maybe these pointers can help as some are open source: stackoverflow.com/questions/481209/… –  Amzoti Sep 12 '12 at 0:48
These may also be helpful: linux.about.com/od/howtos/l/blsc6.htm –  Amzoti Sep 12 '12 at 0:51
I have been playing with them already... well bezier cubic splines... but its too complicated to work out the Y for any given X (which I need to do). Is there a version of cubic/quadratic splines which would allow me to do this? –  Beakie Sep 12 '12 at 0:53
What's an API? What's an MCU? –  Gerry Myerson Sep 12 '12 at 1:34

I wrote up some notes on cubic splines, just a couple of pages about a third of the way through these notes. I think the calculations are not too hard.

-
+1, Thank you for sharing this information, very readable. –  Emmad Kareem Sep 12 '12 at 1:49
Just printed it out. Very good resource. Thanks so much! –  Beakie Sep 12 '12 at 2:33
...will get back to you on the difficulty when i try it :) –  Beakie Sep 12 '12 at 2:34
The problem with this is its assumes equally spaced points... which my points will definitely not be :( Great text though –  Beakie Sep 12 '12 at 4:00
Yes, you're right (although the example you gave in the original question has equally spaced points). The calculations are more difficult when the points are not equally spaced, and I'm afraid I have nothing written up - but my guess is that if you keep looking you'll find it written up somewhere, and the formulas won't be all that bad for computing. –  Gerry Myerson Sep 12 '12 at 4:54

One way is to consider the method of Quadratic Least Square Regression. For an example in C# see CodeProject-Least Square Regression for Quadratic Curve.

The point to notice is that such methods make assumptions about the function value for the data you don't provide. For example, it assumes that data at $x=4.5$. Such assumptions may not be correct.

I assume that Excel is using QR Decomposition method to produce your chart.

For starters, this introduction may help: Seminar-Curve Fitting

-
Curve-fitting and interpolation are not the same thing! Least-squares won't ensure that the curve goes through the given points. –  Rod Carvalho Sep 12 '12 at 1:15
You are absolutely correct. I suggested curve fitting because I am not sure what method Excel uses. –  Emmad Kareem Sep 12 '12 at 1:17
I dont want a single quadratic formula (which I believe this technique will give me). I want to ensure I strike straight through every point and just curve off to some acceptable degree between each point. See edit 1, above. –  Beakie Sep 12 '12 at 1:18
Do you always have fixed number of points? How many points are you expected to have? –  Emmad Kareem Sep 12 '12 at 1:22
an unspecified amount :) –  Beakie Sep 12 '12 at 1:24