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]