Algoritmul Casteljau

Casteljau Algoritmul este un algoritm recursiv găsit de către Paul de Casteljau pentru a aproxima eficient polinoame scrise în baza Bernstein .

Acest algoritm poate fi folosit pentru a desena curbe și suprafețe Bézier . Ideea principală în acest caz este că o restricție a unei curbe Bézier este, de asemenea, o curbă Bézier. Algoritmul calculează eficient punctul parametrului și punctele de control ale curbelor de la și la restricții . Algoritmul este apoi aplicat din nou la cele două restricții până când se atinge un criteriu dat (acest criteriu poate fi, de exemplu, că precizia este mai mică de un pixel). $t = T$ $t \ leqslant T$ $t \ geqslant T$

Acest algoritm pare să nu mai fie cel mai eficient deoarece nu ar permite utilizarea antialiasingului dat fiind că funcționează pixel cu pixel și nu oferă informații despre tangentă.

Istoric

Din punct de vedere istoric, cu acest algoritm lucrarea lui M. de Casteljau a început în 1959 la Citroën. Au fost publicate ca rapoarte tehnice, păstrate foarte secrete de Citroën .

Aceste lucrări au rămas necunoscute până în 1975 când W. Böhm a luat cunoștință de ele și le-a făcut publice. Acest algoritm a fost foarte util pentru prelucrarea datelor care utilizează curbele Bézier în multe cazuri (desen, software de modelare etc.) și fără de care nu ar fi fost posibilă dezvoltarea utilizării curbelor Pierre Bézier .

Algoritmul pentru calcularea unui punct

Principiu

Luați în considerare o curbă Bézier definită de punctele de control , unde sunt puncte ale . Aici vrem pur și simplu să calculăm punctul parametrului . $P_ {0}, \ dots, P_ {N}$ $P_i$ $\ mathbb {R} ^ {m}, m \ geqslant 2$ $t \ in [0,1]$

Așa cum se poate vedea în imagine, prin calcularea baricentrelor parametrilor punctelor de control consecutive ale curbei, apoi baricentrele acelorași parametri ai acestor baricentri și așa mai departe iterativ, definim în acest fel o serie de liste de puncte care vom indexa , unde este baricentrul . Ultima listă conține de fapt doar un punct, care este punctul curbei parametrilor . $\ {t, 1-t \}$ $P_ {i} ^ {j}$ $P_ {i} ^ {j}$ $\ {P_ {i} ^ {{j-1}}, P _ {{i + 1}} ^ {{j-1}} \}$ $t$

Algoritm

În pseudo-cod, aceasta oferă:

// Calcul des points intermédiaires Pour j de 1 à N faire | | Pour i de 0 à N-j faire | | | | T[i][j] = t*T[i+1][j-1] + (1-t)*T[i][j-1] | | | Afficher T[0][N] // Afficher (ou stocker) le point

Dovezi ale algoritmului

Pentru a demonstra algoritmul, este necesar să se demonstreze prin inducție limitată că

$\ forall i \ in [0, n], \ forall t \ in [0,1], B (t) = \ sum _ {{k = 0}} ^ {{n}} P _ {{k}} ^ {{0}} B _ {{k}} ^ {{n}} (t) = \ sum _ {{k = 0}} ^ {{ni}} P _ {{k}} ^ {{i }} B_ {{k}} ^ {{ni}} (t)$

Și aplicați formula în , care ne dă rezultatul direct. $i = n$

Recurența este ușor demonstrată prin utilizarea proprietății de construcție a punctelor pentru a împărți suma în două, apoi pentru a face o schimbare a indicelui și folosirea unei proprietăți a polinoamelor Bernstein pentru a combina cele două sume. Pentru reintegrarea cazurilor speciale, este necesar să se utilizeze alte două proprietăți ale polinoamelor Bernstein: și $P_ {i} ^ {j} = (1-t) P_ {i} ^ {{j-1}} + tP _ {{i + 1}} ^ {{j-1}}$ ${\ displaystyle B_ {i} ^ {n} (t) = (1-t) B_ {i} ^ {n-1} (t) + tB_ {i-1} ^ {n-1} (t)}$ $B_ {n} ^ {n} (t) = t ^ {n} = tB _ {{n-1}} ^ {{n-1}}$ $B_ {0} ^ {n} (t) = (1-t) ^ {n} = (1-t) B _ {{0}} ^ {{n-1}}$

