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

В вычислительной математике алгоритм де Кастельжо, названный в честь его изобретателя Поля де Кастельжо — рекурсивный метод определения формы многочленов Бернштейна или кривых Безье. Алгоритм де Кастельжо также может быть использован для разделения кривой Безье на две части по произвольному значению параметра $(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)}.$

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

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

$\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}$

Геометрическая интерпретация

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

• Задана кривая Безье с опорными точками $\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_ix_i, w_iy_i, w_iz_i, w_i)\}$. Затем обычно алгоритм переходит к интерполяции в $\scriptstyle \mathbf{R}^4$. Результирующие четырехмерные точки могут быть спроецированы обратно в трехмерное пространство с помощью перспективного деления.

В целом, операции с рациональными кривыми (или поверхностями) эквивалентны операциям с нерационалиными кривыми в проективном пространстве. Представление опорных точек как взвешенных часто бывает удобно для определения рациональных кривых.

Ссылки

• Реализация на c++
• Адаптивное разбиение кривых Безье

См. также

• Кривая Безье
• Многочлен Бернштейна
• Кривая
• Поль де Кастельжо
• Пьер Безье
• Сергей Натанович Бернштейн