Casteljon algoritmi

Laskennallisessa matematiikassa keksijänsä Paul de Castelljoun mukaan nimetty de Castelljou - algoritmi on rekursiivinen menetelmä Bernsteinin polynomien tai Bezier - käyrien muodon määrittämiseksi . De Castelljot - algoritmia voidaan käyttää myös Bezier - käyrän jakamiseen kahteen osaan parametrin mielivaltaisella arvolla . ${\näyttötyyli (t)}$

Algoritmin etuna on sen parempi laskennallinen stabiilisuus verrattuna suoraan menetelmään.

Kuvaus

Annettu Bernsteinin polynomi B , jonka aste on n

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

missä b on Bernsteinin polynomin kanta, pisteen t 0 polynomi voidaan määrittää käyttämällä toistuvuusrelaatiota

\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

Sitten pisteen määritelmä voidaan määritellä algoritmin vaiheissa. Tuloksen antaa: $B$ $t_0$ $n$ $B(t_{0})$

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

Bézier-käyrä voidaan myös jakaa pisteessä kahdeksi käyrään vastaavilla ankkuripisteillä: $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)))

Geometrinen tulkinta

De Castelljoun algoritmin geometrinen tulkinta on yksinkertainen:

Annettu Bezier-käyrä ankkuripisteineen . Kytkemällä sarjaan vertailupisteet ensimmäisestä viimeiseen, saadaan katkoviiva . ${\displaystyle \scriptstyle P_{0},...,P_{n))$
Jaamme tämän katkoviivan jokaisen tuloksena olevan segmentin suhteessa ja yhdistämme tuloksena olevat pisteet. Tuloksena saamme katkoviivan, jonka segmenttien lukumäärä on yksi pienempi kuin alkuperäinen katkoviiva. $\scriptstyle t:(1-t)$
Toistamme prosessia, kunnes saamme yhden pisteen. Tämä piste on piste annetulla Bezier-käyrällä parametrilla . $\scriptstyle t$

Seuraava kuva havainnollistaa tätä prosessia kuutiometriselle Bezier-käyrälle:

On huomattava, että rakennusprosessin aikana saadut välipisteet ovat vertailupisteitä kahdelle uudelle Bezier-käyrälle, jotka täsmäävät alkuperäisen kanssa ja yhdessä muodostavat alkuperäisen Bezier-käyrän. Tämä algoritmi ei ainoastaan määritä käyrän pistettä kohdassa , vaan myös jakaa käyrän kahteen osaan kohdassa , ja tarjoaa myös kuvauksen kahdesta osakäyrästä Bezier-muodossa ( parametrisessa esityksessä ). $\scriptstyle t$ $\scriptstyle t$

Kuvattu algoritmi pätee ei-rationaalisille Bezier-käyrille. Laskeaksesi rationaalisia käyriä , voit projisoida pisteen sisään ; esimerkiksi 3D-avaruuden käyrällä on oltava ohjauspisteet ja painot projisoituna painonhallintapisteisiin . Sitten yleensä algoritmi etenee interpoloimaan sisään . Tuloksena saadut 4D-pisteet voidaan projisoida takaisin 3D-avaruuteen käyttämällä perspektiivijakoa. $\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))$

Yleensä rationaalisten käyrien (tai pintojen) operaatiot vastaavat ei-rationaalisten käyrien operaatioita projektitiivisessa avaruudessa . Kiinnityspisteiden esittäminen painotettuina on usein hyödyllistä rationaalisten käyrien määrittämisessä.

Casteljon algoritmi

Kuvaus

Geometrinen tulkinta

Linkit

Katso myös