Algoritmo de De Casteljau

Algoritmo de De Casteljau

El algoritmo de de Casteljau es, en el campo del análisis numérico de la matemática, un método recursivo para calcular polinomios en la forma de Bernstein o base de Bernstein, o en las curvas de Bézier. Toma su nombre del ingeniero Paul de Casteljau. Este algoritmo es un método numéricamente estable para evaluar las curvas de Bézier.

Aunque el algoritmo de De Casteljau es relativamente lento en las configuraciones, si se compara con otros es numéricamente más estable.

Contenido

Idea base

La idea principal de este algoritmo surge de requisitos gráficos en informática y se basa en el hecho que una restricción de una curva de Bézier es también una curva de Bézier. Entonces, a partir de la curva inicial se encuentran los puntos de control de dos curvas definidas por t\in[0,1/2] y t\in[1/2,1] y se fijan los pixeles que corresponden al punto por t=\frac{1}{2}. Donde se iteran los procesos sobre cada una de las dos curvas hasta que la precisión sea inferior al pixel.

Definición

Dado un polinomio B en forma de Bernstein de grado n

B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t),

donde b es un polinomio base de Bernstein, el polinomio en el punto t0 puede ser calculado con la relación de recurrencia

\beta_i^{(0)} := \beta_i \mbox{ , } i=0,\ldots,n
\beta_i^{(j)} := \beta_i^{(j-1)} (1-t_0) + \beta_{i+1}^{(j-1)} t_0 \mbox{ , } i = 0,\ldots,n-j \mbox{ , } j= 1,\ldots n

con

B(t_0)=\beta_0^{(n)}.

Anotaciones

En el cálculo manual es útil escribir los coeficientes en un esquema triangular del tipo:


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

En la elección de un punto t0 por el cual calcular el polinomio de Bernstein se pueden usar las diagonales del esquema triangular para costruir una división del polinomio.



B(t) = \sum_{i=0}^n \beta_i^{(0)} b_{i,n}(t) \mbox{ , } \qquad t \in [0,1]

hasta

B_1(t) = \sum_{i=0}^n \beta_0^{(i)} b_{i,n}\left(\frac{t}{t_0}\right) \mbox{ , } \qquad t \in [0,t_0]

y

B_2(t) = \sum_{i=0}^n \beta_{n-i}^{(i)} b_{i,n}\left(\frac{t-t_0}{1-t_0}\right) \mbox{ , } \qquad t \in [t_0,1]


Ejemplo

Si se desea calcular el valor del polinomio de Bernstein de grado 2 con los coeficientes:

\beta_0^{(0)} = \beta_0
\beta_1^{(0)} = \beta_1
\beta_2^{(0)} = \beta_2

en el punto t0.

Se efectúa la recursión con:

\beta_0^{(1)} = \beta_0^{(0)} (1-t_0) + \beta_1^{(0)}t_0 = \beta_0(1-t_0) + \beta_1 t_0
\beta_1^{(1)} = \beta_1^{(0)} (1-t_0) + \beta_2^{(0)}t_0 = \beta_1(1-t_0) + \beta_2 t_0

y a la segunda iteración la recursión concluye en:

\begin{matrix} \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{matrix}

que es el polinomio de Bernstein buscado de grado 2.

Referencias

  • Farin, Gerald & Hansford, Dianne (2000). The Essentials of CAGD. Natic, MA: A K Peters, Ltd. ISBN 1-56881-123-3

Wikimedia foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Mira otros diccionarios:

  • Algoritmo de de Casteljau — Saltar a navegación, búsqueda El algoritmo de de Casteljau es, en el campo del análisis numérico de la matemática, un método recursivo para calcular polinomios en la forma de Bernstein o base de Bernstein o en las curvas Bézier, toma su nombre de …   Wikipedia Español

  • Algoritmo de Horner — En el campo matemático del análisis numérico, el Algoritmo de Horner, llamado así por William George Horner, es un algoritmo para evaluar de forma eficiente polinomios de una forma monomial. Dado el polinomio donde son números reales, queremos… …   Wikipedia Español

  • Polinomio de Bernstein — Saltar a navegación, búsqueda Los polinomios de Bernstein o polinomios en la base de Bernstein son una particular clase de polinomios (en el campo de los números reales), tales polinomios son utilizados dentro del ámbito del análisis numérico. El …   Wikipedia Español

  • Curva de Bézier — Saltar a navegación, búsqueda Construcción de una curva de Bézier. Se denomina curvas de bezier a un sistema que se desarrolló hacia los años 1960, para el trazado de dibujos técnicos, en el diseño aeronáutico y de automóviles. Su denominación es …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”