Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I've got a 2D quadratic Bézier curve which, by construction, is a f(x) function : no loops, a single solution for each defined x.

Is there a common mean to convert this curve to a 3rd degree polynomial ? 3 should be enough since there can only be two "bumps".

Thanks!

share|improve this question
    
There's no reason a cubic polynomial should have the right shape just because it looks similar. Are you okay with an approximation? How good does it need to be, and in what sense? –  Qiaochu Yuan Oct 16 '10 at 11:53
    
I need the curve's extremity values and derivatives to be exact, and the polynomial to be a reasonably close match (perceptively speaking. This is for camera paths.). After investigation, 3rd degree really is not enough, because the 4 constraints (y and dy, both sides) already resolves the 4 parameters, and Bezier curves are more tweakable than that. I'll see what I can do with 4rth degree polynomial. –  Calvin1602 Oct 16 '10 at 14:24
    
I must be missing something (or maybe two things). First, if the curve is a quadratic Bezier curve, then it is certainly a (degenerate) cubic Bezier curve. Secondly, how can a quadratic Bezier curve have "two bumps" ?? A quadratic Bezier curve is a parabola ! –  bubba Jan 8 '13 at 14:05
    
@bubba : my mistake, I meant cubic. –  Calvin1602 Jan 8 '13 at 17:55
add comment

2 Answers

up vote 0 down vote accepted

Well, it turns out it's not really possible.

The following Processing code shows my results for a 4th order polynomial. The equations of the parameters are from Maple.

float x1 = 10;
float y1 = 20;
float x3 = 90;
float y3 = 50;
float d1 = 3;
float d3 = 1;
float f = 40;

float x2 = 30;
float y2 = mouseY;

void draw(){
background(100);
   x2 = mouseX;
   y2 = mouseY;

  noFill();
  stroke(0, 0, 0);
  bezier(x1, y1,  x1+f, y1+f*d1, x3-f, y3-f*d3,    x3,y3);

  stroke(255, 102, 0);

  for (float i=x1; i<x3;i++){
    point(i, approx(i));
  }
}

