Algoritmo de De Casteljau

Método para evaluar polinomios en forma de Bernstein

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

El algoritmo es numéricamente estable ^[1] en comparación con la evaluación directa de polinomios. La complejidad computacional de este algoritmo es , donde d es el número de dimensiones y n es el número de puntos de control. Existen alternativas más rápidas. ^{[2] [3]} ${\displaystyle O(dn^{2})}$

Definición

Una curva de Bézier (de grado , con puntos de control ) se puede escribir en forma de Bernstein de la siguiente manera, donde es un polinomio de base de Bernstein. La curva en el punto se puede evaluar con la relación de recurrencia ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle \beta _{0},\ldots ,\beta _{n}}$ $${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),}$$ ${\displaystyle b}$ $${\displaystyle b_{i,n}(t)={n \choose i}(1-t)^{n-i}t^{i}.}$$ ${\displaystyle t_{0}}$ $${\displaystyle {\begin{aligned}\beta _{i}^{(0)}&:=\beta _{i},&&i=0,\ldots ,n\\\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\end{aligned}}}$$

Luego, la evaluación de un punto puede evaluarse en operaciones. El resultado viene dado por ${\displaystyle B}$ ${\displaystyle t_{0}}$ ${\textstyle {\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 respectivos puntos de control: ${\displaystyle B}$ ${\displaystyle t_{0}}$ $${\displaystyle {\begin{aligned}&\beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)}\\[1ex]&\beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)}\end{aligned}}}$$

Interpretación geométrica

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

• Consideremos 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},\dots ,P_{n}}$
• Subdivide ahora cada segmento de recta de este polígono con la razón y conecta los puntos que obtengas. De esta manera llegarás 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:

Obsérvese que los puntos intermedios que se construyeron son, de hecho, los puntos de control para 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 . El algoritmo luego procede como de costumbre, interpolando en . Los puntos de cuatro dimensiones resultantes pueden proyectarse nuevamente en el espacio tridimensional con una división en 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 Al elegir un punto t ₀ para evaluar un polinomio de Bernstein, podemos usar las dos diagonales del esquema triangular para construir una división del polinomio en y $${\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}}}$$ $${\displaystyle B(t)=\sum _{i=0}^{n}\beta _{i}^{(0)}b_{i,n}(t),\quad t\in [0,1]}$$ $${\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}]}$$ $${\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 _dividimos la curva de Bézier en tres ecuaciones separadas que evaluamos individualmente utilizando el algoritmo de De Casteljau. $${\displaystyle \mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {P} _{i}b_{i,n}(t),\ t\in [0,1]}$$ $${\displaystyle \mathbf {P} _{i}:={\begin{pmatrix}x_{i}\\y_{i}\\z_{i}\end{pmatrix}},}$$ $${\displaystyle {\begin{aligned}B_{1}(t)&=\sum _{i=0}^{n}x_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{2}(t)&=\sum _{i=0}^{n}y_{i}b_{i,n}(t),&t\in [0,1]\\[1ex]B_{3}(t)&=\sum _{i=0}^{n}z_{i}b_{i,n}(t),&t\in [0,1]\end{aligned}}}$$

Ejemplo

Queremos evaluar el polinomio de Bernstein de grado 2 con los coeficientes de Bernstein en el punto t ₀ . $${\displaystyle {\begin{aligned}\beta _{0}^{(0)}&=\beta _{0}\\[1ex]\beta _{1}^{(0)}&=\beta _{1}\\[1ex]\beta _{2}^{(0)}&=\beta _{2}\end{aligned}}}$$

Comenzamos la recursión con y con la segunda iteración la recursión se detiene con que es el polinomio de Bernstein esperado de grado  2 . $${\displaystyle {\begin{aligned}\beta _{0}^{(1)}&&=&&\beta _{0}^{(0)}(1-t_{0})+\beta _{1}^{(0)}t_{0}&&=&&\beta _{0}(1-t_{0})+\beta _{1}t_{0}\\[1ex]\beta _{1}^{(1)}&&=&&\beta _{1}^{(0)}(1-t_{0})+\beta _{2}^{(0)}t_{0}&&=&&\beta _{1}(1-t_{0})+\beta _{2}t_{0}\end{aligned}}}$$ $${\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}}}$$

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    coeficientes t de deCasteljau = t de deCasteljau reducida       dónde reducido = zipWith ( lerpP t ) coeficientes ( coeficientes de cola )        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 :  float ,  coefs :  lista [ float ])  ->  float : """Algoritmo de De Casteljau.""" beta  =  coefs . copy ()  # 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 n = beta . longitud ;    para ( int i = 1 ; i < n ; i ++ ) {          para ( int j = 0 ; j < ( n - i ); j ​​++ ) {            beta [ j ] = beta [ j ] * ( 1 - t ) + beta [ j + 1 ] * t ;             } } devuelve beta [ 0 ] ; }

