Curbe Bézier#

Unele funcții sunt mult prea complicate pentru a putea fi reprezentate în starea lor obișnuită. Din acest motiv, se folosesc curbele Bézier. Până a ajunge însă la acestea, este necesară o trecere în revistă a polinoamelor Bernstein.

Polinoame Bernstein#

Fie \(B_n^k(x)\in\mathbb{R}[x]\), unde \(n\in\mathbb{N}\) și \(k\in\overline{0,n}\), un polinom care este definit folosind umătoarea formulă, provenită din dezvoltarea \([x+(1-x)]^n=1\):

\[ \boxed{ B_n^k(x) = C_n^k\cdot x^k\cdot (1-x)^{n-k} }\,,\,\,\forall k\in\overline{0,n} \]

Atunci, polinomul \(B_n^k\) se numește bază polinomială Bernstein (alte notații cunoscute cuprind \(B_k^n\) și \(B_{k,n}\); acestea sunt, evident, echivalente).

Proprietăți#

Aceste baze polinomiale au o serie de proprietăți foarte importante. Vom studia și noi câteva dintre acestea, ținând cont de o valoarea \(n\in\mathbb{N}\) fixă:

Semipozitivitatea. Cu alte cuvinte, se respectă relația:
\[ \boxed{B_n^k(x)\geq0}\,,\,\,\forall x\in[0,1],\,k\in\overline{0,n} \]
Partiția unității. Prin însumarea elementelor, se obține \(1\), adică:
\[ \boxed{\sum_{k=0}^nB_n^k(x)=1}\,,\,\,\forall x\in[0,1] \]
Simetria. Aceasta răsare din relația:
\[ \boxed{B_n^k(x)=B_n^{n-k}(x)}\,,\,\,\forall x\in[0,1],\,k\in\overline{0,n} \]

Maxim unic. Acesta se află în punctul:
\[ \boxed{\argmax_{x\in[0,1]} B_n^k(x)=\frac{k}{n}}\,,\,\,\forall k\in\overline{0,n},\,n\neq0 \]

Recurența bazelor polinomiale Bernstein#

Fie \(B_n^k(x)\in\mathbb{R}[x]\), unde \(n\in\mathbb{N}^*\) și \(k\in\overline{1,n}\), o bază polinomială Bernstein. Atunci, apare următoarea recurență:

\[ \boxed{ B_n^k(x) = (1-x)B_{n-1}^{k}(x)+xB_{n-1}^{k-1}(x) }\,,\,\forall x\in[0,1] \]

Demonstrație

Se vor realiza pur și simplu calculele:

\[\begin{split} (1-x)B_{n-1}^{k}(x)+xB_{n-1}^{k-1}(x) & = (1-x) C_{n-1}^k x^k (1-x)^{n-1-k}+x C_{n-1}^{k-1} x^{k-1} (1-x)^{n-1-(k-1)}\\ &= C_{n-1}^k x^k (1-x)^{n-k}+C_{n-1}^{k-1} x^k (1-x)^{n-k}\\ &= \left[C_{n-1}^k+C_{n-1}^{k-1}\right] x^k(1-x)^{n-k}\\ &= C_n^k x^k(1-x)^{n-k}\\ &= B_n^k(x),\,\forall x\in[0,1],\,n\in\mathbb{N}^*,\,k\in\overline{1,n} \end{split}\]

Deci, cunoscând ecuația generală a unei baze polinomiale Bernstein, obținem:

\[(1-x)B_{n-1}^{k}(x)+xB_{n-1}^{k-1}(x) = B_n^k(x)\]

Polinoame Bernstein#

Fie \(f\in\mathbb{R}[x]\) un polinom definit ca o sumă de baze polinomiale Bernstein scalate, adică funcția respectă formula:

\[\begin{split} f(x)&=\alpha_0B_n^0(x)+\alpha_1B_n^1(x)+\dots+\alpha_nB_n^n(x)\\ &=\sum_{k=0}^n\alpha_kB_n^k(x) \end{split}\]

unde \(n\in\mathbb{N}\) și \(\alpha_0,\dots,\alpha_n\in\mathbb{R}\). Atunci, polinomul \(f\) se numește polinom Bernstein.

Vom folosi aceste polinoame pentru a defini curbele Bézier; acestea reprezintă o modalitate prin care se pot aproxima forme din lumea reală care, din punct de vedere matematic, fie nu pot fi reprezentate, fie sunt mult prea complicate și se preferă această formă

Notă

Aplicabilitatea acestor curbe este greu de supraestimat - ele apar în grafica pe calculator și animație, iar invenția lor este datorată matematicianului Paul de Casteljanu, care a dezvoltat o metodă numerică stabilă pentru evaluarea curbelor.

Deși patentat în Franța, algoritmul ajunge publicat abia în anii '80, în timp ce Pierre Bézier deja l-a făcut cunoscut în anii '60, lucrând la aspectul fizic al mașinilor Renault.

Curbe Bézier#

Fie \(M=\Big\{P_k\in\mathbb{R}^\mu\,|\,k\in\overline{0,n}\Big\}\), unde \(n,\mu\in\mathbb{N}^*\), \(\mu\geq2\), o mulțime de \(n+1\) puncte distincte.

Atunci, curba Bézier \(B:[0,1]\rightarrow\mathbb{R}^\mu\) care trece prin toate aceste puncte este definită sub forma acestui polinom Bernstein:

\[ \boxed{B(t)=\sum_{k=0}^nP_kB_n^k(t)}\,\Leftrightarrow B(t)=\sum_{k=0}^nP_k\cdot C_n^k\cdot t^k(1-t)^{n-k},\,\forall t\in[0,1] \]

