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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Описание[править | править вики-текст]

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

B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t),

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

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

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

DeCasteljau1.svg

Следует заметить, что полученные в процессе построения промежуточные точки являются опорными точками для двух новых кривых Безье, в точности совпадающих с исходной, и в совокупности дающих исходную кривую Безье. Этот алгоритм не только определяет точку кривой в \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. Результирующие четырехмерные точки могут быть спроецированы обратно в трехмерное пространство с помощью перспективного деления.

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

Ссылки[править | править вики-текст]

См. также[править | править вики-текст]