Алгоритм де Кастельжо
В вычислительной математике алгоритм де Кастельжо, названный в честь его изобретателя Поля де Кастельжо — рекурсивный метод определения формы многочленов Бернштейна или кривых Безье. Алгоритм де Кастельжо также может быть использован для разделения кривой Безье на две части по произвольному значению параметра [math]\displaystyle{ (t) }[/math].
Достоинством алгоритма является его более высокая вычислительная устойчивость по сравнению с прямым методом.
Описание
Задан многочлен Бернштейна B степени n
- [math]\displaystyle{ B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t), }[/math]
где b — базис многочлена Бернштейна, многочлен в точке t0 может быть определен с помощью рекуррентного соотношения
- [math]\displaystyle{ \beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n }[/math]
- [math]\displaystyle{ \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 }[/math]
Тогда определение [math]\displaystyle{ B }[/math] в точке [math]\displaystyle{ t_0 }[/math] может быть определено в [math]\displaystyle{ n }[/math] шагов алгоритма. Результат [math]\displaystyle{ B(t_0) }[/math] дан по:
- [math]\displaystyle{ B(t_0)=\beta_0^{(n)}. }[/math]
Также, кривая Безье [math]\displaystyle{ B }[/math] может быть разделена в точке [math]\displaystyle{ t_0 }[/math] на две кривые с соответствующими опорными точками:
- [math]\displaystyle{ \beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)} }[/math]
- [math]\displaystyle{ \beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)} }[/math]
Геометрическая интерпретация
Геометрическая интерпретация алгоритма де Кастельжо проста:
- Задана кривая Безье с опорными точками [math]\displaystyle{ \scriptstyle P_0,...,P_n }[/math]. Соединив последовательно опорные точки с первой по последнюю, получаем ломаную линию.
- Разделяем каждый полученный отрезок этой ломаной в соотношении [math]\displaystyle{ \scriptstyle t : (1-t) }[/math] и соединяем полученные точки. В результате получаем ломаную линию с количеством отрезков, меньшим на один, чем исходная ломаная линия.
- Повторяем процесс до тех пор, пока не получим единственную точку. Эта точка и будет являться точкой на заданной кривой Безье с параметром [math]\displaystyle{ \scriptstyle t }[/math].
Следующая иллюстрация демонстрирует этот процесс для кубической кривой Безье:
Следует заметить, что полученные в процессе построения промежуточные точки являются опорными точками для двух новых кривых Безье, в точности совпадающих с исходной, и в совокупности дающих исходную кривую Безье. Этот алгоритм не только определяет точку кривой в [math]\displaystyle{ \scriptstyle t }[/math], но и делит кривую на две части в [math]\displaystyle{ \scriptstyle t }[/math], а также предоставляет описание двух суб-кривых в форме Безье (в параметрическом представлении).
Описанный алгоритм справедлив для нерациональных кривых Безье. Для вычисления рациональных кривых в [math]\displaystyle{ \scriptstyle \mathbf{R}^n }[/math], можно спроецировать точку в [math]\displaystyle{ \scriptstyle \mathbf{R}^{n+1} }[/math]; например кривая в трехмерном пространстве должна иметь опорные точки [math]\displaystyle{ \scriptstyle \{(x_i, y_i, z_i)\} }[/math] и веса [math]\displaystyle{ \scriptstyle \{w_i\} }[/math] спроецированные в весовые контрольные точки [math]\displaystyle{ \scriptstyle \{(w_ix_i, w_iy_i, w_iz_i, w_i)\} }[/math]. Затем обычно алгоритм переходит к интерполяции в [math]\displaystyle{ \scriptstyle \mathbf{R}^4 }[/math]. Результирующие четырехмерные точки могут быть спроецированы обратно в трехмерное пространство с помощью перспективного деления.
В целом, операции с рациональными кривыми (или поверхностями) эквивалентны операциям с нерациональными кривыми в проективном пространстве. Представление опорных точек как взвешенных часто бывает удобно для определения рациональных кривых.