Algorytm Lianga-Barsky’ego

Algorytm Lianga-Barsky'ego – algorytm obcinania odcinka do prostokątnego okna, 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 pracy . 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 okna. Na postawie tak uzyskanych danych można określić, którą część odcinka można narysować. Ten algorytm jest bardziej wydajny niż algorytm Cohena-Sutherlanda w przypadku gdy zachodzi konieczność przycięcia odcinka. 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 odcinka.

Opis

Argumenty przekazywane do algorytmu

1. Odcinek łączący punkty $(x_{1},y_{1})$ i $(x_{2},y_{2})$, przedstawiony parametrycznie równaniami:

${\begin{matrix}x(t)&=&x_{1}+t(x_{2}-x_{1})&=&x_{1}+t\,\Delta x\\y(t)&=&y_{1}+t(y_{2}-y_{1})&=&y_{1}+t\,\Delta y\\\end{matrix}}$

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ów:

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

Wynik działania algorytmu

Dwie wartości parametru $t_{1}\leqslant 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ści:

${\begin{matrix}x_{\text{min}}&\leqslant &x_{1}+t\,\Delta x&\leqslant &x_{\text{max}}\\y_{\text{min}}&\leqslant &y_{1}+t\,\Delta y&\leqslant &y_{\text{max}}\end{matrix}}$

co można wyrazić równoważnie jako cztery nierówności

$t\,p_{k}\leqslant q_{k},\quad 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}{lcllcl}p_{1}&=&-\Delta x,&\quad q_{1}&=&x_{1}-x_{\text{min}}\\p_{2}&=&\Delta x,&\quad q_{2}&=&x_{\text{max}}-x_{1}\\p_{3}&=&-\Delta y,&\quad q_{3}&=&y_{1}-y_{\text{min}}\\p_{4}&=&\Delta y,&\quad q_{4}&=&y_{\text{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$.
2. Jeśli dla pewnego $k$ zachodzi $q_{k}<0$, to odcinek znajduje się na zewnątrz okna i dalszych obliczeń nie trzeba prowadzić.
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 okna.
5. Dla danego odcinka wyznacza się $t_{1}$ i $t_{2}$ (parametry wyznaczające oba przycięte końce):

   ${\begin{array}{lcl}t_{1}&=&\max {\left\{0,\max \limits _{p_{k}<0}{\frac {q_{k}}{p_{k}}}\right\}}\\t_{2}&=&\min {\left\{1,\min \limits _{p_{k}>0}{\frac {q_{k}}{p_{k}}}\right\}}\end{array}}$

6. Jeśli $t_{1}>t_{2}$ to cały odcinek znajduje się poza oknem, 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ęcia.
• Wystarcza obliczenie nie więcej niż czterech parametrów $t$.
• Algorytm nie jest iteracyjny.
• Algorytm można uogólnić na przypadki trójwymiarowe.

Bibliografia

• Clipping, [w:] Max K.M.K. Agoston Max K.M.K., Computer graphics and geometric modeling. Implementation and algorithms, Springer London, 2005, s. 69-110, DOI: 10.1007/1-84628-108-3_3, ISBN 978-1-84628-108-2  (ang.).
• James D.J.D. Foley James D.J.D., Computer Graphics: Principles and Practice, Addison-Wesley Professional, 1996, ISBN 978-0-201-84840-3 [dostęp 2015-11-30]  (ang.).
• MichałM. Jankowski MichałM., Elementy grafiki komputerowej, Warszawa: Wydawnictwa Naukowo-Techniczne, 1990, ISBN 83-204-1326-5 .
• You-DongY.D. Liang You-DongY.D., B.A.B.A. Barsky B.A.B.A., A New Concept and Method for Line Clipping, „ACM Trans. Graph.”, 3 (1), 1984, s. 1–22, DOI: 10.1145/357332.357333, ISSN 0730-0301 [dostęp 2015-11-22] .1 stycznia
• CS355. Graphics and Multimedia. Clipping. [dostęp 2015-11-22]  (ang.).

Linki zewnętrzne

• Algorytm obcinania Lianga-Barsky\ego [online], Warsztat.GD [dostęp 2015-11-22] .
• Grafika komputerowa I – 3. Obcinanie linii i wielokątów – MIM UW [online], mst.mimuw.edu.pl [dostęp 2015-11-22] .
• Artykuł dot. Catmulla-Clarka
• Bimal KumarB.K. Ray Bimal KumarB.K., A Line Segment Clipping Algorithm in 2D, „International Journal of Computer Graphics”, 3 (2), listopad 2012 [dostęp 2015-11-30]  (ang.).brak strony (czasopismo)