2
$\begingroup$

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. :D

$\endgroup$
10
  • $\begingroup$ What do you mean about "Backwards" and "the end points don't have any points on the outside? $\endgroup$ – Zeta.Investigator Jun 16 '13 at 5:31
  • $\begingroup$ Have you seen these pages? en.wikipedia.org/wiki/Interpolation and en.wikipedia.org/wiki/Extrapolation $\endgroup$ – Zeta.Investigator Jun 16 '13 at 5:34
  • 1
    $\begingroup$ @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. $\endgroup$ – Patrick Da Silva Jun 16 '13 at 5:53
  • 1
    $\begingroup$ @Andrew : This seems like a cubic (the black line) and the technique is simple polynomial interpolation. You know that I can draw infinitely many curves that go through those precise four points... for instance, given $n$ points on the plane, if you can find a line which is not orthogonal to a segment between two points (this is always possible because it only removes the possibility of finitely many angles), you can rotate the plane so that this line becomes the $x$-axis and then do polynomial interpolation. $\endgroup$ – Patrick Da Silva Jun 16 '13 at 6:24
  • 1
    $\begingroup$ The problem is that if I change this line I change the curve too. Like I mentioned, there is no unique way of drawing a curve going through $n$ points ; you need to specify what properties you want this curve to have. Do you know what properties you want it to have? $\endgroup$ – Patrick Da Silva Jun 16 '13 at 6:25
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ – Andrew Jun 16 '13 at 6:19
  • $\begingroup$ That's a typo. I will fix. $\endgroup$ – marty cohen Jun 16 '13 at 6:34
  • $\begingroup$ 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. $\endgroup$ – Andrew Jun 16 '13 at 7:18
  • $\begingroup$ I added some more explanation. $\endgroup$ – marty cohen Jun 16 '13 at 17:32
1
$\begingroup$

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...

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.