De Casteljau's algorithm ($P_i^{(r)}(t)=(1-t)P_i^{(r-1)}(t)+t{P}_{i+1}^{(r-1)}(t)$)

De Casteljau's algorithm evaluates a Bézier curve by repeated linear interpolation between neighboring control points. Fix $t\in [0,1]$, start with $P_i^{(0)}(t)=P_i$, and computeEach new row has one fewer point. The final point is $P_0^{(n)}(t)=C(t)$. Use the same $t$ at every stage: it describes the fraction of each line segment traversed from its first endpoint toward its second. A cubic Bézier curve needs three levels containing $3$, $2$, and $1$ linear interpolations, respectively.^[ref]

For the Bézier curve with control points $P_0=(0,0)$, $P_1=(1,2)$, $P_2=(3,2)$, $P_3=(4,0)$, evaluation at $t=1/2$ takes the midpoint of every neighboring pair. The first level givesThe second level givesand the third level givesThe intermediate control polygons shrink toward the evaluated point. Each step is a convex combination, giving a geometric explanation of the convex hull property; every step also commutes with an affine map.

The same construction splits the Bézier curve exactly, with no approximation. The outer edges of the triangular array give the new control points: for a cubic, $(P_0,Q_0,R_0,S)$ specify the left piece and $(S,R_1,Q_2,P_3)$ specify the right piece.^[ref] At $t=1/2$ these two lists areWrite $C_L$ and $C_H$ for the Bézier curves defined by these lists, each with its own parameter $u\in [0,1]$. ThenTheir images reproduce the original curve, while their derivatives account for the shorter parameter intervals. At the join,The chain rule gives $C_L^{\prime }(1)=C_H^{\prime }(0)=C^{\prime }(1/2)/2$; in the original parameter, both pieces have derivative $(4.5,0)$. This is the interval scaling in the parametric first-derivative join of Bézier curves.

Repeated midpoint splitting is useful for drawing vector graphics paths: each piece has a smaller control polygon and its own convex hull enclosure. A renderer can refine pieces until they are sufficiently close to line segments at the chosen display scale. Evaluating $C(t)$ and splitting it are thus two results of the same short algorithm.

For a proof outline, expanding the recursion givesPascal's identity proves this by induction; at $r=n$, $i=0$ it is precisely the Bernstein basis formula for the Bézier curve. The geometric construction remains useful even when expanding the polynomial by hand would be cumbersome.

// Target: analysis.bigb