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
Uma curva de Bézier B (de grau n) pode ser escrita na forma de Bernstein como se segue
,
onde b é um Polinômio de Bernstein
.
A curva no ponto t0 pode ser calculada com a relação de recorrência
![{\displaystyle \beta _{i}^{(0)}:=\beta _{i}{\mbox{ , }}i=0,\ldots ,n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fc8fa1843a2b22addc72880c7ccf2d68a19b1dc)
![{\displaystyle \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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d5dd3746c03b87584a6a379595332ff0f30bf0c)
Então, a estimativa de
no ponto
pode ser calculada em
passos do algoritmo. O resultado
é dado por:
![{\displaystyle B(t_{0})=\beta _{0}^{(n)}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e58a9b6e472c671520531b405d5aedb10e51797)
Além disso, a curva de Bézier
pode ser dividida no ponto
em duas curvas com respectivos pontos de controle:
![{\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e80d473388ce635945b4cc751ed704789e8e2966)
![{\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f09ff951b277c404ca6d4f40ac34187c9cc775d8)
Notas
Ao fazer os cálculos manualmente, é útil escrever os coeficientes em um esquema de triângulo como abaixo
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58fd085f9048ffc54657fc80dfae9bab07d4f783)
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
![{\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t){\mbox{ , }}\qquad t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/eb84d69bb346f499c657d7e0737dda3ee72535fa)
em
![{\displaystyle 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}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ddb872182151fb849a91f142f00b0a7ecb6c0eed)
e
![{\displaystyle 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]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/38ea4239f7425782fc773820c1c01f6450856354)
Exemplo
Deseja-se calcular o polinomial de Bernstein de grau 2 os coeficientes de Bernstein
![{\displaystyle \beta _{0}^{(0)}=\beta _{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b906ff14964ea77ba3a8d1e1484c835a53c54c65)
![{\displaystyle \beta _{1}^{(0)}=\beta _{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0c0afa61238e8ecc64244d7f5f80046ae9fb6e52)
![{\displaystyle \beta _{2}^{(0)}=\beta _{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef05314d830a915317409fbbf9e79c43bb2fa87c)
no ponto t0.
Nós iniciamos a recursão com
![{\displaystyle \beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}t_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/58321257575553e731e053089665ed5a08fde400)
![{\displaystyle \beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}=\beta _{1}(1-t_{0})+\beta _{2}t_{0}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/971e06dcb525874d3d4f4f171d2e264d35ca074d)
a com a segunda iteração da recursão parando com
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/43cf6834403aba9a0f9e6b63295b4145f981ae28)
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
![{\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7841aeeff9c1b50c687890c1a35194fc036309a8)
com
.
nós dividimos a curva de Bézier em três equações separadas
![{\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fc49c852d0ddc38093382f5562bfd61cbfeb0fb)
![{\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b169ad3d55321750016c7bf014e46319f229c1f8)
![{\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t){\mbox{ , }}t\in [0,1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/464a9fad7d1512dd399ade0d86684e1ba47e9fb2)
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
. Conectando os pontos consecutivos, nós criamos o polígono de controle da curva. - Sudividindo agora cada segmento deste polígono com relação
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
.
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
, mas divide a curva em duas partes em
, 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
, nós podemos projetar o ponto em
; por exemplo, uma curva em três dimensões pode ter seus pontos de controle
e cargas
projetadas para os pontos de controle ponderados
. O algoritmo então segue como usual, interpolando em
. 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
- ↑ Teoria Local das Curvas, Roberto Simoni (2005), p. 53, página visitada em 4 de fevereiro de 2014.
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