En el camp matemàtic de l'anàlisi numèrica, l'algorisme de De Casteljau és un mètode recursiu per avaluar polinomis en forma de Bernstein o corbes de Bézier, que rep el nom del seu inventor Paul de Casteljau. L'algorisme de De Casteljau també es pot utilitzar per dividir una sola corba de Bézier en dues corbes de Bézier amb un valor de paràmetre arbitrari.
L'algorisme és numèricament estable en comparació amb l'avaluació directa de polinomis. La complexitat computacional d'aquest algorisme és , on d és el nombre de dimensions i n és el nombre de punts de control. Existeixen alternatives més ràpides.
Definició Una corba de Bézier (de grau , amb punts de control ) es pot escriure en forma de Bernstein de la següent manera on és un polinomi de base de Bernstein La corba en el punt es pot avaluar amb la relació de recurrència Aleshores, l'avaluació de
al punt es pot avaluar en operacions. El resultat ve donat per A més, la corba de Bézier es pot dividir en un punt en dues corbes amb els seus respectius punts de control:
Interpretació geomètrica La interpretació geomètrica de l'algorisme de De Casteljau és senzilla.
Considereu una corba de Bézier amb punts de control Connectant els punts consecutius creem el polígon de control de la corba. Ara, subdivideix cada segment de línia d'aquest polígon amb la raó i connecteu els punts que obtingueu. D'aquesta manera arribeu al nou polígon amb un segment menys. Repetiu el procés fins que arribeu al punt únic; aquest és el punt de la corba corresponent al paràmetre .
La imatge següent mostra aquest procés per a una corba de Bézier cúbica: dreta Cal tenir en compte que els punts intermedis que es van construir són, de fet, els punts de control per a dues noves corbes de Bézier, ambdues exactament coincidents amb l'antiga. Aquest algorisme no només avalua la corba a , però divideix la corba en dues parts a , i proporciona les equacions de les dues subcorbes en forma de Bézier.
La interpretació donada anteriorment és vàlida per a una corba de Bézier no racional. Per avaluar una corba de Bézier racional en , podem projectar el punt a ; per exemple, una corba en tres dimensions pot tenir els seus punts de control i pesos projectat als punts de control ponderats L'algorisme continua com de costum, interpolant en Els punts quadridimensionals resultants es poden projectar de nou en tres espais amb una divisió de perspectiva.
En general, les operacions sobre una corba (o superfície) racional són equivalents a les operacions sobre una corba no racional en un espai projectiu. Aquesta representació com a "punts de control ponderats" i pesos sovint és convenient a l'hora d'avaluar corbes racionals.
Notació Quan es fa el càlcul a mà, és útil escriure els coeficients en un esquema triangular com a
Quan escollim un punt t 0 per avaluar un polinomi de Bernstein, podem utilitzar les dues diagonals de l'esquema del triangle per construir una divisió del polinomi. en i
Corba de Bézier miniatura|Una corba de Bézier de segon ordre miniatura|Una corba de Bézier de tercer ordre En avaluar una corba de Bézier de grau n en un espai tridimensional amb n + 1 punts de control P i amb Dividim la corba de Bézier en tres equacions separades miniatura|Una corba de Bézier de quart ordre
que avaluem individualment mitjançant l'algorisme de De Casteljau.
Exemple Volem avaluar el polinomi de Bernstein de grau 2 amb els coeficients de Bernstein en el punt t0.
Comencem la recursió amb i amb la segona iteració la recursió s'atura amb que és el polinomi de Bernstein esperat de grau 2.
Implementacions Aquí teniu exemples d'implementacions de l'algorisme de De Casteljau en diversos llenguatges de programació.
Haskell deCasteljau :: Double -> [(Double, Double)] -> (Double, Double) deCasteljau t [b] = b deCasteljau t coefs = deCasteljau t reduced where reduced = 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
Python def de_casteljau(t: float, coefs: list[float]) -> float: """De Casteljau's algorithm.""" beta = coefs.copy() # values in this list are overridden n = len(beta) for j in range(1, n): for k in range(n - j): beta[k] = beta[k] * (1 - t) + beta[k + 1] * t return beta
Java public double deCasteljau(double t, double[] coefficients) { double[] beta = coefficients; int n = beta.length; for (int i = 1; i < n; i++) { for (int j = 0; j < (n - i); j++) { beta[j] = beta[j] * (1 - t) + beta[j + 1] * t;
return beta; }
Referències
Categoria:Anàlisi numèrica