Algorytm Cohena-Sutherlanda
Algorytm Cohena-Sutherlanda to analityczny algorytm służący do obcinania dwuwymiarowych odcinków w obrębie prostokąta, którego boki są równoległe do osi układu współrzędnych. Ma on zastosowanie w grafice komputerowej, szczególnie w kontekście okienkowania.
Algorytm
Prostokąt obcinający jest definiowany przez cztery proste równoległe do osi:
x min, x max, y min, y max.
Te proste dzielą płaszczyznę na dziewięć obszarów, którym przypisywane są 4-bitowe kody. Każdy bit kodu określa położenie punktu względem danej prostej. Przyporządkowanie bitów do prostych jest umowne, co ilustruje poniższa tabelka:
- Bit nr 0 ma wartość 1, gdy x < x min (punkt znajduje się po lewej stronie prostokąta);
- Bit nr 1 ma wartość 1, gdy x > x max (po prawej);
- Bit nr 2 ma wartość 1, gdy y < y min (poniżej);
- Bit nr 3 ma wartość 1, gdy y > y max (powyżej).
Kody te służą do szybkiej oceny, czy odcinek może być zaakceptowany lub odrzucony:
Jeżeli kody obu końców odcinka są równe 0 (suma logiczna (operacja OR) daje wynik 0000), wówczas odcinek jest akceptowany, ponieważ w całości znajduje się wewnątrz prostokąta (jak pokazano na rysunku z zielonym odcinkiem).
Jeżeli wynik iloczynu logicznego (operacja AND) kodów odcinka wynosi więcej niż 0 (oba kody mają bit 1 na co najmniej jednym tym samym miejscu), oznacza to, że odcinek w całości leży poza prostokątem (jak na rysunku z niebieskimi odcinkami).
(Na rysunku czerwone odcinki są poza prostokątem. Suma logiczna daje wynik różny od 0000, ale wynik iloczynu logicznego wynosi 0000, dlatego odcinki te nie są odrzucane (są traktowane jako nieokreślone). Po wykonaniu algorytmu może się okazać, że cały obcięty odcinek leży poza prostokątem, co kończy działanie algorytmu, odrzucając czerwone linie).
W pozostałych przypadkach wymagane są dodatkowe obliczenia, a algorytm działa w następujący sposób:
Wybierany jest koniec odcinka, który znajduje się poza prostokątem i ma niezerowy kod; w przypadku, gdy oba kody końców są niezerowe, można wybrać dowolny z nich.
Wyznaczany jest punkt przecięcia odcinka z jedną z prostych, a wybór prostych zależy od kodu wybranego końca. Na przykład, jeśli ustawiony jest bit nr 2, należy znaleźć przecięcie z prostą y = y min.
Jeśli w kodzie ustawionych jest więcej bitów, można wybrać dowolną prostą; ważne jest, aby zawsze wybierać je w tej samej kolejności (w przykładach przyjęto kolejność: górna, dolna, lewa, prawa).
Następnie odcinek jest przycinany do tego punktu – koniec wybrany w pierwszym kroku jest zastępowany przez punkt przecięcia.
Kody końców odcinka są testowane tak, jak opisano wcześniej. Algorytm powtarza się, aż jeden z dwóch testów zostanie spełniony, tj. aż odcinek nie będzie można całkowicie zaakceptować lub odrzucić.
Liczba iteracji potrzebnych do obcięcia odcinka może wynosić od 0 do 4.
Przykład
Obcinanie odcinka AB:
wybierany jest punkt B (1),
wyznaczane jest przecięcie z prostą y = y max – punkt C (2),
nowy odcinek ma końce AC i znajduje się w całości w prostokącie – w tym momencie algorytm kończy działanie (3).
Obcinanie odcinka DE:
wybierany jest punkt D (1),
wyznaczane jest przecięcie z prostą y = y max – punkt F (2),
nowy odcinek ma końce EF, algorytm jest kontynuowany (3),
wybierany jest punkt E (1),
wyznaczane jest przecięcie z prostą y = y min – punkt G (2),
nowy odcinek ma końce FG, algorytm jest kontynuowany (3),
wybierany jest punkt F (1),
wyznaczane jest przecięcie z prostą x = x max – punkt H (2),
nowy odcinek ma końce GH i znajduje się w całości w prostokącie – w tym momencie algorytm kończy działanie (3).
Zobacz też
Bibliografia
Algorytmy Cohena-Sutherlanda obcinania odcinków. W: James D Foley, Andries van Dam, Steven K Freiner, John F Hughes, Richard L Phillips: Wprowadzenie do grafiki komputerowej. Jan Zabrodzki (tłumaczenie). Warszawa: Wydawnictwa Naukowo-Techniczne, 1995, s. 147–152. ISBN 83-204-1840-2.
