Algoritmo de De Casteljau

En el campo matemático del análisis numérico , el algoritmo de De Casteljau es un método recursivo para evaluar polinomios en forma de Bernstein o curvas de Bézier , llamado así en honor a su inventor Paul de Casteljau . El algoritmo de De Casteljau también se puede utilizar para dividir una única curva de Bézier en dos curvas de Bézier con un valor de parámetro arbitrario.

Aunque el algoritmo es más lento para la mayoría de las arquitecturas en comparación con el enfoque directo, es más estable numéricamente . ^{[ cita necesaria ]}

Definición

Una curva de Bézier (de grado , con puntos de control ) se puede escribir en forma de Bernstein de la siguiente manera ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle \beta _{0},\ldots ,\beta _{n}}$

${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),}$

¿Dónde está el polinomio de base de Bernstein ? ${\displaystyle b}$

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

La curva en el punto se puede evaluar con la relación de recurrencia. ${\displaystyle t_{0}}$

${\displaystyle \beta _{i}^{(0)}:=\beta _{i},\ \ i=0,\ldots ,n}$

${\displaystyle \beta _{i}^{(j)}:=\beta _{i}^{(j-1)}(1-t_{0})+\beta _{i+1}^{(j-1)}t_{0},\ \ i=0,\ldots ,n-j,\ \ j=1,\ldots ,n}$

Entonces, la evaluación de un punto se puede evaluar en operaciones. El resultado está dado por ${\displaystyle B}$ ${\displaystyle t_{0}}$ ${\displaystyle {\binom {n}{2}}}$ ${\displaystyle B(t_{0})}$

${\displaystyle B(t_{0})=\beta _{0}^{(n)}.}$

Además, la curva de Bézier se puede dividir en dos curvas con sus respectivos puntos de control: ${\displaystyle B}$ ${\displaystyle t_{0}}$

${\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}}$

${\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}}$

Interpretación geométrica

La interpretación geométrica del algoritmo de De Casteljau es sencilla.

• Considere una curva de Bézier con puntos de control . Conectando los puntos consecutivos creamos el polígono de control de la curva. ${\displaystyle P_{0},...,P_{n}}$
• Subdivide ahora cada segmento de línea de este polígono con la proporción y conecta los puntos que obtengas. De esta forma se llega al nuevo polígono con un segmento menos. ${\displaystyle t:(1-t)}$
• Repita el proceso hasta llegar al punto único: este es el punto de la curva correspondiente al parámetro . ${\displaystyle t}$

La siguiente imagen muestra este proceso para una curva de Bézier cúbica:

Tenga en cuenta que los puntos intermedios que se construyeron son, de hecho, los puntos de control de dos nuevas curvas de Bézier, ambas exactamente coincidentes con la antigua. Este algoritmo no solo evalúa la curva en , sino que la divide en dos partes en y proporciona las ecuaciones de las dos subcurvas en forma de Bézier. ${\displaystyle t}$ ${\displaystyle t}$

La interpretación dada anteriormente es válida para una curva de Bézier no racional. Para evaluar una curva de Bézier racional en , podemos proyectar el punto en ; por ejemplo, una curva en tres dimensiones puede tener sus puntos de control y pesos proyectados a los puntos de control ponderados . Luego, el algoritmo procede como de costumbre, interpolando en . Los puntos cuatridimensionales resultantes se pueden proyectar nuevamente en un espacio tridimensional con una división de perspectiva . ${\displaystyle \mathbf {R} ^{n}}$ ${\displaystyle \mathbf {R} ^{n+1}}$ ${\displaystyle \{(x_{i},y_{i},z_{i})\}}$ ${\displaystyle \{w_{i}\}}$ ${\displaystyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}}$ ${\displaystyle \mathbf {R} ^{4}}$

En general, las operaciones sobre una curva (o superficie) racional son equivalentes a las operaciones sobre una curva no racional en un espacio proyectivo . Esta representación como "puntos de control ponderados" y pesos suele ser conveniente al evaluar curvas racionales.

Notación

Al hacer el cálculo a mano, es útil escribir los coeficientes en un esquema triangular como

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

Al elegir un punto t ₀ para evaluar un polinomio de Bernstein, podemos usar las dos diagonales del esquema del triángulo para construir una división del polinomio.

${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]}$

en

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}\beta _{0}^{(i)}b_{i,n}\left({\frac {t}{t_{0}}}\right)\!,\quad t\in [0,t_{0}]}$

y

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}\beta _{i}^{(n-i)}b_{i,n}\left({\frac {t-t_{0}}{1-t_{0}}}\right)\!,\quad t\in [t_{0},1].}$

curva de Bézier

Una curva de Bézier

Al evaluar una curva de Bézier de grado n en un espacio tridimensional con n + 1 puntos de control P _i

${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]}$

con

${\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},}$

dividimos la curva de Bézier en tres ecuaciones separadas

${\displaystyle B_{1}(t)=\sum _{i=0}^{n}x_{i}b_{i,n}(t),\ t\in [0,1]}$

