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

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

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

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

Ссылки

См. также


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Полезное


Смотреть что такое "Алгоритм де Кастельжо" в других словарях:

  • Де Кастельжо, Поль — Поль де Фаже де Кастельжо Paul de Faget de Casteljau Дата рождения: 19 ноября 1930(1930 11 19) (82 года) Место рождения: Безансон Страна …   Википедия

  • Список алгоритмов — Эта страница информационный список. Основная статья: Алгоритм Ниже приводится список алгоритмов, группированный по категориям. Более детальные сведения приводятся в списке структур данных и …   Википедия

  • Кривая Безье — Кривые Безье или Кривые Бернштейна Безье были разработаны в 60 х годах XX века независимо друг от друга Пьером Безье (Pierre Bézier) из автомобилестроительной компании «Рено» и Полем де Кастельжо (Paul de Faget de Casteljau) из компании «Ситроен» …   Википедия

  • Многочлен Бернштейна — В вычислительной математике многочлены Бернштейна это алгебраические многочлены, представляющие собой линейную комбинацию базисных многочленов Бернштейна. [1] [2] Устойчивым алгоритмом вычисления многочленов в форме Бернштейна является алгоритм… …   Википедия


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»