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 , que lleva el nombre de su inventor Paul de Casteljau . El algoritmo de De Casteljau también se puede utilizar para dividir una sola 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 numéricamente más estable .
Definición
Una curva de Bézier (de grado , con puntos de control ) se puede escribir en forma de Bernstein de la siguiente manera
dónde es un polinomio de base de Bernstein
La curva en el punto se puede evaluar con la relación de recurrencia
Luego, la evaluación de en el punto puede ser evaluado en operaciones. El resultado es dado por
Además, la curva de Bézier se puede dividir en un punto en dos curvas con puntos de control respectivos:
Implementación de ejemplo
Aquí hay una implementación de ejemplo del algoritmo de De Casteljau en Haskell :
deCasteljau :: Doble -> [( Doble , Doble )] -> ( Doble , Doble ) deCasteljau t [ b ] = b deCasteljau t coefs = deCasteljau t reducido donde reducido = zip Con ( lerpP t ) coefs ( cola coefs ) lerpP t ( x0 , y0 ) ( x1 , y1 ) = ( lerp t x0 x1 , lerp t y0 y1 ) lerp t a b = t * b + ( 1 - t ) * a
Notas
Al hacer el cálculo a mano, es útil escribir los coeficientes en un esquema de triángulo como
Al elegir un punto t 0 para evaluar un polinomio de Bernstein, podemos usar las dos diagonales del esquema del triángulo para construir una división del polinomio
dentro
y
Ejemplo
Queremos evaluar el polinomio de Bernstein de grado 2 con los coeficientes de Bernstein
en el punto t 0 .
Comenzamos la recursividad con
y con la segunda iteración la recursividad se detiene con
que es el polinomio de Bernstein esperado de grado 2 .
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
con
dividimos la curva de Bézier en tres ecuaciones separadas
que evaluamos individualmente utilizando el algoritmo de De Casteljau.
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.
- Subdividir ahora cada segmento de línea de este polígono con la relación y conecta los puntos que obtienes. De esta manera se llega al nuevo polígono con un segmento menos.
- Repita el proceso hasta llegar al único punto: este es el punto de la curva correspondiente al parámetro .
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 para dos nuevas curvas de Bézier, ambas exactamente coincidentes con la anterior. Este algoritmo no solo evalúa la curva en, pero divide la curva en dos partes en , y proporciona las ecuaciones de las dos subcurvas en forma Bézier.
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 proyectado a los puntos de control ponderados . El algoritmo procede entonces como de costumbre, interpolando en. Los puntos de cuatro dimensiones resultantes se pueden proyectar de nuevo en tres espacios con una división de perspectiva .
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 los "puntos de control ponderados" y los pesos es a menudo conveniente cuando se evalúan curvas racionales.
Ver 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
- Farin, 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 recusión [ revisar la ortografía ]
- Curvas de Bézier y Picasso - Descripción e ilustración del algoritmo de De Casteljau aplicado a curvas de Bézier cúbicas.