Complexitate

Execuția unui pas al algoritmului este pătratică în număr de puncte de control ale curbei (bucla imbricată dă naștere la operații). ${\ mathcal {O}} (N ^ {2})$

Algoritmul în cazul curbelor Bézier

Luați în considerare din nou o curbă Bézier definită de punctele de control , unde sunt puncte ale . $P_ {0}, \ dots, P_ {N}$ $P_i$ $\ mathbb {R} ^ {m}, m> = 2$

Principiu

Aici vom aplica algoritmul anterior pentru a găsi punctul parametrului și pentru a păstra baricentrele intermediare. Acest lucru se datorează faptului că curba Bézier a punctelor de control este egală cu restricția curbei inițiale la , iar curba Bézier a punctelor de control este egală cu restricția curbei originale la . $1/2$ $P_ {0} ^ {i}, i \ in [0, N]$ $t \ leqslant 1/2$ $P_ {i} ^ {{Ni}}, i \ in [0, N]$ $t \ geqslant 1/2$

Afișăm sau stocăm punctul parametrului (care este ) și aplicăm recursiv algoritmul la cele două curbe (cu același număr de puncte de control ca originalul). Se oprește când se verifică un criteriu care trebuie ales (de obicei distanța dintre punctele inferioare unei limite). $1/2$ $P_ {0} ^ {N}$

Mai degrabă decât parametrul , am putea lua orice parametru și algoritmul ar funcționa în continuare, dar parametrul este cel care converge în medie cel mai rapid. Parametrul este, de asemenea, cel pentru care calculele sunt cele mai rapide atunci când se lucrează în coordonate întregi: calculul fiecărui baricentr se face printr-o adunare și o schimbare dreaptă pentru fiecare coordonată, adică fără înmulțire și nici împărțire. $1/2$ $1/2$ $1/2$

Algoritm

Inițializare : atribuiți tabela punctelor de control în $P_ {i} ^ {0}$
Verificați dacă criteriul de oprire nu este verificat : există mai multe posibilități, inclusiv:
- Dacă facem toate calculele cu numere întregi , o alegere poate fi să ne oprim când toate punctele sunt combinate. (adică curba este reprezentată doar de un singur pixel).
- Dacă calculul nu se face pe numere întregi, se poate opri atunci când punctele sunt îndepărtate cu o distanță mai mică decât valoarea aleasă.
- Se efectuează M iterații apoi se conectează punctele obținute (adică se trasează poligonul Bézier), M fiind determinat empiric.
Calculul punctelor intermediare ale algoritmului : există două metode posibile care dau în cele din urmă aceleași puncte:
- Metoda constructivă (prin construirea unei serii de puncte mediane) : punctele sunt definite iterativ astfel încât este punctul mediu al $P_ {0} ^ {1}, \ dots, P _ {{N-1}} ^ {1}, P_ {0} ^ {2}, \ dots, P _ {{N-2}} ^ {2 }, \ dots, P_ {0} ^ {{N-1}}, P_ {1} ^ {{N-1}}, P_ {0} ^ {N}$ $P_ {i} ^ {j}$ $[P_ {i} ^ {{j-1}} P _ {{i + 1}} ^ {{j-1}}]$
- Metoda matricei (prin construirea directă a punctelor ca baricentru, coeficienții fiind dați de matricile Casteljau ) :

