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

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

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

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

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

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

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

Тогда определение в точке может быть определено в шагов алгоритма. Результат дан по:

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

Геометрическая интерпретация[править | править вики-текст]

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

  • Задана кривая Безье с опорными точками . Соединив последовательно опорные точки с первой по последнюю, получаем ломаную линию.
  • Разделяем каждый полученный отрезок этой ломаной в соотношении и соединяем полученные точки. В результате получаем ломаную линию с количеством отрезков, меньшим на один, чем исходная ломаная линия.
  • Повторяем процесс до тех пор, пока не получим единственную точку. Эта точка и будет являться точкой на заданной кривой Безье с параметром .

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

DeCasteljau1.svg

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

Описанный алгоритм справедлив для нерациональных кривых Безье. Для вычисления рациональных кривых в , можно спроецировать точку в ; например кривая в трехмерном пространстве должна иметь опорные точки и веса спроецированные в весовые контрольные точки . Затем обычно алгоритм переходит к интерполяции в . Результирующие четырехмерные точки могут быть спроецированы обратно в трехмерное пространство с помощью перспективного деления.

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

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

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