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

В математической области численного анализа алгоритм Де Кастельжо представляет собой рекурсивный метод оценки полиномов в форме Бернштейна или кривых Безье , названный в честь его изобретателя Поля де Кастельжо . Алгоритм Де Кастельжо также можно использовать для разделения одной кривой Безье на две кривые Безье при произвольном значении параметра.

Хотя для большинства архитектур алгоритм работает медленнее по сравнению с прямым подходом, он более стабилен в числовом отношении .

Определение

Кривая Безье $B$ (степени $n$, с контрольными точками $\beta _{0},\ldots ,\beta _{n}$) можно записать в форме Бернштейна следующим образом $$B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),$$ где $b$ является базисным полиномом Бернштейна $$b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}.$$ Кривая в точке $t_{0}$ можно оценить с помощью рекуррентного соотношения $${\begin{aligned}\beta _{i}^{(0)}&:=\beta _{i},&&i=0,\ldots ,n\\\beta _{i}^{(j)}&:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0},&&i=0,\ldots ,n-j,\ \ j=1,\ldots ,n\end{aligned}}$$

Затем оценка $B$ в точку $t_{0}$ можно оценить в ${\textstyle {\binom {n}{2}}}$ операции. Результат $B(t_{0})$ дается $$B(t_{0})=\beta _{0}^{(n)}.$$

Более того, кривая Безье $B$ можно разделить в точке $t_{0}$ на две кривые с соответствующими контрольными точками: $${\begin{aligned}&\beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}\\[1ex]&\beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}\end{aligned}}$$

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

Геометрическая интерпретация алгоритма Де Кастельжо проста.

• Рассмотрим кривую Безье с контрольными точками $P_{0},\dots ,P_{n}$. Соединяя последовательные точки, мы создаем контрольный многоугольник кривой.
• Разделите теперь каждый сегмент этого многоугольника с соотношением $t:(1-t)$ и соедините полученные точки. Таким образом, вы получите новый многоугольник, имеющий на один сегмент меньше.
• Повторяйте процесс, пока не дойдете до единственной точки – это точка кривой, соответствующая параметру. $t$.

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

Обратите внимание, что построенные промежуточные точки на самом деле являются контрольными точками для двух новых кривых Безье, обе точно совпадающих со старой. Этот алгоритм не только оценивает кривую при $t$, но разбивает кривую на две части в точке $t$и предоставляет уравнения двух подкривых в форме Безье.

Приведенная выше интерпретация справедлива для нерациональной кривой Безье. Чтобы оценить рациональную кривую Безье в $\mathbf {R} ^{n}$, мы можем спроецировать эту точку на $\mathbf {R} ^{n+1}$; например, трехмерная кривая может иметь свои контрольные точки $\{(x_{i},y_{i},z_{i})\}$ и веса $\{w_{i}\}$ проецируется на взвешенные контрольные точки $\{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$. Затем алгоритм действует как обычно, интерполируя $\mathbf {R} ^{4}$. Полученные четырехмерные точки можно спроецировать обратно в трехмерное пространство с разделением перспективы .

В общем, операции над рациональной кривой (или поверхностью) эквивалентны операциям над нерациональной кривой в проективном пространстве . Такое представление в виде «взвешенных контрольных точек» и весов часто бывает удобно при оценке рациональных кривых.

Обозначения

При выполнении расчета вручную полезно записать коэффициенты в схеме треугольника в виде $${\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 ₀ для оценки многочлена Бернштейна, мы можем использовать две диагонали схемы треугольника, чтобы построить деление многочлена. $$B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]$$ в $$B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right)\!,\quad 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)\!,\quad t\in [t_{0},1].$$

Кривая Безье

Кривая Безье

