Algoritmul de Casteljo

În matematica computațională , algoritmul de Castelljou , numit după inventatorul său Paul de Castelljou , este o metodă recursivă pentru determinarea formei polinoamelor Bernstein sau curbelor Bezier . Algoritmul de Castelljot poate fi folosit și pentru a împărți o curbă Bezier în două părți printr-o valoare arbitrară a parametrului . $(t)$

Avantajul algoritmului este stabilitatea sa de calcul mai mare în comparație cu metoda directă.

Descriere

Având în vedere un polinom Bernstein B de gradul n

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

unde b este baza polinomului Bernstein , polinomul în punctul t 0 poate fi definit folosind relația de recurență

\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

Apoi definiția punctului poate fi definită în pașii algoritmului. Rezultatul este dat de: $B$ $t_0$ $n$ $B(t_{0})$

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

De asemenea, o curbă Bézier poate fi împărțită într-un punct în două curbe cu puncte de ancorare corespunzătoare: $B$ $t_0$

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

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

Interpretare geometrică

Interpretarea geometrică a algoritmului lui de Castelljou este simplă:

Având în vedere o curbă Bezier cu puncte de ancorare . Conectând în serie punctele de referință de la primul la ultimul, obținem o linie întreruptă . $\scriptstyle P_{0},...,P_{n)$
Împărțim fiecare segment rezultat al acestei linii întrerupte în raport și conectăm punctele rezultate. Ca rezultat, obținem o linie întreruptă cu un număr de segmente mai mic decât linia întreruptă inițială. $\scriptstyle t:(1-t)$
Repetăm procesul până obținem un singur punct. Acest punct va fi punctul de pe curba Bezier dată cu parametrul . $\scriptstyle t$

Următoarea ilustrație demonstrează acest proces pentru o curbă Bezier cubică:

De menționat că punctele intermediare obținute în timpul procesului de construcție sunt punctele de referință pentru două noi curbe Bezier, care coincid exact cu cea inițială, și împreună dau curba Bezier originală. Acest algoritm nu numai că determină punctul curbei la , ci și împarte curba în două părți la , și oferă, de asemenea, o descriere a celor două sub-curbe în formă Bezier (în reprezentare parametrică ). $\scriptstyle t$ $\scriptstyle t$

Algoritmul descris este valabil pentru curbele Bezier neraționale. Pentru a calcula curbe raționale în , puteți proiecta un punct în ; de exemplu, o curbă în spațiul 3D trebuie să aibă puncte de control și greutăți proiectate în puncte de control al greutății . Apoi, de obicei, algoritmul continuă să interpoleze în . Punctele 4D rezultate pot fi proiectate înapoi în spațiul 3D folosind diviziunea în perspectivă. $\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})\}$ $\scriptstyle \mathbf {R} ^{4)$

În general, operațiile pe curbe (sau suprafețe) raționale sunt echivalente cu operațiile pe curbe neraționale într-un spațiu proiectiv . Reprezentarea punctelor de ancorare ca ponderate este adesea utilă pentru definirea curbelor raționale.

Algoritmul de Casteljo

Descriere

Interpretare geometrică

Link -uri

Vezi și