Algoritmo de De Casteljau

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. 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

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 t₀ 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)}.$

Além 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

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 t₀ 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

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 t₀.

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{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}}$

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

Curva de Bézier

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

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:

Note que os pontos intermediários que foram construídos 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_{i}x_{i},w_{i}y_{i},w_{i}z_{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.

Bibliografia

• Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3
• Weisstein, Eric W. "Bézier Curve." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/BezierCurve.html

Ver também

• Curva de Bézier
• Algoritmo de Boor
• Esquema de Horner