Rozdział 2 – Wprowadzenie – 1/2 Krzywe Beziera

Wprowadzenie

Opis problemu

Zajmę się tutaj metodą rozwiązywania układu równań wielomianowych w 2 wymiarowej dziedzinie – trójkącie. Rozwiązywanie takich układów równań jest potrzebne m.in. gdy chcę znaleźć punkt przecięcia dwóch krzywych parametrycznych – należy wtedy odjąć odpowiadające sobie funkcje jednej krzywej od funkcji drugiej krzywej i poszukiwać punktu (0,0). Zakładam, że wierzchołki trójkąta w którym poszukuję rozwiązań mają współrzędne: (0,0),(0,1),(1,0). Nie zmniejsza to w niczym ogólności metody – inną dziedzinę należy przeskalować. Skalowanie dziedziny odbywa się poprzez podstawienie: zamiast $f(x,y)$ mamy $f(x’,y’) $,

gdzie: $x’ = a*x+b; y’ = c*x+d$

Rozwiązanie układu dwóch równań wielomianowych z dwiema niewiadomymi jest równoważne znalezieniu wszystkich wspólnych pierwiastków dwóch funkcji wielomianowych.

Dany jest układ $F(x)=F(x_1,x_2)=( f_1( x_1,x_2 ), f_2 (x_1,x_2 ) )=0=(0,0)$, gdzie funkcje $f_1,f_2$ są wielomianami stopnia n zmiennych $x_1,x_2$ z dziedziną będącą trójkątem T.

Zadaniem algorytmu jest znalezienie wszystkich pierwiastków leżących wewnątrz dziedziny.

Dokładniej: jeżeli mamy pewną funkcję $f_1$ z $R^2$ w $R$ ( przyjmijmy oznaczenia: funkcja z (x,y) w z ) – jeżeli przetniemy ją z płaszczyzną zerową (x=0) w typowym przypadku otrzymamy zbiór rozwiązań mocy continuum – funkcję uwikłaną zmiennych x i y . Dla drugiej funkcji $f_2$ otrzymamy drugą funkcję uwikłaną na płaszczyźnie (x,y). Przecięcie tych funkcji da kilka punktów, które stanowią rozwiązanie układu $f_1$ i $f_2$.

Funkcje $f_1,f_2$ są wielomianami, można przedstawić je w bazie Bernsteina, więc będzie można skorzystać z własności trójkątów Beziera .

Zajmę się metodą podpodziału . Jest to metoda globalna, znajdująca wszystkie pierwiastki układu w tej dziedzinie.

Krzywe Beziera

Wielomiany Bernsteina

Baza wielomianów Bernsteina ma postać:
$B^n_i(u) = \binom{n}{i}(1-u)^{n-i}u^i, u \in [0;1]$

Najważniejsze własności wielomianów Bernsteina to:

1) $\sum_{i=0}^n B_i^n(u) = 1$
własność ta wynika z tego, że $B_i^n(u)$ są to po prostu człony rozwiniętego dwumianu $[t+(1-t)]^n$

2) $B_i^n(u) \geqslant , u \in [0;1]$
– dowód natychmiastowy

3) $B_i^n(u) = (1-u)B_i^{n-1}(u) + u B_{i-1}^{n-1}(u)$

Krzywe Beziera

Przedstawienie krzywych w bazie wielomianów Bernsteina B zostało zaproponowane niezależnie przez P. Beziera i P. de Casteljau . Krzywe Beziera definiuje się jako kombinację liniową wielomianów Bernsteina:

$Q(t)= \sum_{i=0}^n P_i B_i^n(u), t \in [t_0;t_1]$

gdzie współczynniki $P_i$ są to punkty z $R^n$ . Zależnie od n (2 lub 3) definiuje się krzywą płaską lub przestrzenną. Punkty $P_i$ noszą nazwę punktów kontrolnych albo punktów Beziera, a łamana, której są wierzchołkami, jest nazywana łamaną Beziera .

Należy od razu wyjaśnić, że dla uniknięcia ograniczenia dziedziny funkcji stosujemy lokalną parametryzację:

$t=t_0+u(t_1-t_0),u \in [0;1]$

Często stosowanym przypadkiem jest n=3 – krzywa Beziera jest postaci:

$Q(u)=P_0(1-u)^3+P_1 3(1-u)^2u + P_2 3(1-u)u^2 + P_3 u^3$

Łatwo można sprawdzić, że :

$Q(0) = P_0$
$Q(1) = P_1$
$Q’(0) = 3(P_1-P_0)$
$Q’(1) = 3(P_3-P_2)$

Z dwóch pierwszych własności wielomianów Bernsteina wynika, że krzywa leży w powłoce wypukłej punktów kontrolnych $P_i$, i = 0,1,…,n. Trzecia, rekurencyjna zależność, prowadzi do wyznaczania punktów algorytmem de Casteljau który można wykorzystać przy dzieleniu krzywej na mniejsze fragmenty.

Algorytm de Casteljau

Oblicz wartość odpowiadającą lokalnej parametryzacji

u = $(t-t_0)/(t_1-t_0)$;

dla i = 0,1,…,n podstaw $P_{i,0}=P_i$;
dla j=1,2,…,n
dla i = j,j+1,…,n
$P_{i,j} = (1-u)P_{i-1,j-1}+uP{i,j-1}$;

Z obliczonych wielkości można utworzyć tablicę trójkątną:

$
\begin{matrix}
P_{0,0} \\
& P_{1,1} \\
P_{1,0} & & \cdot \\
\cdot & P_{2,1} & & \cdot \\
\cdot & \cdot & & \cdot & P_{n,n}\\
\cdot & \cdot & \cdot \\
P_{n-1,0} & \cdot \\
P_{n,0} & & & &
\end{matrix}
$

Jej pierwszą kolumnę tworzą dane punkty kontrolne P krzywej Beziera, a każda następna kolumna powstaje z punktów, które dzielą odcinek łączący sąsiednie punkty poprzedniej kolumny w stosunku u:1-u.

Dowodzi się [1], że $P_{n,n} = Q(t)$, a wyznaczone punkty $P_{0,0},P_{1,1},…,P_{n,n}$ są punktami kontrolnymi fragmentu krzywej od $P_0$ do Q(t); punkty zaś $P_{n,n},…,P_{n,1},P_{n,0}$ są punktami kontrolnymi pozostałej części krzywej tzn. od Q(t) do $P_n$ [11].

Algorytm de Casteljau pozwala zatem dzielić krzywą Beziera na mniejsze fragmenty [16] i traktować je osobno. Jest to istotne w przypadku modelowania krzywych, gdyż przesunięcie w wyjściowej łamanej choćby jednego punktu kontrolnego $P_i$ powoduje zmianę całej krzywej.

Jeśli chcemy wyznaczyć większą ilość punktów leżących na krzywej Beziera, to rozwiązaniem tańszym od przedstawionego wyżej algorytmu jest przejście od kombinacji liniowej wielomianów Bernsteina do postaci naturalnej wielomianu Q(t) i obliczanie jego wartości np. algorytmem Hornera .

Zmiana Baz

Niech w bazie wielomianowej $P_0(u)…P_n(u)$ ( gdzie u [0,1] ) krzywa Q(u) ma przedstawienie:

$Q(u) = P_0B_0(u)+…+P_nB_n(u)$ oraz baza $B_i(u)$ wyraża się w bazie potęgowej jako $Bi(u) = [b_{i,0},…,b_{i,n}].[1,u,u^2,…,u^n]^T$

wtedy

$Q(u)=
\begin{bmatrix}
P_0& … & P_n
\end{bmatrix}
\cdot
\begin{vmatrix}
b_{0,0}& … &b_{0,n} \\
…& … &… \\
b_{n,0}&… & b_{n,n}
\end{vmatrix}
\cdot
\begin{bmatrix}
1\\
..\\
u^n
\end{bmatrix}
= PBU$

Baza Bernsteina (dla stopnia wielomianu = 3)

$B_B = \begin{bmatrix}
1 & -3 & 3 & -1\\
0 & 3 & -6 & 3\\
0 & 0 & 3 & -3\\
0 & 0 & 0 & 1
\end{bmatrix}$

Jeśli wiele punków krzywej ma być obliczonych w ustalonym układzie współrzędnych, opłaca się przejść do bazy potęgowej to znaczy: wyznaczyć macierz współrzędnych punktów macierzy G, obliczyć raz macierz: $A = P \cdot B$

stosować schemat Hornera do równania $Q(u) = (PB)U = AU$

Jeżeli mamy podaną funkcję w bazie wielomianowej, aby przejść do bazy Bernsteina, należy stosować macierze odwrotne:

dla 2:
$\begin{bmatrix}
1 & 1 &1 \\
0 & 1/2 & 1\\
0 & 0 & 1
\end{bmatrix}$

dla 3:

$\begin{bmatrix}
1 & 1 & 1 & 1\\
0 & 1/3 & 2/3 & 1\\
0 & 0 & 1/3 & 1\\
0 & 0 & 0 & 1
\end{bmatrix}$

dla 4:
$\begin{bmatrix}
1& 1 & 1 & 1 & 1\\
0 & 1/4 & 1/2 & 3/4 & 1 \\
0 & 0 & 1/6 & 1/2 & 1\\
0 & 0 & 0 & 1/4 & 1\\
0 & 0 & 0 & 0 & 1
\end{bmatrix}$

Sposób tworzenia takich macierzy:

Trójkąt Pascala:

$\begin{matrix}
0: & & & & & & 1 \\
1: & & & & & 1 & & 1 \\
2: & & & & 1 & & 2 & & 1 \\
3: & & & 1 & & 3 & & 3 & & 1 \\
4: & & 1 & & 4 & & 6 & & 4 & & 1 \\
\end{matrix}$

Gdy mamy utworzyć macierz dla wielomianu stopnia N, wtedy wybieramy z trójkąta Pascala wiersz o numerze N; elementy leżące poniżej przekątnej wypełniamy zerami; począwszy od przekątnej trójkąt wypełniamy :

Dla macierzy przekształcenia zwykłego:
dla wiersza macierzy = r ,wypełniamy iloczynami liczb o numerze r z wybranego wiersza z trójkąta Pascal przez kolejne liczby z ciągu N-r+1 wiersza trójkąta Pascala; dodatkowo co drugą mnożymy przez (-1)

Dla macierzy przekształcenia odwrotnego:
ułamkami, które w liczniku mają kolejne liczby z N-tej przekątnej trójkąta, a w liczniku liczbę stałą dla każdego wiersza – dla kolejnych wierszy bierze się kolejne liczby z wybranego wiersza trójkąta Pascala.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *