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

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

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

Определение

Кривая Безье $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

Следующая функция применяет алгоритм Де Кастельжо к массиву points, разрешая конечную среднюю точку с дополнительными свойствами in и out (для касательных «входа» и «выхода» средней точки соответственно).

function deCasteljau(points, position = 0.5) {
	let a, b, midpoints = [];
	while (points.length > 1) {
		const num = points.length - 1;
		for (let i = 0; i < num; ++i) {
			a = points[i];
			b = points[i+1];
			midpoints.push([
				a[0] + ((b[0] - a[0]) * position),
				a[1] + ((b[1] - a[1]) * position),
			]);
		}
		points = midpoints;
		midpoints = [];
	}
	return Object.assign(points[0], {in: a, out: b});
}

В следующем примере эта функция вызывается с помощью зеленые точки внизу, ровно на середине кривой. Полученные координаты должны быть равны $(192,32)$ , или положение самого центрального красная точка.

{
	/* Definition of deCasteljau() function omitted for brevity */
	const nodes = window.document.querySelectorAll("circle.n0-point");
	const points = Array.from(nodes).map(({cx, cy}) => [cx.baseVal.value, cy.baseVal.value]);
	deCasteljau(points); // Result: [192, 32]
}

См. также

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

Ссылки

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

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

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