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 podstawie 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 i przedstawiony parametrycznie równaniami:
dla Zmiana parametru od do 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:
Wynik działania algorytmu Dwie wartości parametru takie, że i są współrzędnymi punktów przecięcia odcinka z krawędziami oknaW brzegowym przypadku wynikiem przycięcia odcinka do okna jest jeden punkt., bądź informacja, że takie punkty nie istnieją.
W tej pierwszej sytuacji wejściowe równania parametryczne dla 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 znajduje się wewnątrz okna będącego argumentem algorytmu dokładnie wtedy, gdy spełnione są nierówności:
co można wyrazić równoważnie jako cztery nierówności
odpowiadające poszczególnym krawędziom okna w kolejności: lewa, prawa, dolna, górna. Wartości parametrów są następujące:
Ostateczne wyznaczenie odcinka: Odcinek pionowy spełnia a poziomy . Jeśli dla pewnego zachodzi to odcinek znajduje się na zewnątrz okna i dalszych obliczeń nie trzeba prowadzić. Jeśli to odcinek przecina bok z zewnątrz do wewnątrz, natomiast dla odcinek przebiega z wewnątrz na zewnątrz. Dla niezerowego wartość parametru określa punkt przecięcia z bokiem okna. Dla danego odcinka wyznacza się i (parametry wyznaczające oba przycięte końce):
Jeśli 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 . Algorytm nie jest iteracyjny. Algorytm można uogólnić na przypadki trójwymiarowe.
Uwagi
Przypisy
Bibliografia
Linki zewnętrzne
Artykuł dot. Catmulla-Clarka
Lianga-Barsky’ego