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

В обчислювальній математиці алгоритм де Кастельє (або також алгоритм де Кастельжо), названий на честь його винахідника Шаблон:Нп — рекурсивний метод визначення форми поліномів Бернштейна або кривих Безьє. Алгоритм де Кастельє також може бути використаний для поділу кривої Безьє на дві частини за довільним значенням параметра $(t)$.

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

Опис

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

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

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

${\beta }_i^{(0)}:={\beta }_i\text{,}i=0,\dots ,n$

${\beta }_i^{(j)}:={\beta }_i^{(j-1)}(1-t_0)+{\beta }_{i+1}^{(j-1)}{t}_0\text{,}i=0,\dots ,n-j\text{,}j=1,\dots ,n$

Тоді визначення $B$ в точці $t_0$ може бути визначено в $n$ кроків алгоритму. Результат $B(t_0)$ дано за:

$B(t_0)={\beta }_0^{(n)}.$

Також, крива Безьє $B$ може бути розділена в точці $t_0$ на дві криві з відповідними опорними точками:

${\beta }_0^{(0)},{\beta }_0^{(1)},\dots ,{\beta }_0^{(n)}$

${\beta }_0^{(n)},{\beta }_1^{(n-1)},\dots ,{\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

Примітки

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

$\begin{array}{ccccc}{\beta }_0& ={\beta }_0^{(0)}& & & \\ & & {\beta }_0^{(1)}& & \\ {\beta }_1& ={\beta }_1^{(0)}& & & \\ & & & \ddots & \\ ⋮& & ⋮& & {\beta }_0^{(n)}\\ & & & & \\ {\beta }_{n-1}& ={\beta }_{n-1}^{(0)}& & & \\ & & {\beta }_{n-1}^{(1)}& & \\ {\beta }_n& ={\beta }_n^{(0)}& & & \end{array}$

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

$B(t)=\sum _{i=0}^n{\beta }_i^{(0)}{b}_{i,n}(t)\text{ , }t\in [0,1]$

на

$B_1(t)=\sum _{i=0}^n{\beta }_0^{(i)}{b}_{i,n}\left(\frac{t}{t_0}\right)\text{ , }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)\text{ , }t\in [t_0,1]$

Приклад

Ми хочемо розбити поліном Бернштейна 2-го ступеня з коефіцієнтами Бернштейна:

${\beta }_0^{(0)}={\beta }_0$

${\beta }_1^{(0)}={\beta }_1$

${\beta }_2^{(0)}={\beta }_2$

у точці t₀.

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

${\beta }_0^{(1)}={\beta }_0^{(0)}(1-t_0)+{\beta }_1^{(0)}{t}_0={\beta }_0(1-t_0)+{\beta }_1{t}_0$

${\beta }_1^{(1)}={\beta }_1^{(0)}(1-t_0)+{\beta }_2^{(0)}{t}_0={\beta }_1(1-t_0)+{\beta }_2{t}_0$

і друга ітерація рекурсії зупиняється у

$\begin{array}{cc}{\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{array},$

яка очікувано є многочленом Бернштейна ступеня 2.

Крива Безьє

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

$𝐁(t)=\sum _{i=0}^n{𝐏}_i{b}_{i,n}(t)\text{ , }t\in [0,1]$

за

${𝐏}_i:=\left(\begin{array}{c}{x}_i\\ y_i\\ z_i\end{array}\right)$.

ми можемо розбити криву Безьє на три окремі рівняння:

$B_1(t)=\sum _{i=0}^n{x}_i{b}_{i,n}(t)\text{ , }t\in [0,1]$

$B_2(t)=\sum _{i=0}^n{y}_i{b}_{i,n}(t)\text{ , }t\in [0,1]$

$B_3(t)=\sum _{i=0}^n{z}_i{b}_{i,n}(t)\text{ , }t\in [0,1],$

які ми оцінюємо окремо, використовуючи алгоритм де Кастельє.

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

Геометрична інтерпретація алгоритму де Кастельє проста:

• Задана крива Безьє з опорними точками $P_0,...,P_n$. Поєднавши послідовно опорні точки з першої по останню, отримуємо ламану лінію.
• Поділяємо кожний отриманий відрізок цієї ламаної в співвідношенні $t:(1-t)$ та з'єднуємо отримані точки. Внаслідок отримуємо ламану лінію з кількістю відрізків, меншим на один, ніж вихідна ламана лінія.
• Повторюємо процес до тих пір, поки не отримаємо єдину точку. Ця точка і буде точкою на заданій кривій Безьє з параметром $t$.

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

Слід зауважити, що отримані в процесі побудови проміжні точки є опорними точками для двох нових кривих Безьє, що в точності збігаються з вихідною, і в сукупності дають вихідну криву Безьє. Цей алгоритм не лише визначає точку кривої для значення $t$, але і ділить криву на дві частини в точці, що відповідає параметру $t$, а також надає опис двох окремих кривих у формі Безьє (у параметричному вигляді).

Описаний алгоритм справедливий для нераціональних кривих Безьє. Для обчислення раціональних кривих в ${𝐑}^n$, можна спроектувати точку в ${𝐑}^{n+1}$; наприклад крива в тривимірному просторі повинна мати опорні точки $\{(x_i,y_i,z_i)\}$ і ваги $\{w_i\}$ спроектовані в вагові опорні точки $\{(w_i{x}_i,w_i{y}_i,w_i{z}_i,w_i)\}$. Потім зазвичай алгоритм переходить до інтерполяції в ${𝐑}^4$. Отримані чотиривимірні точки можуть бути спроектовані назад в тривимірний простір за допомогою перспективного ділення (однорідні координати точки діляться на «вагу» $\{w_i\}$).

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

Посилання

• Реалізація на c++ Шаблон:Webarchive
• Адаптивне розбиття кривих Безьє Шаблон:Webarchive

Див. також

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

Література

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3