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

Метод вычисления полиномов в форме Бернштейна

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

Хотя алгоритм работает медленнее для большинства архитектур по сравнению с прямым подходом, он более стабилен в числовом отношении . ^{[ нужна цитата ]}

Определение

Кривая Безье (степени с контрольными точками ) может быть записана в форме Бернштейна следующим образом: где – базисный полином Бернштейна. Кривая в точке может быть вычислена с помощью рекуррентного соотношения ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle \beta _{0},\ldots ,\beta _{n}}$ $${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),}$$ ${\displaystyle b}$ $${\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}.}$$ ${\displaystyle t_{0}}$ $${\displaystyle {\begin{aligned}\beta _{i}^{(0)}&:=\beta _{i},&&i=0,\ldots ,n\\\beta _{i}^{(j)}&:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0},&&i=0,\ldots ,n-j,\ \ j=1,\ldots ,n\end{aligned}}}$$

Затем оценку в точке можно оценить в операциях. Результат дается ${\displaystyle B}$ ${\displaystyle t_{0}}$ ${\textstyle {\binom {n}{2}}}$ ${\displaystyle B(t_{0})}$ $${\displaystyle B(t_{0})=\beta _{0}^{(n)}.}$$

Более того, кривую Безье можно разбить в точке на две кривые с соответствующими контрольными точками: ${\displaystyle B}$ ${\displaystyle t_{0}}$ $${\displaystyle {\begin{aligned}&\beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}\\[1ex]&\beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}\end{aligned}}}$$

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

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

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

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

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

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

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

Обозначения

При выполнении вычислений вручную полезно записать коэффициенты в схеме треугольника следующим образом. При выборе точки t ₀ для оценки полинома Бернштейна мы можем использовать две диагонали схемы треугольника, чтобы построить деление многочлена на и $${\displaystyle {\begin{matrix}\beta _{0}&=\beta _{0}^{(0)}&&&\\&&\beta _{0}^{(1)}&&\\\beta _{1}&=\beta _{1}^{(0)}&&&\\&&&\ddots &\\\vdots &&\vdots &&\beta _{0}^{(n)}\\&&&&\\\beta _{n-1}&=\beta _{n-1}^{(0)}&&&\\&&\beta _{n-1}^{(1)}&&\\\beta _{n}&=\beta _{n}^{(0)}&&&\\\end{matrix}}}$$ $${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]}$$ $${\displaystyle B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right)\!,\quad t\in [0,t_{0}]}$$ $${\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right)\!,\quad t\in [t_{0},1].}$$

Кривая Безье

Кривая Безье

При оценке кривой Безье степени n в трехмерном пространстве с n + 1 контрольными точками Pi мы разбиваем кривую Безье на три отдельных уравнения , которые мы оцениваем индивидуально _, используя алгоритм Де Кастельжо. $${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]}$$ $${\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},}$$ $${\displaystyle {\begin{aligned}B_{1}(t)&=\sum _{i=0}^{n}x_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{2}(t)&=\sum _{i=0}^{n}y_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{3}(t)&=\sum _{i=0}^{n}z_{i}b_{i,n}(t),&t\in [0,1]\end{aligned}}}$$

Пример

Мы хотим оценить полином Бернштейна степени 2 с коэффициентами Бернштейна в точке t ₀ . $${\displaystyle {\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}}$$

Мы начинаем рекурсию с и на второй итерации рекурсия останавливается на ожидаемом полиноме Бернштейна степени  2 . $${\displaystyle {\begin{aligned}\beta _{0}^{(1)}&&=&&\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}&&=&&\beta _{0}(1-t_{0})+\beta _{1}t_{0}\\[1ex]\beta _{1}^{(1)}&&=&&\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}&&=&&\beta _{1}(1-t_{0})+\beta _{2}t_{0}\end{aligned}}}$$ $${\displaystyle {\begin{aligned}\beta _{0}^{(2)}&=\beta _{0}^{(1)}(1-t_{0})+\beta _{1}^{(1)}t_{0}\\\ &=\beta _{0}(1-t_{0})(1-t_{0})+\beta _{1}t_{0}(1-t_{0})+\beta _{1}(1-t_{0})t_{0}+\beta _{2}t_{0}t_{0}\\\ &=\beta _{0}(1-t_{0})^{2}+\beta _{1}2t_{0}(1-t_{0})+\beta _{2}t_{0}^{2}\end{aligned}}}$$

