Алгоритм Де Кастельжау
Метод оценки полиномов в форме Бернштейна

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

Алгоритм численно устойчив [1] по сравнению с прямой оценкой полиномов. Вычислительная сложность этого алгоритма составляет , где d — число измерений, а n — число контрольных точек. Существуют более быстрые альтернативы. [2] [3] О ( г н 2 ) {\displaystyle O(dn^{2})}

Определение

Кривая Безье (степени , с контрольными точками ) может быть записана в форме Бернштейна следующим образом, где — базисный полином Бернштейна. Кривую в точке можно оценить с помощью рекуррентного соотношения Б {\displaystyle Б} н {\displaystyle n} β 0 , … , β н {\displaystyle \beta _{0},\ldots ,\beta _{n}} Б ( т ) = ∑ я = 0 н β я б я , н ( т ) , {\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),} б {\displaystyle б} б я , н ( т ) = ( н я ) ( 1 − т ) н − я т я . {\displaystyle b_{i,n}(t)={n \выберите i}(1-t)^{ni}t^{i}.} т 0 {\displaystyle t_{0}} β я ( 0 ) := β я , я = 0 , … , н β я ( дж ) := β я ( дж − 1 ) ( 1 − т 0 ) + β я + 1 ( дж − 1 ) т 0 , я = 0 , … , н − дж ,     дж = 1 , … , н {\displaystyle {\begin{align}\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 ,nj,\ \ j=1,\ldots ,n\end{align}}}

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

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

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

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

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

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

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

Интерпретация, данная выше, верна для нерациональной кривой Безье. Чтобы оценить рациональную кривую Безье в , мы можем спроецировать точку в ; например, кривая в трех измерениях может иметь свои контрольные точки и веса, спроецированные на взвешенные контрольные точки . Затем алгоритм действует как обычно, интерполируя в . Полученные четырехмерные точки можно спроецировать обратно в трехмерное пространство с перспективным разделением . Р н {\displaystyle \mathbf {R} ^{n}} Р н + 1 {\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})\}} Р 4 {\displaystyle \mathbf {R} ^{4}}

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

Обозначение

При выполнении вычислений вручную полезно записать коэффициенты в схеме треугольника как При выборе точки t 0 для вычисления полинома Бернштейна мы можем использовать две диагонали схемы треугольника для построения деления полинома на и β 0 = β 0 ( 0 ) β 0 ( 1 ) β 1 = β 1 ( 0 ) ⋱ ⋮ ⋮ β 0 ( н ) β н − 1 = β н − 1 ( 0 ) β н − 1 ( 1 ) β н = β н ( 0 ) {\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}}} Б ( т ) = ∑ я = 0 н β я ( 0 ) б я , н ( т ) , т ∈ [ 0 , 1 ] {\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]} Б 1 ( т ) = ∑ я = 0 н β 0 ( я ) б я , н ( т т 0 ) , т ∈ [ 0 , т 0 ] {\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}]} Б 2 ( т ) = ∑ я = 0 н β я ( н − я ) б я , н ( т − т 0 1 − т 0 ) , т ∈ [ т 0 , 1 ] . {\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(ni)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right)\!,\quad t\in [t_{0},1].}

кривая Безье

Кривая Безье

