Русская Википедия:Алгоритм де Кастельжо
В вычислительной математике алгоритм де Кастельжо, названный в честь его изобретателя Поля де Кастельжо — рекурсивный метод определения формы многочленов Бернштейна или кривых Безье. Алгоритм де Кастельжо также может быть использован для разделения кривой Безье на две части по произвольному значению параметра <math>(t)</math>.
Достоинством алгоритма является его более высокая вычислительная устойчивость по сравнению с прямым методом.
Описание
Задан многочлен Бернштейна B степени n
- <math>B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t),</math>
где b — базис многочлена Бернштейна, многочлен в точке t0 может быть определен с помощью рекуррентного соотношения
- <math>\beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n</math>
- <math>\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</math>
Тогда определение <math>B</math> в точке <math>t_0</math> может быть определено в <math>n</math> шагов алгоритма. Результат <math>B(t_0)</math> дан по:
- <math>B(t_0)=\beta_0^{(n)}.</math>
Также, кривая Безье <math>B</math> может быть разделена в точке <math>t_0</math> на две кривые с соответствующими опорными точками:
- <math>\beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)}</math>
- <math>\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}</math>
Геометрическая интерпретация
Геометрическая интерпретация алгоритма де Кастельжо проста:
- Задана кривая Безье с опорными точками <math>\scriptstyle P_0,...,P_n</math>. Соединив последовательно опорные точки с первой по последнюю, получаем ломаную линию.
- Разделяем каждый полученный отрезок этой ломаной в соотношении <math>\scriptstyle t : (1-t)</math> и соединяем полученные точки. В результате получаем ломаную линию с количеством отрезков, меньшим на один, чем исходная ломаная линия.
- Повторяем процесс до тех пор, пока не получим единственную точку. Эта точка и будет являться точкой на заданной кривой Безье с параметром <math>\scriptstyle t</math>.
Следующая иллюстрация демонстрирует этот процесс для кубической кривой Безье:
Следует заметить, что полученные в процессе построения промежуточные точки являются опорными точками для двух новых кривых Безье, в точности совпадающих с исходной, и в совокупности дающих исходную кривую Безье. Этот алгоритм не только определяет точку кривой в <math>\scriptstyle t</math>, но и делит кривую на две части в <math>\scriptstyle t</math>, а также предоставляет описание двух суб-кривых в форме Безье (в параметрическом представлении).
Описанный алгоритм справедлив для нерациональных кривых Безье. Для вычисления рациональных кривых в <math>\scriptstyle \mathbf{R}^n</math>, можно спроецировать точку в <math>\scriptstyle \mathbf{R}^{n+1}</math>; например кривая в трехмерном пространстве должна иметь опорные точки <math>\scriptstyle \{(x_i, y_i, z_i)\}</math> и веса <math>\scriptstyle \{w_i\}</math> спроецированные в весовые контрольные точки <math>\scriptstyle \{(w_ix_i, w_iy_i, w_iz_i, w_i)\}</math>. Затем обычно алгоритм переходит к интерполяции в <math>\scriptstyle \mathbf{R}^4</math>. Результирующие четырехмерные точки могут быть спроецированы обратно в трехмерное пространство с помощью перспективного деления.
В целом, операции с рациональными кривыми (или поверхностями) эквивалентны операциям с нерациональными кривыми в проективном пространстве. Представление опорных точек как взвешенных часто бывает удобно для определения рациональных кривых.
Ссылки
См. также
- Русская Википедия
- Страницы с неработающими файловыми ссылками
- Алгоритмы
- Геометрические алгоритмы
- Вычислительная геометрия
- Компьютерная графика
- Математические основы компьютерной графики
- Численные методы
- Страницы, где используется шаблон "Навигационная таблица/Телепорт"
- Страницы с телепортом
- Википедия
- Статья из Википедии
- Статья из Русской Википедии
