В математической области численного анализа , алгоритм де кастельжо является рекурсивным методом оценки полиномов Бернштейна формы или кривых Безье , названной в честь его изобретателя Пола де Кастельжо . Алгоритм Де Кастельжау также можно использовать для разделения одной кривой Безье на две кривые Безье при произвольном значении параметра.
Хотя алгоритм для большинства архитектур медленнее по сравнению с прямым подходом, он более стабилен в числовом отношении .
Кривая Безье (степени , с контрольными точками ) можно записать в форме Бернштейна следующим образом
где является базисным полиномом Бернштейна
Кривая в точке можно оценить с помощью рекуррентного соотношения
Затем оценка в точке можно оценить в операции. Результат дан кем-то
Кроме того, кривая Безье может быть разделен на точку на две кривые с соответствующими контрольными точками:
Вот пример реализации алгоритма Де Кастельжау на Haskell :
deCasteljau :: Double -> [( Double , Double )] -> ( Double , Double ) deCasteljau t [ b ] = b deCasteljau t coefs = deCasteljau t уменьшено, где уменьшено = zipWith ( lerpP t ) coefs ( хвостовые коэффициенты ) lerpP t ( x0 , y0 ) ( x1 , y1 ) = ( lerp t x0 x1 , lerp t y0 y1 ) lerp t a b = t * b + ( 1 - t ) * a
При выполнении расчетов вручную полезно записать коэффициенты в схеме треугольника как
Выбирая точку t 0 для вычисления многочлена Бернштейна, мы можем использовать две диагонали треугольной схемы для построения деления многочлена
в
а также
Мы хотим вычислить многочлен Бернштейна степени 2 с коэффициентами Бернштейна
в точке t 0 .
Начнем рекурсию с
и на второй итерации рекурсия останавливается на
который является ожидаемым многочленом Бернштейна степени 2 .
При оценке кривой Безье степени n в трехмерном пространстве с n + 1 контрольными точками P i
с участием
мы разбиваем кривую Безье на три отдельных уравнения
которые мы оцениваем индивидуально с помощью алгоритма Де Кастельжау.
Геометрическая интерпретация алгоритма Де Кастельжау проста.
- Рассмотрим кривую Безье с контрольными точками . Соединяя последовательные точки, мы создаем контрольный многоугольник кривой.
- Теперь разделите каждый линейный сегмент этого многоугольника с соотношением и соедините полученные баллы. Таким образом, вы придете к новому многоугольнику, имеющему на один сегмент меньше.
- Повторяйте процесс, пока не дойдете до единственной точки - это точка кривой, соответствующая параметру. .
На следующем рисунке показан этот процесс для кубической кривой Безье:
Обратите внимание, что построенные промежуточные точки фактически являются контрольными точками для двух новых кривых Безье, обе точно совпадают со старой. Этот алгоритм не только оценивает кривую при, но разбивает кривую на две части при , и предоставляет уравнения двух кривых в форме Безье.
Приведенная выше интерпретация верна для нерациональной кривой Безье. Чтобы оценить рациональную кривую Безье в, мы можем спроецировать точку в ; например, кривая в трех измерениях может иметь свои контрольные точки и веса проецируется на взвешенные контрольные точки . Затем алгоритм работает как обычно, интерполируя в. Полученные четырехмерные точки можно спроецировать обратно в трехмерное пространство с перспективным разделением .
В общем случае операции на рациональной кривой (или поверхности) эквивалентны операциям на нерациональной кривой в проективном пространстве . Такое представление в виде «взвешенных контрольных точек» и весов часто удобно при оценке рациональных кривых.