De Casteljau's Algorithm

De Casteljau's algorithm, named for its creator Paul de Casteljau, is a recursive numerical method for evaluating a Bezier curve, or equivalently a polynomial written in Bernstein form, at a chosen parameter value. It works by repeated linear interpolation: given a curve's control points, the algorithm connects them with line segments and marks the point on each segment that divides it in the ratio t to 1 minus t for the chosen parameter t, then repeats the same construction on this new, smaller set of points, and continues doing so until only a single point remains, which is the curve's exact position at that value of t. The same recursive construction can also split one Bezier curve into two shorter Bezier curves at an arbitrary parameter value rather than only evaluating a point on it. Because it relies only on repeated linear interpolation rather than directly evaluating a high-degree polynomial, de Casteljau's algorithm is numerically stable even though its computational cost, proportional to the square of the number of control points for each dimension, is higher than that of some faster but less stable evaluation methods.