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

,

onde b é um Polinômio de Bernstein

.

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

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

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

Notas[editar | editar código-fonte]

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

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

em

e

Exemplo[editar | editar código-fonte]

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

no ponto t0.

Nós iniciamos a recursão com

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

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

com

.

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

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

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

  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]