${\displaystyle B_{2}(t)=\sum _{i=0}^{n}y_{i}b_{i,n}(t),\ t\in [0,1]}$

${\displaystyle B_{3}(t)=\sum _{i=0}^{n}z_{i}b_{i,n}(t),\ t\in [0,1]}$

que evaluamos individualmente utilizando el algoritmo de De Casteljau.

Ejemplo

Queremos evaluar el polinomio de Bernstein de grado 2 con los coeficientes de Bernstein

${\displaystyle \beta _{0}^{(0)}=\beta _{0}}$

${\displaystyle \beta _{1}^{(0)}=\beta _{1}}$

${\displaystyle \beta _{2}^{(0)}=\beta _{2}}$

en el punto t ₀ .

Comenzamos la recursividad con

${\displaystyle \beta _{0}^{(1)}=\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}=\beta _{0}(1-t_{0})+\beta _{1}t_{0}}$

${\displaystyle \beta _{1}^{(1)}=\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}=\beta _{1}(1-t_{0})+\beta _{2}t_{0}}$

y con la segunda iteración la recursividad se detiene con

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

que es el polinomio de Bernstein esperado de grado  2 .

Implementaciones

A continuación se muestran ejemplos de implementaciones del algoritmo de De Casteljau en varios lenguajes de programación.

Haskell

deCasteljau :: Doble -> [( Doble , Doble )] -> ( Doble , Doble ) deCasteljau t [ b ] = b deCasteljau t coefs = deCasteljau t reducido donde reducido = zipWith ( lerpP t ) coefs ( tail coefs ) lerpP t ( x0 , y0 ) ( x1 , y1 ) = ( lerp t x0 x1 , lerp t y0 y1 ) lerp t a b = t * b + ( 1 - t ) * a                                                        

Pitón

def  de_casteljau ( t ,  coefs ):  beta  =  [ c  for  c  in  coefs ]  # los valores en esta lista se anulan  n  =  len ( beta )  para  j  en  el rango ( 1 ,  n ):  para  k  en el  rango ( n  -  j ):  beta [ k ]  =  beta [ k ]  *  ( 1  -  t )  +  beta [ k  +  1 ]  *  t  devuelve  beta [ 0 ]

Java

público doble deCasteljau ( doble t , doble [] coeficientes ) { doble [] beta = coeficientes ; int norte = beta . longitud ; para ( int i = 0 ; i < n ; i ++ ) { para ( int j = 0 ; j < ( n - i ); j ++ ) { beta [ j ] = beta [ j ] * ( 1 - t ) + beta [ j + 1 ] * t ; } } devolver beta [ 0 ] ; }                                                     

javascript

La siguiente función aplica el algoritmo de De Casteljau a una matriz de points, resolviendo el punto medio final con las propiedades adicionales iny out(para las tangentes "de entrada" y "de salida" del punto medio, respectivamente).

función deCasteljau ( puntos , posición = 0,5 ) {     sea ​​a , b , puntos medios = [];     mientras ( puntos . longitud > 1 ) {    número constante = puntos . longitud - 1 ;     para ( sea i = 0 ; i < núm ; ++ i ) {         a = puntos [ i ];  b = puntos [ i + 1 ];  puntos medios . empujar ([a [ 0 ] + (( b [ 0 ] - a [ 0 ]) * posición ),      a [ 1 ] + (( b [ 1 ] - a [ 1 ]) * posición ),      ]);}puntos = puntos medios ;  puntos medios = [];  }devolver objeto . asignar ( puntos [ 0 ], { entrada : a , salida : b });     }

El siguiente ejemplo llama a esta función con los puntos verdes debajo, exactamente a la mitad de la curva. Las coordenadas resultantes deben ser iguales a , o la posición del punto rojo más central . ${\displaystyle (192,32)}$

Segmentos de recta intermedios obtenidos aplicando recursivamente interpolación lineal a puntos adyacentes.

{ /* Definición de la función deCasteljau() omitida por brevedad */ const nodes = window . documento . querySelectorAll ( "circulo.n0-punto" ); puntos constantes = Matriz . de ( nodos ). map (({ cx , cy }) => [ cx . baseVal . valor , cy . baseVal . valor ]); deCasteljau ( puntos ); // Resultado: [192, 32] }           

Ver también

• Curvas de Bézier
• Algoritmo de De Boor
• Esquema de Horner para evaluar polinomios en forma monomio
• Algoritmo de Clenshaw para evaluar polinomios en forma de Chebyshev

Referencias

• Farín, Gerald y Hansford, Dianne (2000). Los fundamentos de CAGD . Natic, MA: AK Peters, Ltd. ISBN  1-56881-123-3

enlaces externos

• Aproximación lineal por partes de las curvas de Bézier: descripción del algoritmo de De Casteljau, incluido un criterio para determinar cuándo detener la recursividad
• Curvas de Bézier y Picasso: descripción e ilustración del algoritmo de De Casteljau aplicado a curvas de Bézier cúbicas.
• Algoritmo de Casteljau: ayuda para la implementación y demostración interactiva del algoritmo.