Ejemplo de código en JavaScript

La siguiente función de JavaScript aplica el algoritmo de De Casteljau a una matriz de puntos de control o polos como los nombró originalmente De Casteljau para reducirlos uno por uno hasta llegar a un punto en la curva para un t dado entre 0 para el primer punto de la curva y 1 para el último.

función crlPtReduceDeCasteljau ( puntos , t ) {    deje que retArr = [ puntos . slice () ];      mientras ( puntos . longitud > 1 ) {     deje que los puntos medios sean [];   para ( sea i = 0 ; i + 1 < puntos . longitud ; ++ i ) {         sea ​​ax = puntos [ i ][ 0 ];   sea ​​ay = puntos [ i ][ 1 ];   sea ​​bx = puntos [ i + 1 ][ 0 ];   sea ​​por = puntos [ i + 1 ][ 1 ];    // a * (1-t) + b * t = a + (b - a) * tpuntos medios . empujar ([ax + ( bx - ax ) * t ,      ay + ( por - ay ) * t ,      ]);} retArr . push ( puntos medios ) puntos = puntos medios ;  }devolver retArr ; }

Por ejemplo,

 var polos = [ [0, 128], [128, 0], [256, 0], [384, 128] ] crlPtReduceDeCasteljau (polos, .5)

devuelve la matriz

 [ [ [0, 128], [128, 0], [256, 0], [384, 128] ], [[64, 64], [192, 0], [320, 64]], [ [128, 32], [256, 32]], [ [192, 32]], ]

¿Qué puntos y segmentos los unen se representan a continuación?

Segmentos de línea intermedios obtenidos aplicando recursivamente interpolación lineal a puntos adyacentes.

Véase también

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

Referencias

1. Delgado, J.; Mainar, E.; Peña, JM (1 de octubre de 2023). "Sobre la precisión de los algoritmos de tipo de Casteljau y las representaciones de Bernstein". Computer Aided Geometric Design . 106 : 102243. doi :10.1016/j.cagd.2023.102243. ISSN  0167-8396.
2. Woźny, Paweł; Chudy, Filip (1 de enero de 2020). "Algoritmo geométrico de tiempo lineal para evaluar curvas de Bézier". Diseño asistido por computadora . 118 : 102760. arXiv : 1803.06843 . doi :10.1016/j.cad.2019.102760. ISSN  0010-4485.
3. Fuda, Chiara; Ramanantoanina, Andriamahenina; Hormann, Kai (2024). "Una comparación exhaustiva de algoritmos para evaluar curvas de Bézier racionales". Notas de investigación sobre aproximación en dolomitas . 17 (9/2024): 56–78. doi :10.14658/PUPJ-DRNA-2024-3-9. ISSN  2035-6803.

• Farín, Gerald E.; Hansford, Dianne (2000). Los fundamentos de CAGD . Natick, MA: AK Peters. ISBN 978-1-56881-123-9.

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 recursión
• 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.