float approx(float time){
  float a,b,c,d,e;

a = -(8*x1*pow(x3,2)*x2*y1-2*pow(x1,4)*y3+2*pow(x3,4)*y1-pow(x1,2)*d3*pow(x3,3)+2*pow(x1,4)*d3*x3-pow(x1,3)*d3*pow(x3,2)+pow(x1,2)*d1*pow(x3,3)+pow(x1,3)*d1*pow(x3,2)-2*x1*pow(x3,4)*d1-8*x1*pow(x3,2)*x2*y3-8*x3*pow(x1,2)*x2*y3+8*x3*pow(x1,2)*x2*y1-2*pow(x1,3)*x3*x2*d1-2*pow(x3,2)*pow(x1,2)*x2*d1+x3*pow(x1,2)*pow(x2,2)*d1-x3*pow(x1,2)*pow(x2,2)*d3-2*x3*pow(x1,3)*x2*d3+2*x1*pow(x3,3)*x2*d1+x1*pow(x3,2)*pow(x2,2)*d1-x1*pow(x3,2)*pow(x2,2)*d3+2*pow(x1,2)*pow(x3,2)*x2*d3+2*pow(x3,3)*x2*x1*d3+3*pow(x1,3)*pow(x2,2)*d3-2*pow(x1,4)*x2*d3+pow(x1,3)*pow(x2,2)*d1+4*pow(x1,3)*x3*y3+2*pow(x1,4)*y2-2*pow(x3,4)*y2-2*pow(x2,4)*y3+2*pow(x2,4)*y1+4*x1*y3*x3*pow(x2,2)-4*x1*y1*x3*pow(x2,2)+2*pow(x3,4)*x2*d1-3*pow(x3,3)*pow(x2,2)*d1-pow(x3,3)*pow(x2,2)*d3+pow(x2,4)*x3*d3-pow(x2,4)*x1*d3-pow(x2,4)*x1*d1+pow(x2,4)*x3*d1-4*pow(x3,3)*x1*y1+4*pow(x3,3)*x1*y2-4*pow(x3,2)*pow(x1,2)*y1-4*x3*pow(x1,3)*y2-4*pow(x1,2)*pow(x2,2)*y1+4*pow(x1,2)*pow(x2,2)*y3-4*pow(x3,2)*pow(x2,2)*y1+4*pow(x3,2)*pow(x2,2)*y3+4*pow(x3,2)*pow(x1,2)*y3)/((-pow(x3,3)-3*x3*pow(x1,2)+pow(x1,3)+3*x1*pow(x3,2))*(pow(x3,2)*pow(x1,2)-2*x3*pow(x1,2)*x2+pow(x1,2)*pow(x2,2)+4*x1*x3*pow(x2,2)-2*x1*pow(x3,2)*x2-2*x1*pow(x2,3)+pow(x2,4)-2*x3*pow(x2,3)+pow(x3,2)*pow(x2,2)));
b = (y1*pow(x3,5)-pow(x1,2)*pow(x3,4)*d1+2*pow(x1,3)*pow(x3,3)*d1-2*pow(x1,3)*pow(x3,3)*d3+pow(x1,4)*pow(x3,2)*d3+pow(x1,5)*x3*d3-pow(x1,4)*x3*y3-x1*pow(x3,5)*d1+x1*pow(x3,4)*y1-pow(x1,5)*y3-pow(x3,3)*d3*pow(x2,3)+pow(x3,5)*x2*d1-pow(x3,5)*y2-3*pow(x3,3)*d1*pow(x2,3)+pow(x3,2)*pow(x2,4)*d3-3*y3*x3*pow(x2,4)-3*pow(x1,3)*pow(x3,2)*x2*d1-pow(x1,3)*pow(x3,2)*x2*d3-pow(x1,4)*x3*x2*d3+pow(x1,2)*x3*d1*pow(x2,3)+3*pow(x1,2)*pow(x3,3)*x2*d3+pow(x1,2)*pow(x3,3)*x2*d1-pow(x1,2)*x3*d3*pow(x2,3)+x1*pow(x2,4)*x3*d3-x1*pow(x2,4)*x3*d1+2*pow(x2,4)*pow(x3,2)*d1+pow(x1,5)*y2+3*x3*pow(x2,4)*y1-pow(x1,5)*x2*d3+pow(x1,4)*x3*y2+3*pow(x1,3)*d3*pow(x2,3)+pow(x1,3)*d1*pow(x2,3)-2*pow(x1,2)*pow(x2,4)*d3-pow(x1,2)*pow(x2,4)*d1-3*x1*pow(x2,4)*y3-x1*pow(x3,4)*y2+3*x1*pow(x2,4)*y1+x1*pow(x3,4)*x2*d1-x1*pow(x3,2)*d3*pow(x2,3)+x1*pow(x3,2)*d1*pow(x2,3)+4*pow(x3,2)*y3*pow(x2,3)-12*pow(x1,2)*y3*pow(x3,2)*x2+12*pow(x1,2)*y1*pow(x3,2)*x2+4*x1*x3*pow(x2,3)*y3-4*x1*x3*pow(x2,3)*y1+8*pow(x1,3)*y3*pow(x3,2)-8*pow(x1,3)*pow(x3,2)*y2+4*pow(x1,2)*y3*pow(x2,3)-4*pow(x1,2)*y1*pow(x2,3)-8*pow(x1,2)*pow(x3,3)*y1+8*pow(x1,2)*pow(x3,3)*y2-4*pow(x3,2)*pow(x2,3)*y1)/((-x3+x1)*(pow(x3,2)*pow(x1,4)-2*pow(x1,4)*x3*x2+pow(x1,4)*pow(x2,2)-2*pow(x3,3)*pow(x1,3)+2*pow(x1,3)*x3*pow(x2,2)+2*pow(x1,3)*pow(x3,2)*x2-2*pow(x1,3)*pow(x2,3)+pow(x1,2)*pow(x2,4)+2*pow(x1,2)*x3*pow(x2,3)+pow(x3,4)*pow(x1,2)-6*pow(x1,2)*pow(x2,2)*pow(x3,2)+2*pow(x1,2)*pow(x3,3)*x2+2*x1*pow(x3,3)*pow(x2,2)-2*x1*x3*pow(x2,4)-2*x1*pow(x3,4)*x2+2*x1*pow(x3,2)*pow(x2,3)+pow(x2,4)*pow(x3,2)-2*pow(x3,3)*pow(x2,3)+pow(x3,4)*pow(x2,2)));
c = -(pow(x1,3)*pow(x3,4)*d1-pow(x1,4)*pow(x3,3)*d3+pow(x1,5)*pow(x3,2)*d3-2*pow(x1,5)*x3*y3-pow(x1,2)*pow(x3,5)*d1+2*pow(x1,4)*d3*pow(x2,3)+2*y1*pow(x3,5)*x1-2*x1*pow(x3,5)*y2+pow(x3,5)*pow(x2,2)*d1-2*d1*pow(x3,4)*pow(x2,3)-2*pow(x1,2)*pow(x2,4)*x3*d1-pow(x1,2)*pow(x2,4)*x3*d3-pow(x1,4)*x3*pow(x2,2)*d3+x1*pow(x3,4)*pow(x2,2)*d1+pow(x3,3)*pow(x1,2)*pow(x2,2)*d1+3*pow(x3,3)*pow(x1,2)*pow(x2,2)*d3-pow(x3,2)*pow(x1,3)*pow(x2,2)*d3-3*pow(x3,2)*pow(x1,3)*pow(x2,2)*d1+2*pow(x3,2)*pow(x2,4)*x1*d3+pow(x3,2)*pow(x2,4)*x1*d1+pow(x3,3)*pow(x2,4)*d1-pow(x1,3)*pow(x2,4)*d3-pow(x1,5)*pow(x2,2)*d3+2*pow(x1,5)*x3*y2-6*x3*x1*pow(x2,4)*y3+6*x3*x1*pow(x2,4)*y1+2*pow(x1,3)*x3*d1*pow(x2,3)+2*pow(x1,3)*x3*d3*pow(x2,3)+2*pow(x1,2)*pow(x3,2)*d1*pow(x2,3)-2*pow(x1,2)*pow(x3,2)*d3*pow(x2,3)-2*x1*pow(x3,3)*d3*pow(x2,3)-2*x1*pow(x3,3)*d1*pow(x2,3)+8*y3*pow(x2,3)*x3*pow(x1,2)+8*y3*pow(x2,3)*x1*pow(x3,2)-8*y1*pow(x2,3)*x3*pow(x1,2)-8*y1*pow(x2,3)*x1*pow(x3,2)-12*pow(x1,2)*pow(x3,2)*pow(x2,2)*y3+12*pow(x1,2)*pow(x3,2)*pow(x2,2)*y1+4*pow(x1,4)*pow(x3,2)*y3-4*pow(x1,4)*pow(x3,2)*y2-4*pow(x1,2)*pow(x3,4)*y1+4*pow(x1,2)*pow(x3,4)*y2)/((-x3+x1)*(pow(x3,2)*pow(x1,4)-2*pow(x1,4)*x3*x2+pow(x1,4)*pow(x2,2)-2*pow(x3,3)*pow(x1,3)+2*pow(x1,3)*x3*pow(x2,2)+2*pow(x1,3)*pow(x3,2)*x2-2*pow(x1,3)*pow(x2,3)+pow(x1,2)*pow(x2,4)+2*pow(x1,2)*x3*pow(x2,3)+pow(x3,4)*pow(x1,2)-6*pow(x1,2)*pow(x2,2)*pow(x3,2)+2*pow(x1,2)*pow(x3,3)*x2+2*x1*pow(x3,3)*pow(x2,2)-2*x1*x3*pow(x2,4)-2*x1*pow(x3,4)*x2+2*x1*pow(x3,2)*pow(x2,3)+pow(x2,4)*pow(x3,2)-2*pow(x3,3)*pow(x2,3)+pow(x3,4)*pow(x2,2)));
d = (3*x1*pow(x3,2)*pow(x2,4)*y1+2*x3*d3*pow(x1,4)*pow(x2,3)-pow(x3,5)*pow(x1,2)*x2*d1+pow(x3,4)*pow(x1,3)*x2*d1+pow(x3,4)*pow(x1,2)*pow(x2,2)*d1+pow(x3,5)*x1*pow(x2,2)*d1+2*pow(x3,3)*pow(x1,3)*pow(x2,2)*d3-pow(x3,3)*pow(x1,4)*x2*d3-2*pow(x3,3)*pow(x1,3)*pow(x2,2)*d1+pow(x3,3)*pow(x2,4)*x1*d1-pow(x3,2)*pow(x1,4)*pow(x2,2)*d3+pow(x3,2)*pow(x1,5)*x2*d3-x3*pow(x1,5)*pow(x2,2)*d3-3*x3*pow(x1,2)*pow(x2,4)*y3+pow(x3,2)*pow(x1,2)*pow(x2,4)*d3-x3*pow(x1,3)*pow(x2,4)*d3-pow(x3,2)*pow(x1,2)*pow(x2,4)*d1-3*pow(x3,3)*pow(x1,4)*y2-pow(x3,3)*pow(x2,4)*y1-pow(x3,5)*pow(x1,2)*y2+3*pow(x1,3)*pow(x3,4)*y2+pow(x1,3)*pow(x2,4)*y3+pow(x1,5)*pow(x3,2)*y2-2*y3*pow(x1,4)*pow(x2,3)+y3*pow(x1,5)*pow(x2,2)+2*y1*pow(x3,4)*pow(x2,3)-y1*pow(x3,5)*pow(x2,2)-2*y3*pow(x1,5)*x3*x2+y3*x3*pow(x1,4)*pow(x2,2)-2*x1*d1*pow(x3,4)*pow(x2,3)-y1*x1*pow(x3,4)*pow(x2,2)+2*y1*pow(x3,5)*x2*x1+pow(x1,3)*pow(x3,2)*d1*pow(x2,3)-pow(x1,3)*pow(x3,2)*d3*pow(x2,3)+pow(x1,2)*pow(x3,3)*d1*pow(x2,3)-pow(x1,2)*pow(x3,3)*d3*pow(x2,3)+4*pow(x1,4)*pow(x3,2)*y3*x2-4*pow(x1,2)*pow(x3,4)*y1*x2-4*pow(x1,2)*pow(x3,2)*pow(x2,3)*y1+4*pow(x1,2)*pow(x3,2)*y3*pow(x2,3)-4*pow(x3,3)*x1*pow(x2,3)*y1+8*pow(x3,3)*pow(x1,2)*pow(x2,2)*y1+4*pow(x1,3)*x3*pow(x2,3)*y3-8*pow(x1,3)*pow(x3,2)*pow(x2,2)*y3)/((-x3+x1)*(pow(x3,2)*pow(x1,4)-2*pow(x1,4)*x3*x2+pow(x1,4)*pow(x2,2)-2*pow(x3,3)*pow(x1,3)+2*pow(x1,3)*x3*pow(x2,2)+2*pow(x1,3)*pow(x3,2)*x2-2*pow(x1,3)*pow(x2,3)+pow(x1,2)*pow(x2,4)+2*pow(x1,2)*x3*pow(x2,3)+pow(x3,4)*pow(x1,2)-6*pow(x1,2)*pow(x2,2)*pow(x3,2)+2*pow(x1,2)*pow(x3,3)*x2+2*x1*pow(x3,3)*pow(x2,2)-2*x1*x3*pow(x2,4)-2*x1*pow(x3,4)*x2+2*x1*pow(x3,2)*pow(x2,3)+pow(x2,4)*pow(x3,2)-2*pow(x3,3)*pow(x2,3)+pow(x3,4)*pow(x2,2)));
e = (pow(x3,3)*y1-pow(x1,3)*y3-x1*pow(x3,3)*d1+pow(x1,2)*pow(x3,2)*d1-3*pow(x3,2)*y1*x1-pow(x3,2)*d3*pow(x1,2)+pow(x1,3)*x3*d3+3*x3*y3*pow(x1,2)+x3*d3*pow(x2,3)+pow(x3,3)*x2*d1-2*pow(x3,2)*pow(x2,2)*d1-pow(x3,2)*pow(x2,2)*d3+3*y3*x3*pow(x2,2)-3*y1*x3*pow(x2,2)+x3*d1*pow(x2,3)-pow(x3,3)*y2-2*y3*pow(x2,3)+2*y1*pow(x2,3)-2*pow(x1,2)*x3*x2*d1-pow(x1,2)*x3*x2*d3+x1*pow(x3,2)*x2*d1+2*x1*pow(x3,2)*x2*d3-x1*x3*pow(x2,2)*d3+6*x1*y1*x3*x2-6*x1*y3*x3*x2+x1*x3*pow(x2,2)*d1-x1*d1*pow(x2,3)+3*x1*y3*pow(x2,2)-3*x1*y1*pow(x2,2)+3*x1*pow(x3,2)*y2-pow(x1,3)*x2*d3+2*pow(x1,2)*pow(x2,2)*d3+pow(x1,2)*pow(x2,2)*d1-3*pow(x1,2)*x3*y2-x1*d3*pow(x2,3)+pow(x1,3)*y2)/(-pow(x2,4)*pow(x3,3)+pow(x1,5)*pow(x3,2)-3*pow(x1,4)*pow(x3,3)-pow(x3,5)*pow(x2,2)-pow(x1,2)*pow(x3,5)+3*pow(x1,3)*pow(x3,4)+pow(x2,4)*pow(x1,3)+pow(x1,5)*pow(x2,2)+2*pow(x3,4)*pow(x2,3)-2*pow(x1,4)*pow(x2,3)+3*pow(x2,4)*x1*pow(x3,2)-8*pow(x1,3)*pow(x3,2)*pow(x2,2)+2*pow(x3,5)*x2*x1-3*pow(x2,4)*x3*pow(x1,2)-x1*pow(x3,4)*pow(x2,2)+x3*pow(x1,4)*pow(x2,2)+4*pow(x1,4)*pow(x3,2)*x2-4*pow(x1,2)*pow(x3,4)*x2+8*pow(x3,3)*pow(x1,2)*pow(x2,2)-2*pow(x1,5)*x3*x2+4*pow(x1,3)*x3*pow(x2,3)-4*pow(x3,3)*x1*pow(x2,3));
  return 
  e*time*time*time*time+
  a*time*time*time+
  b*time*time+
  c*time+
  d;   
}

