In the mathematical field of numerical analysis, De Casteljau's algorithm is a recursive method to evaluate polynomials in Bernstein form or Bézier curves, named after its inventor Paul de Casteljau. De Casteljau's algorithm can also be used to split a single Bézier curve into two Bézier curves at an arbitrary parameter value.

The algorithm is numerically stable, where d is the number of dimensions, and n is the number of control points. There exist faster alternatives.

Definition

is a Bernstein basis polynomial can be evaluated with the recurrence relation

Geometric interpretation

The geometric interpretation of De Casteljau's algorithm is straightforward.

• . Connecting the consecutive points we create the control polygon of the curve.

• Now, subdivide each line segment and connect the points you get. This way you arrive at the new polygon having one fewer segment.

• .

The following picture shows this process for a cubic Bézier curve:

, and provides the equations of the two sub-curves in Bézier form.

. The resulting four-dimensional points may be projected back into three-space with a perspective divide.

In general, operations on a rational curve (or surface) are equivalent to operations on a nonrational curve in a projective space. This representation as the "weighted control points" and weights is often convenient when evaluating rational curves.

Notation

When choosing a point t0

Bézier curve

When evaluating a Bézier curve of degree n in 3-dimensional space with n + 1 control points Pi which we evaluate individually using De Casteljau's algorithm.

Example

at the point t0.

which is the expected Bernstein polynomial of degree2.

ImplementationsExample implementation

Here are example implementations of De Casteljau's algorithm in various programming languages.

Haskell (programming language)Haskell

Python (programming language)Python

Java (programming language)Java

Code example in JavaScript

The following JavaScript function applies De Casteljau's algorithm to an array of control points or poles as originally named by De Casteljau to reduce them one by one until reaching a point in the curve for a given t between 0 for the first point of the curve and 1 for the last one

For example,

returns the array which yields the points and segments plotted below:

See also

• Bézier curve

• De Boor's algorithm

• Horner scheme to evaluate polynomials in monomial form

• Clenshaw algorithm to evaluate polynomials in Chebyshev form

References

External links

• Piecewise linear approximation of Bézier curves – description of De Casteljau's algorithm, including a criterion to determine when to stop the recursion

• Bézier Curves and Picasso – description and illustration of De Casteljau's algorithm applied to cubic Bézier curves

• de Casteljau's algorithm – implementation help and interactive demonstration of the algorithm