Algorytm Lianga-Barsky’ego

Szablon:Spis treści Algorytm Lianga-Barsky’ego – algorytm obcinania odcinka do prostokątnego oknaSzablon:Odn, stosowany w grafice komputerowej. Nazwa algorytmu pochodzi od nazwisk autorów You-Dong Lianga i Briana A. Barsky’ego, którzy zaproponowali go w swojej pracySzablon:Odn. Algorytm wykorzystuje parametryczne równanie odcinka oraz nierówności opisujące prostokątne okno do określenia wartości współczynnika parametrycznego, dla których odcinek przecina się z bokami oknaSzablon:Odn. Na podstawie tak uzyskanych danych można określić, którą część odcinka można narysować. Ten algorytm jest bardziej wydajny niż algorytm Cohena-SutherlandaSzablon:Odn w przypadku gdy zachodzi konieczność przycięcia odcinkaSzablon:Odn. Pomysłem w algorytmie Lianga-Barsky’ego jest wykonywanie tylu porównań, na ile jest to możliwe przed właściwym obliczaniem końców przyciętego odcinkaSzablon:Odn.

Opis

Argumenty przekazywane do algorytmu

1. Odcinek łączący punkty $(x_1,y_1)$ i $(x_2,y_2),$ przedstawiony parametrycznie równaniamiSzablon:Odn:

$\begin{array}{ccccc}x(t)& =& x_1+t(x_2-x_1)& =& x_1+t\mathrm{\Delta }x\\ y(t)& =& y_1+t(y_2-y_1)& =& y_1+t\mathrm{\Delta }y\end{array}$

dla $t\in [0,1].$ Zmiana parametru od $0$ do $1$ opisuje też kierunek rysowania odcinka, do którego odnosi się działanie algorytmu.

2. Prostokątne okno o krawędziach równoległych do osi układu współrzędnych, zadane przez współrzędne swoich narożnikówSzablon:Odn:

$x_{\min },$ $x_{\max },$ $y_{\min },$ $y_{\max }.$

Wynik działania algorytmu

Dwie wartości parametru $t_1⩽t_2$ takie, że $(x(t_1),y(t_1))$ i $(x(t_2),y(t_2))$ są współrzędnymi punktów przecięcia odcinka z krawędziami okna, bądź informacja, że takie punkty nie istnieją.

W tej pierwszej sytuacji wejściowe równania parametryczne dla $t\in [t_1,t_2]$ opisują odcinek, który jest wynikiem przycięcia odcinka wejściowego do obszaru okna, w tej drugiej odcinek leży w całości na zewnątrz okna.

Działanie algorytmu

Punkt $(x(t),y(t))$ znajduje się wewnątrz okna będącego argumentem algorytmu dokładnie wtedy, gdy spełnione są nierównościSzablon:Odn:

$\begin{array}{ccccc}{x}_{\min }& ⩽& x_1+t\mathrm{\Delta }x& ⩽& x_{\max }\\ y_{\min }& ⩽& y_1+t\mathrm{\Delta }y& ⩽& y_{\max }\end{array}$

co można wyrazić równoważnie jako cztery nierównościSzablon:Odn

$t{p}_k⩽q_k,k=1,2,3,4,$

odpowiadające poszczególnym krawędziom okna w kolejności: lewa, prawa, dolna, górna. Wartości parametrów są następujące:

$\begin{array}{cccccc}{p}_1& =& -\mathrm{\Delta }x,& q_1& =& x_1-x_{\min }\\ p_2& =& \mathrm{\Delta }x,& q_2& =& x_{\max }-x_1\\ p_3& =& -\mathrm{\Delta }y,& q_3& =& y_1-y_{\min }\\ p_4& =& \mathrm{\Delta }y,& q_4& =& y_{\max }-y_1\end{array}$

Ostateczne wyznaczenie odcinka:

1. Odcinek pionowy spełnia $p_1=p_2=0,$ a poziomy $p_3=p_4=0$Szablon:Odn.
2. Jeśli dla pewnego $k$ zachodzi $q_k<0,$ to odcinek znajduje się na zewnątrz okna i dalszych obliczeń nie trzeba prowadzićSzablon:Odn.
3. Jeśli $p_k<0$ to odcinek przecina bok z zewnątrz do wewnątrz, natomiast dla $p_k>0,$ odcinek przebiega z wewnątrz na zewnątrz.
4. Dla niezerowego $p_k,$ wartość parametru $t=\frac{q_k}{p_k}$ określa punkt przecięcia z bokiem oknaSzablon:Odn.
5. Dla danego odcinka wyznacza się $t_1$ i $t_2$ (parametry wyznaczające oba przycięte końce)Szablon:Odn:

   $\begin{array}{ccc}{t}_1& =& \max \{0,\max {\mathrm{\backslash limits}}_{p_k<0}\frac{q_k}{p_k}\},\\ t_2& =& \min \{1,\min {\mathrm{\backslash limits}}_{p_k>0}\frac{q_k}{p_k}\}.\end{array}$

6. Jeśli $t_1>t_2$ to cały odcinek znajduje się poza oknemSzablon:Odn, w przeciwnym razie obliczone wartości stanowią wynik działania algorytmu.

Własności

• Współrzędne są obliczane tylko dla dwóch punktów przecięciaSzablon:Odn.
• Wystarcza obliczenie nie więcej niż czterech parametrów $t$Szablon:Odn.
• Algorytm nie jest iteracyjnySzablon:Odn.
• Algorytm można uogólnić na przypadki trójwymiaroweSzablon:Odn.

Bibliografia

• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj

Linki zewnętrzne

• Szablon:Cytuj
• Szablon:Cytuj
• Artykuł dot. Catmulla-Clarka
• Szablon:Cytuj