Algoritme af Casteljo

I beregningsmatematik er de Castelljou-algoritmen , opkaldt efter dens opfinder Paul de Castelljou , en rekursiv metode til at bestemme formen på Bernstein-polynomier eller Bezier-kurver . De Castelljot-algoritmen kan også bruges til at opdele en Bezier-kurve i to dele med en vilkårlig værdi af parameteren . $(t)$

Fordelen ved algoritmen er dens højere beregningsstabilitet sammenlignet med den direkte metode.

Beskrivelse

Givet et Bernstein polynomium B af grad n

B(t)=\sum _{i=0}^{n}\beta _{i}b_{i,n}(t),

hvor b er grundlaget for Bernstein -polynomiet, kan polynomiet i punktet t 0 defineres ved hjælp af gentagelsesrelationen

\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,nj{\mbox{, }}j=1,\ldots,n

Derefter kan definitionen på punktet defineres i algoritmens trin. Resultatet er givet af: $B$ $t_0$ $n$ $B(t_{0})$

B(t_{0})=\beta _{0}^{(n)}.

Også en Bézier-kurve kan opdeles i et punkt i to kurver med tilsvarende ankerpunkter: $B$ $t_0$

{\displaystyle \beta _{0}^{(0)},\beta _{0}^{(1)},\ldots ,\beta _{0}^{(n)))

{\displaystyle \beta _{0}^{(n)},\beta _{1}^{(n-1)},\ldots ,\beta _{n}^{(0)))

Geometrisk fortolkning

Den geometriske fortolkning af de Castelljous algoritme er enkel:

Givet en Bezier-kurve med ankerpunkter . Ved at seriekoble referencepunkterne fra det første til det sidste, får vi en stiplet linje . ${\displaystyle \scriptstyle P_{0},...,P_{n))$
Vi deler hvert resulterende segment af denne stiplede linje i forholdet og forbinder de resulterende punkter. Som et resultat får vi en stiplet linje med antallet af segmenter en mindre end den oprindelige stiplede linje. $\scriptstyle t:(1-t)$
Vi gentager processen, indtil vi får et enkelt point. Dette punkt vil være punktet på den givne Bezier-kurve med parameteren . $\scriptstyle t$

Følgende illustration viser denne proces for en kubisk Bezier-kurve:

Det skal bemærkes, at de mellemliggende punkter opnået under byggeprocessen er referencepunkterne for to nye Bezier-kurver, som nøjagtigt falder sammen med den oprindelige, og tilsammen giver den originale Bezier-kurve. Denne algoritme bestemmer ikke kun punktet på kurven ved , men deler også kurven op i to dele ved , og giver også en beskrivelse af de to underkurver i Bezier-form (i parametrisk repræsentation ). $\scriptstyle t$ $\scriptstyle t$

Den beskrevne algoritme er gyldig for ikke-rationelle Bezier-kurver. For at beregne rationelle kurver i , kan du projicere et punkt ind i ; for eksempel skal en kurve i 3D-rum have kontrolpunkter og vægte projiceret ind i vægtkontrolpunkter . Derefter fortsætter algoritmen normalt med at interpolere i . De resulterende 4D-punkter kan projiceres tilbage i 3D-rummet ved hjælp af perspektivdeling. $\scriptstyle \mathbf {R} ^{n}$ $\scriptstyle \mathbf {R} ^{n+1}$ $\scriptstyle \{(x_{i},y_{i},z_{i})\}$ $\scriptstyle \{w_{i}\}$ $\scriptstyle \{(w_{i}x_{i},w_{i}y_{i},w_{i}z_{i},w_{i})\}$ ${\displaystyle \scriptstyle \mathbf {R} ^{4))$

Generelt svarer operationer på rationelle kurver (eller overflader) til operationer på ikke-rationelle kurver i et projektivt rum . At repræsentere ankerpunkter som vægtede er ofte nyttigt til at definere rationelle kurver.

Algoritme af Casteljo

Beskrivelse

Geometrisk fortolkning

Links

Se også