Algorithm for deriving control points of a bezier curve from points along that curve?

Question

I've been looking for, but obviously not finding, an algorithm that will allow me to plug in a list of x,y coordinates that are known to be along a curve so as to get the 4 control points for a cubic bezier curve spit out.

To be more precise, I'm looking for an algorithm that will give me the two control points required to shape the curve while inputting a series of discrete points including the two control points which determine the start and end of the curve.

Thanks!

Edit: Okay, due to math, an old foe, I need to ask for the bezier curve of best fit to a polynomial function.

Answer 1

So I assume that the endpoints are fixed, and then you have a number of (x,y) sample points that you want to fit with a cubic Bezier.

The number of sample points that you have will determine what approach to take. Let's look through a few cases:

2 points

2 sample points is the simplest case. That gives you a total of 4 points, if you count the end points. This is the number of CVs in a cubic Bezier. To solve this, you need a parameter (t) value for both of the sample points. Then you have a system of 2 equations and 2 points that you need to solve, where the equation is the parametric equation of a Bezier curve at the t values you've chosen.

The t values can be whatever you like, but you will get better results by using either 1/3 and 2/3, or looking at relative distances, or relative distances along a baseline, depending on your data.

1 point

This is similar to 2 points, except that you have insufficient information to uniquely determine all your degrees of freedom. What I would suggest is to fit a quadratic Bezier, and then degree elevate. I wrote up a detailed example of quadratic fitting in this question.

More than 2 points

In this case, there isn't a unique solution. I have used least-squares approximation with good results. The steps are:

• Pick t values for each sample
• Build your system of equations as a matrix
• Optionally add fairing or some other smoothing function
• Solve the matrix with a least-squares solver

There is a good description of these steps in this free cagd textbook, chapter 11. It talks about fitting b-splines, but a cubic bezier is a type of b-spline (knot vector is 0,0,0,1,1,1 and has 4 points).