De Boor algoritme

FONT SIZE:
fontsize_dec
fontsize_inc
Januar 4, 2017 Dylan Bille D 0 8

I den matematiske underfelt af numerisk analyse af de Boor algoritme er en hurtig og numerisk stabil algoritme for at vurdere spline-kurver i B-spline form. Det er en generalisering af de Casteljau algoritme for Bézier kurver. Algoritmen blev udtænkt af Carl R. de Boor. Forenklede, potentielt hurtigere varianter af de Boor algoritmen er blevet oprettet, men de lider af relativt lavere stabilitet.

Introduktion

Den generelle indstilling er som følger. Vi ønsker at konstruere en kurve, hvis form er beskrevet ved en sekvens af p point, som spiller rollen som en kontrol polygon. Kurven kan beskrives som en funktion af en parameter x. Til at passere gennem sekvensen af ​​punkter, skal kurven opfylde. Men dette er ikke helt tilfældet: generelt er vi tilfredse med, at kurven "tilnærmer" kontrol polygon. Vi antager, at u0, ..., up-1 er givet til os sammen med.

En metode til at løse dette problem er ved at splines. En spline er en kurve, der er en stykvis n grad polynomium. Det betyder, at på et interval [ui, ui + 1), kurven skal være lig med et polynomium af graden højst n. Det kan være lig med forskellige polynomier på forskellige intervaller. De polynomier skal synkroniseres: når polynomier fra intervaller [ui-1, ui) og [ui, ui + 1) mødes på det punkt ui, skal de have samme værdi på dette tidspunkt og deres derivater skal være lig.

De Boor algoritme er en algoritme, der givet U0, ..., up-1 og finder værdien af ​​spline-kurve ved et punkt på x. Det bruger O + O operationer, hvor n er graden og p antallet af kontrolpunkter i s.

Oversigt over algoritmen

Antag, at vi ønsker at vurdere spline-kurve for en parameterværdi. Vi kan udtrykke kurven som

hvor

og


På grund af beliggenheden spline ejendom,

Så værdien bestemmes af kontrolpunkter; de andre kontrolpunkter har ingen indflydelse. De Boor algoritme, der er beskrevet i næste afsnit, er en procedure, som effektivt beregner udtrykket for.

Algoritmen

Antag og for. Nu beregner

med

Derefter.

  0   0

Kommentarer - 0

Ingen kommentar

Tilføj en kommentar

smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile smile smile smile smile
smile smile smile smile
Tegn tilbage: 3000
captcha