En el subcampo matemàtic de l'anàlisis numèric, l'algoritme de De Boor[1] és un algoritme de temps polinomial i numèricament estable per a evaluar curves spline en forma B-spline. És una generalisació de l'algoritme Casteljau per a les curves de Bézier. L'algoritme va ser ideat per Carl R. De Boor. S'han creat variants simplificades i potencialment més ràpides de l'algoritme de De Boor, pero sofrixen una estabilitat comparativament menor.[2][3]

Introducció

L'algoritme de De Boor és un esquema eficient i numèricament estable per a evaluar una curva spline 𝐒(x) en posició x. La curva es construïx a partir d'una suma de funcions B-spline Bi,p(x) multiplicada en valors vectorials potencialment constants 𝐜i, cridats punts de control.

𝐒(x)=∑i𝐜iBi,p(x).

Les B-splines d'orde p+1 són funcions polinòmiques unitàries de grau p definides sobre una quadrícula de nucs t0,…,ti,…,tm (s'utilisen índexs basats en zero en avant). L'algoritme de De Boor utilisa operacions O(p2) + O(p) per a evaluar la curva de spline. Nota: l'artícul principal sobre B-splines i les publicacions clàssiques[1] utilisen una notació diferent: la B-spline és indexada com Bi,n(x)n=p+1.

Soport local

Les B-splines tenen soport local, lo que significa que els polinomis són positius solament en un àmbit finit i zero en atres llocs. La fòrmula de recursió Cox-De Boor[4] mostra açò:

Bi,0(x):={1siti≤x<ti+10deotraforma
Bi,p(x):=x−titi+p−tiBi,p−1(x)+ti+p+1−xti+p+1−ti+1Bi+1,p−1(x).

Permetent que l'índex k definixca l'interval de nucs que conté la posició, x∈[tk,tk+1]. Podem vore en la fòrmula de recursió que solament B-splines en i=k−p,…,k no són zeros per a este interval de nucs. Aixina, la suma es reduïx a:

𝐒(x)=∑i=k−pk𝐜iBi,p(x).

De i≥0 es deduïx que k≥p. De la mateixa manera, veem en la recursividad que l'ubicació del nuc més alt està en l'índex k+1+p . Açò significa que qualsevol interval de nucs [tk,tk+1) que s'use realment deu tindre a lo manco p nucs adicionals abans i despuix. En un programa de computadora, açò generalment es conseguix repetint la primera i l'última ubicació de nuc utilisada p voltes. Per eixemple, per a p=3 i ubicacions de nucs reals (0,1,2), un podria reblir el vector de nucs com (0,0,0,0,1,2,2,2,2).

Vore també

Referències

  1. ↑ 1,0 1,1 C. de Boor [1971], "Subroutine package for calculating with B-splines", Techn.Rep. LA-4728-MS, Els Alamos Sci.Lab, Els Alamos NM; p. 109, 121.
  2. ↑ Lee, E. T. Y.(December 1982).«A Simplified B-Spline Computation Routine».Computing.Springer-Verlag.29(4): 365–371.doi:10.1007/BF02246763.
  3. ↑ Lee, E. T. Y.(1986).«Comments on some B-spline algorithms».Computing.Springer-Verlag.36(3): 229–238.doi:10.1007/BF02240069.
  4. ↑ C. de Boor, p. 90

Bibliografia

  • Carl de Boor (2003). A Practical Guide to Splines, Revised Edition, Springer-Verlag. ISBN 0-387-95366-3.