# What's the best way to calculate all of the points for a curve given only a few points?

I've been reading up on curves, polynomials, splines, knots, etc., and I could definitely use some help. (I'm writing open source code, if that makes a difference.)

Given two end points and any number of control points (including e.g. $0$ and $100$), I need to calculate many different points for curve. This curve must pass through all points, including the end points.

I'm not sure if this means that there is even a difference between the end points and the control points or not; I guess the difference would be that the end points don't have any points on the "outside", and thus they are different in that regard.

I have tried and succeeded with the "De Casteljau's algorithm" method, but the curve it generates doesn't (necessarily) pass through the control points (unless on a straight line or something).

I have also looked into solving for the curve's equation using a generic polynomial curve equation, e.g.:

$y = a + b x + c x ^ 2 + \dots + j x ^ 9$

plugging points into it, and then solving systematic equations. The problem with this approach is that it solves for a function, so then the curve wouldn't be able to go "backwards" any, right (unless it's a "multivalued" function maybe)?

Based on browsing through Wikipedia, I think what I might want is to calculate a spline curve, but even though I know some Calculus I'm having trouble understanding the math behind it.

I asked this question in the Mathematics section because I'm expecting a mathematical answer, but if the solution is easier to explain with pseudocode or something then I'll take that too. :)

Thanks!

• Andrew

Update: I'm looking to curve fit using Spline (low-degree) polynomial interpolation given some points. Order matters (as marty cohen explained it), and I want each polynomial to be continuous in position, tangent, and curvature. I also want minimalized wiggles and to avoid high degree polynomials if possible. :D

-
What do you mean about "Backwards" and "the end points don't have any points on the outside? – Zeta.Investigator Jun 16 '13 at 5:31
Have you seen these pages? en.wikipedia.org/wiki/Interpolation and en.wikipedia.org/wiki/Extrapolation – Zeta.Investigator Jun 16 '13 at 5:34
This is what I consider going "backwards": i.imgur.com/j5ldhFu.png Notice how the curve goes outside the minimal bounding rectangle (based off of the provided points) and goes back over the same x value with a different y value. I said "the end points don't have any points on the outside" in reference to the fact that they are in fact end points. If you were to add another point outside an end point, it would no longer be an end point, etc. This could very well then change the slope of the tangent line on that point (that used to be the end point). – Andrew Jun 16 '13 at 5:47
@PooyaM : He means that you cannot draw the curve on the plane with a parametrization of the form $\vec v(t) = (t,f(t))$ because there are at least two points on the curve who have the same $x$-coordinate but distinct $y$-coordinates. – Patrick Da Silva Jun 16 '13 at 5:53
@Andrew : Do you have an example of a curve you want to plot, with the control points? Because I think mathematically your description is a bit vague ; maybe in your terms it will be easier to understand! – Patrick Da Silva Jun 16 '13 at 5:54

It looks like your set of endpoints and control points can be any set of points in the plane. This means that the $order$ of the points is critical, so that the generated curve goes through the points in a specified order.

This is much different than the ordinary interpolation problem, where the points of the form $(x_i, y_i)$ are ordered so that $x_i < x_{i+1}$.

As I read your desire, if you gave a set of points on a circle ordered by the angle of the line from the center to each point, you would want the result to be a curve close to the circle.

There are a number of ways this could be done. I will assume that you have $n+1$ points and your points are $(x_i, y_i)_{i=0}^n$.

The first way I would do this is to separately parameterize the curve by arc length, with $d_i = \sqrt{(x_i-x_{i-1})^2+(y_i-y_{i-1})^2}$ for $i=1$ to $n$, so $d_i$ is the distance from the $i-1$-th point to the $i$-th point.

For a linear fit, for each $i$ from $1$ to $n$, let $t$ go from $0$ to $d_i$ and construct separate curves $X_i(t)$ and $Y_i(t)$ such that $X_i(0) = x_{i-1}$, $X_i(d_i) = x_i$, and $Y_i(0) = y_{i-1}$, $Y_i(d_i) = y_i$. Then piece these together.

For a smoother fit, do a spline curve through each of $(T_i, x_i)$ and $(T_i, y_i)$ for $i=0$ to $n$, where $T_0 = 0$ and $T_i = T_{i-1}+d_i$. To get a point for any $t$ from $0$ to $T_n$, find the $i$ such that $T_{i-1} \le t \le T_i$ and then, using the spline fits for $x$ and $y$ (instead of the linear fit), get the $x$ and $y$ values from their fits.

Note that $T_i$ is the cumulative length from $(x_0, y_0)$ to $(x_i, y_i)$, and $T_n$ is the total length of the line segments joining the consecutive points.

To keep the curves from not getting too wild, you might look up "splines under tension".

Until you get more precise, this is as far as I can go.

-
What you said about ordering and the circle is correct. Could you clarify what d_i and i_i mean? I am looking to generate spline curves. – Andrew Jun 16 '13 at 6:19
That's a typo. I will fix. – marty cohen Jun 16 '13 at 6:34
Ahh. Much better. :) So... i is the resulting point number that goes from 0/1 to n, t is the point number for each individual polynomial that goes from 0 to d_i, d_i is the linear distance between each end/control point, and X_i and Y_i are the sets of resulting points? What are T_0 and T_i then, and why are they being paired with x_i and y_i for spline curves? What's confusing is that T_i is the first in each pair. Thanks. – Andrew Jun 16 '13 at 7:18
I added some more explanation. – marty cohen Jun 16 '13 at 17:32

Well, you have some points of a "curve" of unknown type and you want to know which set of points would that curve passes.
Suppose you know the price of gold in US market at time 10:00AM . You also know that price at 11:00 AM. Does it mean that "given mere two points,you can predict the exact price at any time later?"
Here comes the concepts of Interpolation and Extrapolation and Fitting methods.

From Wikipedia:

In the mathematical field of numerical analysis, interpolation is a method of constructing new data points within the range of a discrete set of known data points.

In engineering and science, one often has a number of data points, obtained by sampling or experimentation, which represent the values of a function for a limited number of values of the independent variable. It is often required to interpolate (i.e. estimate) the value of that function for an intermediate value of the independent variable. This may be achieved by curve fitting or regression analysis.

In mathematics, extrapolation is the process of estimating, beyond the original observation interval, the value of a variable on the basis of its relationship with another variable. It is similar to interpolation, which produces estimates between known observations, but extrapolation is subject to greater uncertainty and a higher risk of producing meaningless results

For example in Interpolation, If you want that curve to be polynomial there is a Lagrange polynomials method and a Newton Finite difference method. See this paper about XY Interpolation Algorithms:
http://goldberg.berkeley.edu/pubs/XY-Interpolation-Algorithms.pdf
You can find some useful information in these pages:
http://en.wikipedia.org/wiki/Interpolation#Polynomial_interpolation
http://en.wikipedia.org/wiki/Extrapolation http://en.wikipedia.org/wiki/Polynomial_interpolation http://en.wikipedia.org/wiki/Newton_series#Newton_series

Hope this helps...

-
I'm looking to curve fit using Spline (low-degree) polynomial interpolation given some points, and I don't understand Wikipedia's math. – Andrew Jun 16 '13 at 6:09