Алгоритм де Кастельє
В обчислювальній математиці алгоритм де Кастельє (або також алгоритм де Кастельжо), названий на честь його винахідника Поля де Кастельє — рекурсивний метод визначення форми поліномів Бернштейна або кривих Безьє. Алгоритм де Кастельє також може бути використаний для поділу кривої Безьє на дві частини за довільним значенням параметра .
Перевагою алгоритму є його вища обчислювальна стійкість у порівнянні з прямим методом.
Опис
Заданий многочлен Бернштейна 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
за
- .
ми можемо розбити криву Безьє на три окремі рівняння:
які ми оцінюємо окремо, використовуючи алгоритм де Кастельє.
Геометрична інтерпретація
Геометрична інтерпретація алгоритму де Кастельє проста:
- Задана крива Безьє з опорними точками . Поєднавши послідовно опорні точки з першої по останню, отримуємо ламану лінію.
- Поділяємо кожний отриманий відрізок цієї ламаної в співвідношенні та з'єднуємо отримані точки. Внаслідок отримуємо ламану лінію з кількістю відрізків, меншим на один, ніж вихідна ламана лінія.
- Повторюємо процес до тих пір, поки не отримаємо єдину точку. Ця точка і буде точкою на заданій кривій Безьє з параметром .
Наступна ілюстрація демонструє цей процес для кубічної кривої Безьє:
Слід зауважити, що отримані в процесі побудови проміжні точки є опорними точками для двох нових кривих Безьє, що в точності збігаються з вихідною, і в сукупності дають вихідну криву Безьє. Цей алгоритм не лише визначає точку кривої для значення , але і ділить криву на дві частини в точці, що відповідає параметру , а також надає опис двох окремих кривих у формі Безьє (у параметричному вигляді).
Описаний алгоритм справедливий для нераціональних кривих Безьє. Для обчислення раціональних кривих в , можна спроектувати точку в ; наприклад крива в тривимірному просторі повинна мати опорні точки і ваги спроектовані в вагові опорні точки . Потім зазвичай алгоритм переходить до інтерполяції в . Отримані чотиривимірні точки можуть бути спроектовані назад в тривимірний простір за допомогою перспективного ділення (однорідні координати точки діляться на «вагу» ).
У цілому, операції з раціональними кривими (або поверхнями) еквівалентні операціям з нераціональними кривими в проективному просторі. Представлення опорних точок як «вагових» часто буває зручно для визначення раціональних кривих.
Див. також
Література
- Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3