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

Метод оценки полиномов в форме Бернштейна

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

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

Определение

Кривая Безье (степени , с контрольными точками ) может быть записана в форме Бернштейна следующим образом, где — базисный полином Бернштейна. Кривую в точке можно оценить с помощью рекуррентного соотношения ${\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 контрольными точками P _i мы разбиваем кривую Безье на три отдельных уравнения , которые оцениваем по отдельности с помощью алгоритма Де Кастельжау. $${\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 :: Двойной -> [( Двойной , Двойной )] -> ( Двойной , Двойной )        деКастельжау т [ б ] = б    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.

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

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

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