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

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

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

Описание

Задан многочлен Бернштейна B степени n

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

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

${\displaystyle \beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n}$

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

• Адаптивное разбиение кривых Безье

См. также

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