Casteljo algoritmus

A számítási matematikában a feltalálója, Paul de Castelljou után elnevezett de Castelljou-algoritmus egy rekurzív módszer a Bernstein-polinomok vagy Bezier-görbék alakjának meghatározására . A de Castelljot algoritmus arra is használható, hogy a paraméter tetszőleges értékével két részre bontsa a Bezier-görbét . ${\megjelenítési stílus (t)}$

Az algoritmus előnye a direkt módszerhez képest nagyobb számítási stabilitása .

Leírás

Adott egy n fokú Bernstein - polinom

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

ahol b a Bernstein -polinom alapja , a t 0 pontban lévő polinom az ismétlődési reláció segítségével definiálható

\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

Ekkor az algoritmus lépéseiben definiálható a pont definíciója. Az eredményt a következő adja: $B$ $t_0$ $n$ $B(t_{0})$

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

Ezenkívül egy Bézier-görbe egy ponton két görbére bontható a megfelelő rögzítési pontokkal: $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)))

Geometriai értelmezés

De Castelljou algoritmusának geometriai értelmezése egyszerű:

Adott egy Bezier-görbe horgonypontokkal . Ha sorba kapcsoljuk a referenciapontokat az elsőtől az utolsóig, szaggatott vonalat kapunk . ${\displaystyle \scriptstyle P_{0},...,P_{n))$
Ennek a szaggatott vonalnak minden eredményül kapott szakaszát elosztjuk az arányban , és összekapcsoljuk a kapott pontokat. Ennek eredményeként egy szaggatott vonalat kapunk, amelynek szegmenseinek száma eggyel kevesebb, mint az eredeti szaggatott vonal. $\scriptstyle t:(1-t)$
Addig ismételjük a folyamatot, amíg egyetlen pontot nem kapunk. Ez a pont lesz az adott Bezier-görbe pontja a paraméterrel . $\scriptstyle t$

A következő ábra ezt a folyamatot szemlélteti egy köbös Bezier-görbe esetén:

Megjegyzendő, hogy az építési folyamat során kapott köztes pontok két új Bezier-görbe referenciapontjai, amelyek pontosan egybeesnek az eredetivel, és együtt adják az eredeti Bezier-görbét. Ez az algoritmus nem csak a görbe pontját határozza meg , hanem két részre osztja a görbét pontban , és a két részgörbe leírását is adja Bezier formában ( paraméteres ábrázolásban ). $\scriptstyle t$ $\scriptstyle t$

A leírt algoritmus nem racionális Bezier-görbékre érvényes. A racionális görbék kiszámításához bevetíthet egy pontot a -ba ; például egy 3D térben lévő görbének rendelkeznie kell ellenőrző pontokkal , és súlyokat kell vetíteni súlyellenőrzési pontokra . Ezután általában az algoritmus interpolál -ban . Az így kapott 4D pontok perspektivikus felosztással visszavetíthetők a 3D térbe. $\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))$

Általában a racionális görbéken (vagy felületeken) végzett műveletek egyenértékűek a projektív térben végzett nem racionális görbékkel végzett műveletekkel . A rögzítési pontok súlyozottként való ábrázolása gyakran hasznos a racionális görbék meghatározásához.

Casteljo algoritmus

Leírás

Geometriai értelmezés

Linkek

Lásd még