Алгоритм де Кастеляуса - De Casteljaus algorithm

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

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

Определение

Кривая Безье B (степени п, с контрольными точками ${\displaystyle \beta _{0},\ldots ,\beta _{n}}$) можно записать в форме Бернштейна следующим образом

${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t)}$,

куда б это Базисный многочлен Бернштейна

${\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}}$.

Кривая в точке т₀ можно оценить с помощью отношение повторения

${\displaystyle \beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n}$

${\displaystyle \beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0}{\mbox{ , }}i=0,\ldots ,n-j{\mbox{ , }}j=1,\ldots ,n}$

Затем оценка ${\displaystyle B}$ в точке ${\displaystyle t_{0}}$ можно оценить в ${\displaystyle {\binom {n}{2}}}$ операции. Результат ${\displaystyle B(t_{0})}$ дан кем-то:

${\displaystyle B(t_{0})=\beta _{0}^{(n)}.}$

Кроме того, кривая Безье ${\displaystyle B}$ может быть разделен на точку ${\displaystyle t_{0}}$ на две кривые с соответствующими контрольными точками:

${\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}$

${\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}$

Пример реализации

Вот пример реализации алгоритма Де Кастельжау в Haskell:

DeCasteljau :: Двойной -> [(Двойной, Двойной)] -> (Двойной, Двойной)DeCasteljau т [б] = бDeCasteljau т Coefs = DeCasteljau т уменьшенный  куда    уменьшенный = zipWith (lerpP т) Coefs (хвост Coefs)    lerpP т (x0, y0) (x1, y1) = (лерп т x0 x1, лерп т y0 y1)    лерп т а б = т * б + (1 - т) * а

Примечания

При расчете вручную полезно записывать коэффициенты в схеме треугольника как

${\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){\mbox{ , }}\qquad t\in [0,1]}$

в

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right){\mbox{ , }}\qquad 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){\mbox{ , }}\qquad t\in [t_{0},1]}$

Пример

Мы хотим вычислить многочлен Бернштейна степени 2 с коэффициентами Бернштейна

${\displaystyle \beta _{0}^{(0)}=\beta _{0}}$

${\displaystyle \beta _{1}^{(0)}=\beta _{1}}$

${\displaystyle \beta _{2}^{(0)}=\beta _{2}}$

в момент т₀.

Начнем рекурсию с

${\displaystyle \beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}t_{0}}$

${\displaystyle \beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}=\beta _{1}(1-t_{0})+\beta _{2}t_{0}}$

и на второй итерации рекурсия останавливается на

${\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}}}$

который является ожидаемым многочленом Бернштейна степени2.

Кривая Безье

Кривая Безье

При оценке кривой Безье степени п в трехмерном пространстве с п+1 контрольная точка п_я

${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$

с

${\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}}}$.

мы разбиваем кривую Безье на три отдельных уравнения

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$

${\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}$

которые мы оцениваем индивидуально, используя алгоритм Де Кастельжау.

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

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

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

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

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

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

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

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

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

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

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

внешняя ссылка

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