${\ begin {pmatrix} P_ {0} ^ {0} \\\ vdots \\ P_ {0} ^ {N} \ end {pmatrix}} = D_ {0} ^ {N} * {\ begin {pmatrix} P_ {0} ^ {0} \\\ vdots \\ P_ {N} ^ {0} \ end {pmatrix}}$ și ${\ begin {pmatrix} P_ {0} ^ {N} \\\ vdots \\ P_ {N} ^ {0} \ end {pmatrix}} = D_ {1} ^ {N} * {\ begin {pmatrix} P_ {0} ^ {0} \\\ vdots \\ P_ {N} ^ {0} \ end {pmatrix}}$

Memorare : punctul care se află pe curbă este memorat . $P_ {0} ^ {N}$
Apel recursiv : algoritmul este apelat pe cele două curbe Bézier intermediare definite de punctele pe de o parte, pe de altă parte. $P_ {0} ^ {i}, i \ in [0, n]$ $P_ {i} ^ {{ni}}, i \ in [0, n]$

Iată un exemplu de implementare a algoritmului în pseudo-cod cu criteriul de oprire egalitatea punctelor (prin urmare lucrăm la numere întregi) și construcția constructivă pentru a calcula punctele intermediare:

Complexitate

Dacă luăm drept criteriu de oprire un număr constant de apeluri recursive, deoarece numărul de puncte de control este constant în timpul apelurilor recursive rămâne constant și că la fiecare pas de recursivitate dublăm numărul de curbe studiate, complexitatea algoritmului este cu numărul a recursiunilor (dar este liniar ca număr de puncte calculate deoarece pentru iterații există puncte calculate). ${\ mathcal {O}} (N ^ {2} * 2 ^ {M})$ $M$ $M$ $2 ^ {M}$

Algoritmul în cazul suprafețelor Bézier

O suprafață Bézier este definită printr-o sumă dublă de puncte: $P (t_ {1}, t_ {2}) = \ sum _ {{i = 1}} ^ {m} \ sum _ {{j = 1}} ^ {n} P _ {{i, j}} B_ {m} ^ {i} (t_ {1}) B_ {n} ^ {j} (t_ {2})$

Principiul algoritmului este de a rescrie formula în forma:

$P (t_ {1}, t_ {2}) = \ sum _ {{i = 1}} ^ {m} B_ {m} ^ {i} (t_ {1}) \ left (\ sum _ {{j = 1}} ^ {n} P _ {{i, j}} B_ {n} ^ {j} (t_ {2}) \ dreapta)$

și prin redenumire , obținem $Q _ {{i}} (t_ {2}) = \ sum _ {{j = 1}} ^ {n} P _ {{i, j}} B_ {n} ^ {j} (t_ {2} )$

$P (t_ {1}, t_ {2}) = \ sum _ {{i = 1}} ^ {m} Q _ {{i}} (t_ {2}) B_ {m} ^ {i} (t_ {1})$

Observând că sunt punctele curbelor Bézier, ajunge principiul algoritmului. La fiecare iterație a algoritmului $Q _ {{i}} (t_ {2})$

calculați punctele și restricțiile curbelor Bézier pentru fiecare de către algoritmul Casteljau pe curbe $Q _ {{i}} (1/2)$ $eu$
calculați apoi afișați / stocați punctele curbei Bézier a punctelor de control de algoritmul Casteljau pe curbe $Q _ {{i}} (1/2)$
aplica recursiv algoritmul pe cele două suprafețe obținute prin gruparea restricțiilor pentru și $t_ {2} \ leqslant 1/2$ $t_ {2} \ geqslant 1/2$

Vezi și tu

Bibliografie

Claude Brezinski, Metode numerice de bază , Tehnici de inginerie ( citește online ) , p. 7
Jean-Louis Merrien, Analiză numerică cu MATLAB , Dunod , col. „Științe suplimentare / exerciții și probleme”,2007( citiți online ) , p. 89-90
Alain Yger și Jacques-Arthur Weil, Matematică aplicată L3: Curs complet cu 500 de teste și exerciții corectate , Pearson Education France,2009( citiți online ) , p. 115