Computing Bezier curve of a high order

I have a set of ten points that much be used to compute a bezier curve. As you are probably aware, computing a bezier curve of order 9 is a very strenuous activity. I need it in polynomial form. I found this section in the wikipedia article on Bezier curves, but it cautioned against using this polynomial formula for higher order curves:

\begin{align} \begin{split} B(t) =& \sum \limits_{j=0}^{n}t^{j}C_{j} \\ \text{where} \\ C_j =& \frac{n!}{(n - j)!} \sum \limits_{i=0}^{j} \frac{(-1)^{i+j}P_{i}}{i!(j - i)!} \end{split} \end{align}

This could be practical if $C_j$ can be computed prior to many evaluations of $B(t)$; however one should use caution as high order curves may lack numeric stability (de Casteljau's algorithm should be used if this occurs).

My question is therefore, what is the standard way to compute a higher order bezier curve in polynomial form and if so, how?

• This post suggests I use De Casteljau's algorithm to compute Bezier curves – Richard Slabbert Apr 9 '16 at 8:42
• The de Casteljau algorithm is for calculating a point on a Bezier curve, assuming you know its control points. Your problem (if I understand it correctly) is to compute the control points, given some points that it must pass through. The de Casteljau algorithm won't help with this latter problem. – bubba Apr 10 '16 at 4:07

I found the method to construct a set of Bezier curves in my numerical methods textbook, Numerical Analysis by Burden, Faires, and Burden (10E).

I split the points to create three connected cubic Bezier curves $C_0$, $C_1$, and $C_2$ in parametric form, where $C_i$ is represented by

\begin{align} (x_{i}(t), y_{i}(t)) &= (a_{0}^{(i)} + a_{1}^{(i)}t + a_{2}^{(i)}t^{2} + a_{3}^{(i)}t^{3}, b_{0}^{(i)} + b_{1}^{(i)}t + b_{2}^{(i)}t^{2} + b_{3}^{(i)}t^{3}) \end{align}

for $0 \leq t \leq 1$, as determined by the left endpoint $(x_i, y_i)$, left guidepoint $(x_{i}^{+}, y_{i}^{+})$, right endpoint $(x_{i+1}, y_{i+1})$, and right guidepoint $(x_{i+1}^{-}, y_{i+1}^{-})$ for each $i = 0, 1, 2$. \begin{align} a_{0}^{(i)} &= x_i \\ a_{1}^{(i)} &= 3(x_{i}^{+} - x_i) \\ a_{2}^{(i)} &= 3(x_i + x_{i+1}^{-} - 2x_{i}^{+}) \\ a_{3}^{(i)} &=x_{i+1} - x_i + 3x_{i}^{+} - 3x_{i+1}^{-} \end{align}

Your algorithm constructs a cubic spline, which is a string of three cubic Bezier curves joined end-to-end. If you care about the smoothness of the joins, you will need some conditions to ensure this.

In your original question, it's not clear which computation you're worried about. Is it

1. Calculating the control points of the Bezier curve from the given data points, or
2. Converting from Bezier form to "power basis" form, or
3. Calculating points on the curve, once it has been constructed

The de Casteljau algorithm's purpose is #3.

All of these have some danger of numerical stability problems, but I wouldn't expect the problems to be very significant when the curve degree is only around 10.

If you want a polynomial curve (expressed using the power basis), then you don't need to use Bezier curves at all. Just compute the power basis coefficients by directly interpolating the given data points. This involves solving a linear system of equations, which might lead to numerical instabilities. But, again, in a $10 \times 10$ system, I wouldn't expect very big problems.

• ...depends on the configuration of the ten points of course. OP unfortunately did not show even a picture. – J. M. is a poor mathematician Apr 10 '16 at 4:35