Алгоритм де Кастельжо

В вычислительной математике алгоритм де Кастельжо, названный в честь его изобретателя Поля де Кастельжо — рекурсивный метод определения формы многочленов Бернштейна или кривых Безье. Алгоритм де Кастельжо также может быть использован для разделения кривой Безье на две части по произвольному значению параметра $(t)$.

Достоинством алгоритма является его более высокая вычислительная устойчивость по сравнению с прямым методом.

Описание

Дан многочлен B в форме Бернштейна степени n

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

где b — базис многочлена Бернштейна, многочлен в точке t₀ может быть определен с помощью рекуррентной последовательности

$\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$

Тогда определение $B$ в точке $t_{0}$ может быть определено в $n$ шагов алгоритма. Результат $B(t_{0})$ дан по:

$B(t_{0})=\beta _{0}^{(n)}.$

Geometric interpretation

Геометрическая интерпретация алгоритма де Кастельжо прямая:

• Относительно кривой Безье с контрольными точками $\scriptstyle P_{0},...,P_{n}$. Соединем последовательность контрольных точек с первой по последнюю, создавая ломаную линию.
• Разделяем каждую полученную сторону этой ломаной в соотношении $\scriptstyle t:(1-t)$ и соединяем полученные точки. В результате получаем ломаную линию с количеством отрезков, меньшим на один, чем исходная ломаная линия.
• Повторяем процесс до тех пор, пока не получим точку. Эта точка и будет являться точкой заданной кривой Безье с параметром $\scriptstyle t$.

Слеюующая иллюстрация демонстрирует этот процесс для кубической кривой Безье:

Обратите внимание, что полученные в процессе промежуточные точки являются контрольными точками для двух новых кривых Безье, в точности совпадающих с исходной и в сумме дающих исходную кривую Безье. Этот алгоритм не только определяет точку кривой в $\scriptstyle t$, но и делит кривую на две части в $\scriptstyle t$, а также предоставляет описание двух суб-кривых в форме Безье.

Описанный алоритм справедлив для нерациональных кривых Безье. Для вычисления рациональных кривых в $\scriptstyle \mathbf {R} ^{n}$, можно спроецировать точку в $\scriptstyle \mathbf {R} ^{n+1}$; например кривая в трехмерном пространстве должна иметь опорные точки $\scriptstyle \{(x_{i},y_{i},z_{i})\}$ и веса $\scriptstyle \{w_{i}\}$ спроецированные в весовые контрольные точки $\scriptstyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$. Затем обычно алгоритм переходит к интерполяции в $\scriptstyle \mathbf {R} ^{4}$.

The interpretation given above is valid for a nonrational Bezier curve. To evaluate a rational Bezier curve in $\scriptstyle \mathbf {R} ^{n}$, we may project the point into $\scriptstyle \mathbf {R} ^{n+1}$; for example, a curve in three dimensions may have its control points $\scriptstyle \{(x_{i},y_{i},z_{i})\}$ and weights $\scriptstyle \{w_{i}\}$ projected to the weighted control points $\scriptstyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$. The algorithm then proceeds as usual, interpolating in $\scriptstyle \mathbf {R} ^{4}$. 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.

Также, кривая Безье $B$ может быть разделена в точке $t_{0}$ на две кривые с соответствующими контрольными точками:

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

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