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

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

Хотя для большинства архитектур алгоритм работает медленнее по сравнению с прямым подходом, он более стабилен в числовом отношении .

Определение

Кривая Безье $B$ (степени $n$, с контрольными точками $\beta _{0},\ldots ,\beta _{n}$) можно записать в форме Бернштейна следующим образом $$B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),$$где $b$ является базисным полиномом Бернштейна $$b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}.$$Кривая в точке $t_{0}$ можно оценить с помощью рекуррентного соотношения $${\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}}$$

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

Более того, кривая Безье $B$ можно разделить в точке $t_{0}$ на две кривые с соответствующими контрольными точками: $${\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}}$$

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

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

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

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

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

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

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

Обозначения

При выполнении расчета вручную полезно записать коэффициенты в схеме треугольника в виде $${\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}}$$Выбирая точку t ₀ для оценки многочлена Бернштейна, мы можем использовать две диагонали схемы треугольника, чтобы построить деление многочлена. $$B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]$$в $$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}]$$и $$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 в 3-мерном пространстве с n + 1 контрольными точками P _i $$\mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]$$с $$\mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},$$мы разбиваем кривую Безье на три отдельных уравнения $${\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 с коэффициентами Бернштейна $${\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}$$в точке t ₀ .

Мы начинаем рекурсию с $${\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}}$$и на второй итерации рекурсия останавливается на $${\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}}$$который является ожидаемым полиномом Бернштейна степени 2 .

Реализации

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

Хаскелл

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 

Питон

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

Ява

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

JavaScript

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

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

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

Intermediate line segments obtained by recursively applying linear interpolation to adjacent points.

{ 	 /* Определение функции 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 .

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

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