Przejdź do zawartości

Algorytm Lianga-Barsky’ego

Z Wikipedii, wolnej encyklopedii

Algorytm Lianga-Barsky’ego – algorytm obcinania odcinka do prostokątnego okna[1], 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[2]. 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[3]. 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[4] w przypadku gdy zachodzi konieczność przycięcia odcinka[5]. 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[5].

Argumenty przekazywane do algorytmu

[edytuj | edytuj kod]

1. Odcinek łączący punkty i przedstawiony parametrycznie równaniami[3]:

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[6]:

Wynik działania algorytmu

[edytuj | edytuj kod]

Dwie wartości parametru takie, że i są współrzędnymi punktów przecięcia odcinka z krawędziami okna[a], 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

[edytuj | edytuj kod]

Punkt znajduje się wewnątrz okna będącego argumentem algorytmu dokładnie wtedy, gdy spełnione są nierówności[3]:

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

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:

  1. Odcinek pionowy spełnia a poziomy [3].
  2. Jeśli dla pewnego zachodzi to odcinek znajduje się na zewnątrz okna i dalszych obliczeń nie trzeba prowadzić[3].
  3. Jeśli to odcinek przecina bok z zewnątrz do wewnątrz, natomiast dla odcinek przebiega z wewnątrz na zewnątrz.
  4. Dla niezerowego wartość parametru określa punkt przecięcia z bokiem okna[3].
  5. Dla danego odcinka wyznacza się i (parametry wyznaczające oba przycięte końce)[3]:
  6. Jeśli to cały odcinek znajduje się poza oknem[1], w przeciwnym razie obliczone wartości stanowią wynik działania algorytmu.

Własności

[edytuj | edytuj kod]
  • Współrzędne są obliczane tylko dla dwóch punktów przecięcia[7].
  • Wystarcza obliczenie nie więcej niż czterech parametrów [7].
  • Algorytm nie jest iteracyjny[7].
  • Algorytm można uogólnić na przypadki trójwymiarowe[b][7].
  1. W brzegowym przypadku wynikiem przycięcia odcinka do okna jest jeden punkt.
  2. Ograniczeniem jest prostopadłościan wraz z dodatkową nierównością dla trzeciego wymiaru[8]:

Przypisy

[edytuj | edytuj kod]
  1. a b Jankowski 1990 ↓, s. 59.
  2. Liang i Barsky 1984 ↓.
  3. a b c d e f g h Jankowski 1990 ↓, s. 58.
  4. Agoston 2005 ↓, s. 80.
  5. a b Foley 1996 ↓, s. 123.
  6. Jankowski 1990 ↓, s. 53–54, 59.
  7. a b c d Clipping, s. 20.
  8. Jankowski 1990 ↓, s. 104–105.

Bibliografia

[edytuj | edytuj kod]

Linki zewnętrzne

[edytuj | edytuj kod]