De Casteljau's algorithm

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.

Although the algorithm is slower for most architectures when compared with the direct approach, it is more numerically stable.

Definition

A Bézier curve B (of degree n, with control points $\beta _{0},\ldots ,\beta _{n}$ ) can be written in Bernstein form as follows

$B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t)$ ,

where b is a Bernstein basis polynomial

$b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}$ .

The curve at point t0 can be evaluated with the recurrence relation

$\beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n$ $\beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0}{\mbox{ , }}i=0,\ldots ,n-j{\mbox{ , }}j=1,\ldots ,n$ Then, the evaluation of $B$ at point $t_{0}$ can be evaluated in ${\binom {n}{2}}$ operations. The result $B(t_{0})$ is given by :

$B(t_{0})=\beta _{0}^{(n)}.$ Moreover, the Bézier curve $B$ can be split at point $t_{0}$ into two curves with respective control points :

$\beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}$ $\beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}$ Example implementation

Here is an example implementation of De Casteljau's algorithm in Haskell:

deCasteljau :: Double -> [(Double, Double)] -> (Double, Double)
deCasteljau t [b] = b
deCasteljau t coefs = deCasteljau t reduced
where
reduced = zipWith (lerpP t) coefs (tail coefs)
lerpP t (x0, y0) (x1, y1) = (lerp t x0 x1, lerp t y0 y1)
lerp t a b = t * b + (1 - t) * a