Algoritmo de De Casteljau

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O Algoritmo de De Casteljau na matemática, no campo da análise numérica, é um método recursivo para calcular polinômios na forma de Bernstein ou da Curva de Bézier. Chamado assim por causa do seu criador Paul de Casteljau.1 Esse algoritmo pode ser usado também para dividir uma única curva de Bézier em duas, recebendo um valor arbitrário como parâmetro.

Embora seja um pouco mais lento, para a maior parte das arquiteturas, quando comparado com abordagens diretas, esse algoritmo se mostra numericamente estável. É amplamente usado, com algumas modificações, como o mais robusto e numericamente estável método para calculo de polinomiais.

Definição[editar | editar código-fonte]

Uma curva de Bézier B (de grau n) pode ser escrita na forma de Bernstein como se segue

B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t) ,

onde b é um Polinômio de Bernstein

 b_{i,n}(t) = {n \choose i}(1-t)^{n-i}t^i.

A curva no ponto t0 pode ser calculada com a relação de recorrência

\beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n
\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

Então, a estimativa de B no ponto t_0 pode ser calculada em n passos do algoritmo. O resultado B(t_0) é dado por:

B(t_0)=\beta_0^{(n)}.

Alem disso, a curva de Bézier B pode ser dividida no ponto t_0 em duas curvas com respectivos pontos de controle:

\beta_0^{(0)},\beta_0^{(1)},\ldots,\beta_0^{(n)}
\beta_0^{(n)},\beta_1^{(n-1)},\ldots,\beta_n^{(0)}

Notas[editar | editar código-fonte]

Ao fazer os cálculos manualmente, é útil escrever os coeficientes em um esquema de triângulo como abaixo


\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}

Ao escolher um ponto t0 para calcular o polinomial de Bernstein pode-se usar as duas diagonais do esquema de triângulo para construir um divisão da polinomial

B(t) = \sum_{i=0}^n \beta_i^{(0)} b_{i,n}(t) \mbox{ , } \qquad t \in [0,1]

em

B_1(t) = \sum_{i=0}^n \beta_0^{(i)} b_{i,n}\left(\frac{t}{t_0}\right) \mbox{ , } \qquad t \in [0,t_0]

e

B_2(t) = \sum_{i=0}^n \beta_i^{(n-i)} b_{i,n}\left(\frac{t-t_0}{1-t_0}\right) \mbox{ , } \qquad t \in [t_0,1]

Exemplo[editar | editar código-fonte]

Deseja-se calcular o polinomial de Bernstein de grau 2 os coeficientes de Bernstein

\beta_0^{(0)} = \beta_0
\beta_1^{(0)} = \beta_1
\beta_2^{(0)} = \beta_2

no ponto t0.

Nós iniciamos a recursão com

\beta_0^{(1)} = \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 = \beta_0(1-t_0) + \beta_1 t_0
\beta_1^{(1)} = \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 = \beta_1(1-t_0) + \beta_2 t_0

a com a segunda iteração da recursão parando com

 
\begin{align}
\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{align}

que é o esperado polinômio de Bernstein de grau 2.

Curva de Bézier[editar | editar código-fonte]

Ao calcular uma curva de Bézier de grau n no espaço 3 dimensional com n+1 pontos de controle p i

\mathbf{B}(t) = \sum_{i=0}^{n} \mathbf{P}_i b_{i,n}(t) \mbox{ , } t \in [0,1]

com

\mathbf{P}_i := 
\begin{pmatrix} 
x_i \\ 
y_i \\
z_i 
\end{pmatrix}
.

nós dividimos a curva de Bézier em três equações separadas

B_1(t) = \sum_{i=0}^{n} x_i b_{i,n}(t) \mbox{ , } t \in [0,1]
B_2(t) = \sum_{i=0}^{n} y_i b_{i,n}(t) \mbox{ , } t \in [0,1]
B_3(t) = \sum_{i=0}^{n} z_i b_{i,n}(t) \mbox{ , } t \in [0,1]

que calculamos individualmente usando o algoritmo de De Casteljau.

Interpretação geométrica[editar | editar código-fonte]

A interpretação geométrica do algoritmo de De Casteljau é simples.

  • Considerando uma curva de Bézier com pontos de controle \scriptstyle P_0,...,P_n. Conectando os pontos consecutivos, nós criamos o polígono de controle da curva.
  • Sudividindo agora cada segmento deste polígono com relação \scriptstyle t : (1-t) e conectando os pontos, se consegue. Desta forma você vai conseguir o novo polígono tendo menos um segmento.
  • Repita o processo até conseguir chegar a um único ponto - este é o ponto da curva correspondente ao parâmetro \scriptstyle t.

A seguinte figura mostra o processo para um curva cúbica de Bézier:

DeCasteljau1.svg

Note que os pontos intermediários que foram construidos são de fato os pontos de controle para duas novas curvas de Bézier, ambas exatamente coincidente com a antiga. Este algoritmo não somente calcula a curva em \scriptstyle t, mas divide a curva em duas partes em \scriptstyle t, e fornece as equações das duas sub-curvas na forma de Bézier.

A interpretação dada acima é válida para uma curva de Bázier não-racional. Para calcular um curva de Bézier racional em \scriptstyle \mathbf{R}^n, nós podemos projetar o ponto em \scriptstyle \mathbf{R}^{n+1}; por exemplo, uma curva em três dimensões pode ter seus pontos de controle \scriptstyle \{(x_i, y_i, z_i)\} e cargas \scriptstyle \{w_i\} projetadas para os pontos de controle ponderados \scriptstyle \{(w_ix_i, w_iy_i, w_iz_i, w_i)\}. O algoritmo então segue como usual, interpolando em \scriptstyle \mathbf{R}^4. Os pontos de quatro dimensões resultantes podem ser projetados de volta no espaço 3D com uma pelo inverso (divisão homogênea).

Em geral, operações em uma curva racional (ou superfície) são equivalente a operações em uma curva não-racional em um espaço projetivo. Esta projeção como a "pontos de controle ponderados" e cargas é frequentemente conveniente ao calcular curvas racionais.

Referências

  1. Teoria Local das Curvas, Roberto Simoni (2005), p. 53, página visitada em 4 de fevereiro de 2014.

Bibliografia[editar | editar código-fonte]

Ver também[editar | editar código-fonte]