Рекурсивное Представление

Вышеизложенные вычисления можно провести и по-другому, с помощью рекурсии. Пусть P _{0, j} будет P _j для j = 0, 1,..., n. То есть, P _{0, j} - это j -й элемент в 0 столбце. Элемент j в столбце i находим так:

Говоря точнее, элемент P _{i , j} - это сумма (1- u) P _{i -1, j} (сверху слева) и u P _{i -1, j +1} (снизу слева). Конечный результат (т.e. точка на кривой) - это P _{n ,0}. Исходя из этого, можно сразу составить такую рекурсивную процедуру:

Function deCasteljau(i,j) begin

if i = 0 then

return P _{0, j}

Else

return (1- u)* deCasteljau (i -1, j) + u * deCasteljau (i -1, j +1)

End

Выглядит она простой и короткой; тем не менее, она очень неэффективна. И вот почему.

Блин, не хочу я вам[SSN], объяснять, почему она неэффективна. - (прим. перев.)

We start with a call to deCasteljau (n,0) for computing P _{n ,0}. The else part splits this call into two more calls, deCasteljau (n -1,0) for computing P _{n -1,0} and deCasteljau (n -1,1) for computing P _{n -1,1}.

Consider the call to deCasteljau (n -1,0). It splits into two more calls, deCasteljau (n -2,0) for computing P _{n -2,0} and deCasteljau (n -2,1) for computing P _{n -2,1}. The call to deCasteljau (n -1,1) splits into two calls, deCasteljau (n -2,1) for computing P _{n -2,1} and deCasteljau (n -2,2) for computing P _{n -2,2}. Thus, deCasteljau (n -2,1) is called twice. If we keep expanding these function calls, we should discover that almost all function calls for computing P _{i , j} are repeated, not once but many many times. How bad is this? In fact, the above computation scheme is very similar to the following way of computing the n -th Fibonacci number:

Тут процедура сравнивается с процедурой вычисления чисел Фибоначи - прим. перев.:

Function Fibonacci(n) begin

if n = 0 or n = 1 then

return 1

Else

return Fibonacci (n -1) + Fibonacci (n -2)

End

Чтобы найти касательный и нормальный вектора в точке на кривой Безье, нам нужно знать ее производную в этой точке. К счастью, это просто, как два бита переслать.

Кривая Безье, построенная по n + 1 контрольным точкам p ₀, p ₁,..., p _n имеет следующее уравнение:

где коэффициент Безье B_n,i (u) рассчитывается по формуле:

Так как контрольные точки постоянны и не зависят от переменной u, вычисление p '(u) сводится к вычислению производных коэффициентов Безье. После алгебраических преобразований имеем такой результат для B ^' _n,i (u):

Затем, вычисляя производную кривой p (u), получим:

Пусть q ₀ = n (p ₁ - p ₀), q ₁ = n (p ₂ - p ₁), q ₂ = n (p ₃ - p ₂),..., q _{n -1} = n (p _n - p _{n -1}). Вышеизложенное уравнение уменьшается до

Таким образом, производная p (u) - это кривая Безье n - 1 пстепени, построенная по n контрольным точкам n (p ₁ - p ₀), n (p ₂ - p ₁), n (p ₃ - p ₂),..., n (p _n - p _{n -1}). Эта производная кривая обычно называется годографом исходной кривой Безье. Заметьте, что p _{i +1} - p _i - это вектор от p _i до p _{i +1} и n (p _{i +1} - p _i) в n раз длиннее этого вектора. Имея в наличии контрольные точки кривой, можно легко получить контрольные точки ее производной. Рисунок слева показывает кривую Безье 7 степени, а справа - ее производную, т.е. кривую Безье 6 степени.

Дата добавления: 2015-10-29