Алгоритм де Кастельє

В обчислювальній математиці алгоритм де Кастельє (або також алгоритм де Кастельжо), названий на честь його винахідника ^[en] — рекурсивний метод визначення форми поліномів Бернштейна або кривих Безьє. Алгоритм де Кастельє також може бути використаний для поділу кривої Безьє на дві частини за довільним значенням параметра ${\displaystyle (t)}$.

Перевагою алгоритму є його вища обчислювальна стійкість у порівнянні з прямим методом.

Опис

Заданий многочлен Бернштейна B ступеня n з опорними точками ${\displaystyle \beta _{0},\ldots ,\beta _{n}}$

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

де b — базис многочлена Бернштейна, многочлен в точці t₀ може бути визначений за допомогою рекурентного співвідношення:

${\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 n}$ кроків алгоритму. Результат ${\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 :: Double -> [(Double, Double)] -> (Double, Double) deCasteljau t [b] = b deCasteljau t coefs = deCasteljau t reduced  where  reduced = zipWith (lerpP t) coefs (tail coefs)  lerpP t (x0, y0) (x1, y1) = (lerp t x0 x1, lerp t y0 y1)  lerp t a b = t * b + (1 - t) * a 

Примітки

При виконанні розрахунків вручну корисно записати коефіцієнти у вигляді трикутної схеми:

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

При виборі точки t₀ для розбиття поліному Бернштейна ми можемо використовувати дві діагоналі трикутної схеми, щоб побудувати поділ поліному

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

у точці t₀.

Почнемо рекурсію з

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

Крива Безьє

При оцінці кривої Безьє ступеня N в 3-вимірному просторі з N+1 опорною точкою P_i

${\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 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}}$. Отримані чотиривимірні точки можуть бути спроектовані назад в тривимірний простір за допомогою перспективного ділення (однорідні координати точки діляться на «вагу» ${\displaystyle \{w_{i}\}}$).

У цілому, операції з раціональними кривими (або поверхнями) еквівалентні операціям з нераціональними кривими в проективному просторі. Представлення опорних точок як «вагових» часто буває зручно для визначення раціональних кривих.

Посилання

• Реалізація на c++ [ 19 грудня 2014 у Wayback Machine.]
• Адаптивне розбиття кривих Безьє [ 22 жовтня 2014 у Wayback Machine.]

Див. також

• Крива Безьє
• Поліноми Бернштейна
• П'єр Безьє

Література

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd.