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!
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. 😀
Best Answer
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.