При оценке кривой Безье степени n в трехмерном пространстве с n + 1 контрольными точками P i мы разбиваем кривую Безье на три отдельных уравнения , которые оцениваем по отдельности с помощью алгоритма Де Кастельжау. Б ( т ) = ∑ я = 0 н П я б я , н ( т ) ,   т ∈ [ 0 , 1 ] {\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]} P i := ( x i y i z i ) , {\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},} B 1 ( t ) = ∑ i = 0 n x i b i , n ( t ) , t ∈ [ 0 , 1 ] B 2 ( t ) = ∑ i = 0 n y i b i , n ( t ) , t ∈ [ 0 , 1 ] B 3 ( t ) = ∑ i = 0 n z i b i , n ( t ) , t ∈ [ 0 , 1 ] {\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 0 . β 0 ( 0 ) = β 0 β 1 ( 0 ) = β 1 β 2 ( 0 ) = β 2 {\displaystyle {\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}}

Мы начинаем рекурсию с , а на второй итерации рекурсия останавливается , что является ожидаемым полиномом Бернштейна степени  2 . β 0 ( 1 ) = β 0 ( 0 ) ( 1 − t 0 ) + β 1 ( 0 ) t 0 = β 0 ( 1 − t 0 ) + β 1 t 0 β 1 ( 1 ) = β 1 ( 0 ) ( 1 − t 0 ) + β 2 ( 0 ) t 0 = β 1 ( 1 − t 0 ) + β 2 t 0 {\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}}} β 0 ( 2 ) = β 0 ( 1 ) ( 1 − t 0 ) + β 1 ( 1 ) t 0   = β 0 ( 1 − t 0 ) ( 1 − t 0 ) + β 1 t 0 ( 1 − t 0 ) + β 1 ( 1 − t 0 ) t 0 + β 2 t 0 t 0   = β 0 ( 1 − t 0 ) 2 + β 1 2 t 0 ( 1 − t 0 ) + β 2 t 0 2 {\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 :: Двойной -> [( Двойной , Двойной )] -> ( Двойной , Двойной )        деКастельжау т [ б ] = б    deCasteljau t coefs = deCasteljau t уменьшенный       где уменьшенный = zipWith ( lerpP t ) coefs ( хвостовые 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 ( бета ) для  j  в  диапазоне ( 1 ,  n ): для  k  в  диапазоне ( n  -  j ): бета [ к ]  =  бета [ к ]  *  ( 1  -  t )  +  бета [ к  +  1 ]  *  t возврат  бета [ 0 ]

Ява

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

Пример кода на JavaScript

Следующая функция JavaScript применяет алгоритм Де Кастельжау к массиву контрольных точек или полюсов, как их первоначально назвал Де Кастельжау, чтобы уменьшать их одну за другой до достижения точки на кривой для заданного t между 0 для первой точки кривой и 1 для последней.

функция crlPtReduceDeCasteljau ( точки , t ) {    пусть retArr = [ точки.срез ( ) ] ;      в то время как ( точки . длина > 1 ) {     пусть средние точки = [];   для ( пусть i = 0 ; i + 1 < точек . длина ; ++ i ) {         пусть ax = точки [ i ][ 0 ];   пусть y = точки [ i ][ 1 ];   пусть bx = точки [ i + 1 ][ 0 ];   пусть по = точек [ i + 1 ][ 1 ];    // а * (1-t) + b * t = а + (b - a) * tсредние точки . толкать ([ах + ( bx - ах ) * т ,      ау + ( по - ау ) * т ,      ]);} retArr . push ( средние точки ) точки = средние точки ;  }возврат retArr ; }

Например,

 вар полюсов = [[0, 128], [128, 0], [256, 0], [384, 128] ] crlPtReduceDeCasteljau (полюса, .5)

возвращает массив

 [[[0, 128], [128, 0], [256, 0], [384, 128] ], [[64, 64], [192, 0], [320, 64]], [ [128, 32], [256, 32]], [ [192, 32]], ]

Какие точки и соединяющие их отрезки изображены ниже

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

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

Ссылки

  1. ^ Дельгадо, Х.; Майнар, Э.; Пенья, Х. М. (2023-10-01). «О точности алгоритмов типа де Кастельжау и представлениях Бернштейна». Computer Aided Geometric Design . 106 : 102243. doi : 10.1016/j.cagd.2023.102243. ISSN  0167-8396.
  2. ^ Woźny, Paweł; Chudy, Filip (2020-01-01). "Линейный геометрический алгоритм для оценки кривых Безье". Computer-Aided Design . 118 : 102760. arXiv : 1803.06843 . doi : 10.1016/j.cad.2019.102760. ISSN  0010-4485.
  3. ^ Фуда, Кьяра; Раманантоанина, Андриамахенина; Хорманн, Кай (2024). «Комплексное сравнение алгоритмов оценки рациональных кривых Безье». Dolomites Research Notes on Approximation . 17 (9/2024): 56–78. doi :10.14658/PUPJ-DRNA-2024-3-9. ISSN  2035-6803.
  • Кусочно-линейная аппроксимация кривых Безье – описание алгоритма Де Кастельжау, включая критерий для определения момента остановки рекурсии
  • Кривые Безье и Пикассо — Описание и иллюстрация алгоритма Де Кастельжо, примененного к кубическим кривым Безье.
  • Алгоритм де Кастельжау — помощь в реализации и интерактивная демонстрация алгоритма.
Retrieved from "https://en.wikipedia.org/w/index.php?title=De_Casteljau%27s_algorithm&oldid=1248607052"