При оценке кривой Безье степени n в 3-мерном пространстве с n + 1 контрольными точками P _i $$\mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]$$ с $$\mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},$$ мы разбиваем кривую Безье на три отдельных уравнения $${\begin{aligned}B_{1}(t)&=\sum _{i=0}^{n}x_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{2}(t)&=\sum _{i=0}^{n}y_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{3}(t)&=\sum _{i=0}^{n}z_{i}b_{i,n}(t),&t\in [0,1]\end{aligned}}$$ которые мы оцениваем индивидуально с помощью алгоритма Де Кастельжо.

Пример

Мы хотим оценить полином Бернштейна степени 2 с коэффициентами Бернштейна $${\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}$$ в точке t ₀ .

Мы начинаем рекурсию с $${\begin{aligned}\beta _{0}^{(1)}&&=&&\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}&&=&&\beta _{0}(1-t_{0})+\beta _{1}t_{0}\\[1ex]\beta _{1}^{(1)}&&=&&\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}&&=&&\beta _{1}(1-t_{0})+\beta _{2}t_{0}\end{aligned}}$$ и на второй итерации рекурсия останавливается на $${\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 .

Реализации

Вот примеры реализации алгоритма Де Кастельжо на различных языках программирования.

Хаскелл

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

Питон

def de_casteljau(t: float, coefs: list[float]) -> float:
    """De Casteljau's algorithm."""
    beta = coefs.copy()  # values in this list are overridden
    n = len(beta)
    for j in range(1, n):
        for k in range(n - j):
            beta[k] = beta[k] * (1 - t) + beta[k + 1] * t
    return beta[0]

Ява

public double deCasteljau(double t, double[] coefficients) {
    double[] beta = coefficients;
    int n = beta.length;
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < (n - i); j++) {
            beta[j] = beta[j] * (1 - t) + beta[j + 1] * t;
        }
    }
    return beta[0];
}

Пример кода на Javascript

Следующая функция javascript применяет алгоритм Де Кастельжау к массиву контрольных точек или полюсов , первоначально названных Де Кастельжау, чтобы уменьшать их одну за другой до тех пор, пока не будет достигнута точка на кривой для заданного t между 0 для первой точки кривой и 1. для последнего

function crlPtReduceDeCasteljau(points, t) {
    let retArr = [ points.slice () ];
	while (points.length > 1) {
        let midpoints = [];
		for (let i = 0; i+1 < points.length; ++i) {
			let ax = points[i][0];
			let ay = points[i][1];
			let bx = points[i+1][0];
			let by = points[i+1][1];
            // a * (1-t) + b * t = a + (b - a) * t
			midpoints.push([
				ax + (bx - ax) * t,
				ay + (by - ax) * t,
			]);
		}
        retArr.push (midpoints)
		points = midpoints;
	}
	return retArr;
}

Например

       var poles = [ [0, 128], [128, 0], [256, 0], [384, 128] ] 
       crlPtReduceDeCasteljau (poles, .5)

возвращает массив

       [ [ [0, 128], [128, 0], [256, 0], [384, 128 ] ], 
         [ [64, 64], [192, 0], [320, 64] ], 
         [ [128, 32], [256, 32]], 
         [ [192, 32]], 
       ]

Какие точки и соединяющие их отрезки показаны ниже?

Intermediate line segments obtained by recursively applying linear interpolation to adjacent points.

См. также

• Кривые Безье
• Алгоритм Де Бура
• Схема Хорнера для оценки полиномов в мономиальной форме
• Алгоритм Кленшоу для вычисления полиномов в форме Чебышева

Ссылки

• Фарин, Джеральд Э.; Хансфорд, Дайанна (2000). Основы CAGD . Натик, Массачусетс: АК Питерс. ISBN  978-1-56881-123-9 .

Внешние ссылки

• Кусочно-линейная аппроксимация кривых Безье - описание алгоритма Де Кастельжо, включая критерий определения момента остановки рекурсии
• Кривые Безье и Пикассо — Описание и иллюстрация алгоритма Де Кастельжо, примененного к кубическим кривым Безье.
• Алгоритм де Кастельжо — помощь по реализации и интерактивная демонстрация алгоритма.