Vizualizare#

Algoritmul este cel mai bine vizionat dinamic (de exemplu, pe Wikipedia[60]). Cu toate acestea, cartea va prezenta o ilustrație statică a algoritmului, menită dezvoltării unei înțelegeri în profunzime a acestei probleme (totodată, cu bune și cu rele, examenul la Metode Numerice este pe hârtie, motiv pentru care acesta trebuie explicat static).

Vom trata conceptul cu seriozitatea pe care o merită. Să considerăm două puncte în plan, \(P_0(0,1)\), \(P_1(1,0)\). În această situație, putem observa cum curba Bézier va fi o simplă dreaptă. Să adăugăm la setul inițial de puncte și valoarea \(P_2(2,2)\) și să trasăm segmentele \([P_0P_1]\) și \([P_1P_2]\):

Segmentele \([P_0P_1]\) și \([P_1P_2]\)

Pentru a construi curba Bézier, va trebui să facem apel la imaginație - ne vom imagina un segment care conține un capăt \(Q_0\in [P_0P_1]\) și un capăt \(Q_1\in [P_1P_2]\). Deplasăm acum acest segment astfel încât să nu se modifice proporțiile:

\[ \alpha=\frac{Q_0-P_0}{P_1-P_0}=\frac{Q_1-P_1}{P_2-P_1} \]

Deplasarea dreptei (\(20\%\) progres)

Deplasarea dreptei (\(40\%\) progres)

Atragem acum atenția asupra punctului \(R_0\in [Q_0Q_1]\) care se află la o distanță cunoscută față de \(Q_0\), \(\alpha\):

Punctul \(R_0\) relativ față de deplasarea dreptei (\(20\%\) progres)

Punctul \(R_0\) relativ față de deplasarea dreptei (\(40\%\) progres)

Ducând toate punctele posibile \(R_0\) (indiferent de deplasare), se va obține curba Bézier. Cum este imposibil să desenăm toate aceste drepte, procesul va trebui să aibă loc în imaginația noastră:

Curba Bézier, alături de două segmente ajutătoare

Notă

Matematic, curba ar avea formula:

\[ B(t)=\begin{bmatrix} 2t\\ 2t^2+(1-t)^2 \end{bmatrix}\Rightarrow B_y(x)=2\left(\frac{x}{2}\right)^{2}+\left(1-\frac{x}{2}\right)^{2} \]

Vom mai adăuga acum un punct, \(P_3(3,0)\). Asemănător, se vor crea segmentele \([Q_0Q_1]\) și \([Q_1Q_2]\), și, pe același principiu, va apărea în ecuație segmentul \([R_0R_1]\), ce păstrează proporția constantă \(\alpha\) între punctele \(Q\). Va răsări totodată punctul \(S\in[R_0R_1]\). Arătăm mai jos cum trebuie imaginate aceste grafice:

Punctul \(S\) relativ față de deplasarea dreptei (\(20\%\) progres)

Curba Bézier, alături de segmentele ajutătoare (\(20\%\) progres)

Algoritmul De Casteljau#

Curbele Bézier sau, la modul general, polinoamele Bernstein, pot fi calculate folosind algoritmul recursiv propus de Paul de Casteljau.

În ciuda dezavantajului temporal în care se află comparativ cu metoda directă, algoritmul este folosit în practică deoarece produce rezultate mai stabile din punct de vedere numeric.

Așadar, fie \(M=\Big\{P_k\in\mathbb{R}^\mu\,|\,k\in\overline{0,n}\Big\}\), unde \(n,\mu\in\mathbb{N}^*\) și \(\mu\geq2\), o mulțime de \(n+1\) puncte distincte.

Totodată, se definesc polinoamele ajutătoare \(\beta_i^j:[0,1]\rightarrow\mathbb{R}^\mu\), \(i\in\overline{0,n}\), \(j\in\overline{0,i}\), de forma:

\[ \boxed{ \beta_i^j(t)=\begin{cases} P_i,&\text{dacă } j=0\\ (1-t)\beta_i^{j-1}(t)+t\beta_{i+1}^{j-1}(t),&\text{dacă } i\neq0 \end{cases} }\,,\,\,\forall i\in\overline{0,n},\,j\in\overline{0,i} \]

Astfel, curba Bézier definită de mulțimea \(M\) va avea forma \(B(t)=\beta_0^n(t)\).

Pentru a nu se greși recurența, propunem următoarea schemă ajutătoare (când \(n=3\)):

Desen ce ilustrează recurența algoritmului De Casteljau

Ilustrația anterioară poate fi interpretată în felul următor:

O săgeată roșie din \(A\) în \(B\) va reprezenta că \(A\) contribuie cu \((1-t)\) rezultatului \(B\);
O săgeată albastră din \(A\) în \(B\) va reprezenta că \(A\) contribuie cu \(t\) rezultatului \(B\).

Aceste detalii sunt explicate și pe desen.

Cod ilustrativ#

Vom implementa algoritmul De Casteljau în Matlab, adică funcția de_casteljau. Aceasta primește:

M - funcția (numerică) de interpolat;
t - punctul relativ în care se dorește evaluarea algoritmului, echivalentul lui \(t\in[0,1]\).

Codul de mai jos returnează p, evaluarea algoritmului în punctul relativ dat.

function p = de_casteljau(M, t)
    n = size(M)(1);
    beta = M;
    for j = [1 : n]
        for i = [1 : n-j]
            beta(i,:) = (1-t) .* beta(i,:) + t .* beta(i+1,:);
        end
    end
    p = beta(1,:);
end

Licență#

The book "Metode Numerice", written by Valentin-Ioan Vintilă, is licensed under CC BY-NC-SA 4.0