I'll try with adding the derivative of x2 and adding another point in the middle (with a 5rth order polynomial) but I'm not sure it'll appropriate for my use.

share|improve this answer
    
Wow, what heck is that? –  muntoo Mar 15 '11 at 1:10
    
@muntoo : It's an approximation of a Bezier curve using a 4th degree polynomial, given the starting point, the end point, another point in the middle, and two derivatives. Equations are computed by Maple. But yeah it's ugly. –  Calvin1602 Mar 15 '11 at 8:03
add comment

I assume you want a polynomial function $y=f(x)$ that has the same shape as your original parametric cubic Bezier curve.

Well, you already have $y$ as a function of $x$, but the function is unpleasant. For a given value of $x$, there is no closed form formula for the corresponding $y$ -- you have to find $y$ numerically (by intersecting a vertical line with the given Bezier curve).

Let's denote this unpleasant function by $y=g(x)$. So, now the problem is just to approximate $g$ by a polynomial $f$. There are lots of standard ways to do this, depending on how you want to measure the approximation error and what extra conditions you want $f$ to satisfy. You say you want exact matching of end points and end tangents.

So, you choose a degree $m$ for $f$. As you say, $m$ will have to be bigger than 4. Then $f$ will have $m+1$ coefficients, which you can determine by solving a system of $m+1$ linear equations. You get 4 equations from the end-point constraints. Pick another $m-3$ points $(x_i,y_i)$ in the interior of the curve, and, for each $i$, write down the equation that expresses the requirement that $y_i = f(x_i)$. Solve the system of linear equations.

One subtlety is that the extra $m-3$ points have to be chosen fairly carefully. You can't just distribute them uniformly, or else $f$ might wiggle badly. They have to be more dense towards the ends of the curve, and less dense in the middle. The "Chebyshev nodes" are a good choice.

This process is called Hermite interpolation if you use derivative information, and Lagrange interpolation if you don't. Both are covered in Wikipedia articles.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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