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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

Опис[ред. | ред. код]

Заданий многочлен Бернштейна B ступеня n з опорними точками

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

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

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

Приклад реалізації[ред. | ред. код]

Ось приклад реалізації алгоритму де Кастельє в 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

Примітки[ред. | ред. код]

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

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

на

та

Приклад[ред. | ред. код]

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

у точці t0.

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

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

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

Крива Безьє[ред. | ред. код]

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

за

.

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

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

Геометрична інтерпретація[ред. | ред. код]

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

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

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

DeCasteljau1.svg

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

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

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

Посилання[ред. | ред. код]

Див. також[ред. | ред. код]

Література[ред. | ред. код]

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