Реализации

Вот примеры реализации алгоритма Де Кастельжо на различных языках программирования.

Хаскелл

деКастельжау :: Двойной -> [( Двойной , Двойной )] -> ( Двойной , Двойной )        деКастельжо т [ б ] = б    deCasteljau t coefs = deCasteljau t уменьшенный       где уменьшенный = zipWith ( lerpP t ) коэфы ( хвостовые коэфы )        lerpP t ( x0 , y0 ) ( x1 , y1 ) = ( lerp t x0 x1 , lerp t y0 y1 )               lerp т а б знак равно т * б + ( 1 - т ) * а             

Питон

def  de_casteljau ( t :  float ,  coefs :  list [ float ])  ->  float : """Алгоритм Де Кастельжо.""" бета  =  коэф . copy ()  # значения в этом списке переопределяются n  =  len ( бета ) для  j  в  диапазоне ( 1 ,  n ): для  k  в  диапазоне ( n  -  j ): бета [ k ]  =  бета [ k ]  *  ( 1  -  t )  +  бета [ k  +  1 ]  *  t вернуть  бета [ 0 ]

Джава

public double deCasteljau ( двойной t , двойной [] коэффициенты ) {       двойной [] бета = коэффициенты ;    int n = бета . длина ;    для ( int я знак равно 1 ; я <= n ; я ++ ) {          для ( int j знак равно 0 ; j < ( n - я ); j ​​++ ) {            бета [ j ] = бета [ j ] * ( 1 - т ) + бета [ j + 1 ] * т ;             } } вернуть бета [ 0 ] ; }

JavaScript

Следующая функция применяет алгоритм Де Кастельжо к массиву points, определяя конечную среднюю точку с дополнительными свойствами inи out(для касательных «входа» и «выхода» средней точки соответственно).

функция де Кастельжау ( точки , позиция = 0,5 ) {     пусть a , b , средние точки = [];     в то время как ( точки . длина > 1 ) {    const num = очки . длина - 1 ;     для ( пусть я знак равно 0 ; я < число ; ++ я ) {         а = точки [ я ];  б = баллы [ я + 1 ];  средние точки . толкать ([a [ 0 ] + (( b [ 0 ] - a [ 0 ]) * позиция ),      a [ 1 ] + (( b [ 1 ] - a [ 1 ]) * позиция ),      ]);}точки = средние точки ;  средние точки = [];  }вернуть Объект . назначить ( точки [ 0 ], { in : a , out : b });     }

В следующем примере эта функция вызывается с зелеными точками внизу, ровно на середине кривой. Полученные координаты должны равняться или положению самой центральной красной точки. ${\displaystyle (192,32)}$

Промежуточные сегменты линий, полученные путем рекурсивного применения линейной интерполяции к соседним точкам.

{ /* Определение функции deCasteljau() опущено для краткости */ const nodes = window . документ . querySelectorAll ( "circle.n0-point" ); константные точки = Массив . из ( узлов ). карта (({ cx , cy }) => [ cx .baseVal . value , cy . baseVal . value ]) ; де Кастельжо ( очки ); // Результат: [192, 32] }           

Смотрите также

• Кривые Безье
• Алгоритм Де Бура
• Схема Хорнера для оценки полиномов в мономиальной форме
• Алгоритм Кленшоу для вычисления полиномов в форме Чебышева

Рекомендации

• Фарин, Джеральд Э.; Хансфорд, Дайан (2000). Основы CAGD . Натик, Массачусетс: АК Питерс. ISBN 978-1-56881-123-9.

Внешние ссылки

• Кусочно-линейная аппроксимация кривых Безье - описание алгоритма Де Кастельжо, включая критерий определения момента остановки рекурсии
• Кривые Безье и Пикассо — Описание и иллюстрация алгоритма Де Кастельжо, примененного к кубическим кривым Безье.
• Алгоритм де Кастельжо — помощь по реализации и интерактивная демонстрация алгоритма.