Algorytm Cohena-Sutherlanda

Algorytm Cohena-Sutherlanda jest analitycznym algorytmem obcinania dwuwymiarowych odcinków przez prostokąt obcinający, którego boki są równoległe do osi układu współrzędnych. Algorytm ma zastosowanie w grafice komputerowej m.in. w okienkowaniu.

Algorytm

Prostokąt obcinający jest wyznaczony przez cztery proste równoległe do osi: $x_{\mathrm{min}}$, $x_{\mathrm{max}}$, $y_{\mathrm{min}}$, $y_{\mathrm{max}}$. Dzielą one płaszczyznę na 9 obszarów, którym przypisuje się 4-bitowe kody, każdy bit opisuje położenie punktu względem danej prostej. Przyporządkowanie bitów do prostych jest zupełnie umowne, tutaj opisano sytuację na rysunku:

• bit nr 0 ma wartość jeden, gdy $x < x_{\mathrm{min}}$ (punkt znajduje się po lewej prostokąta);
• bit nr 1 ma wartość jeden, gdy $x > x_{\mathrm{max}}$ (po prawej);
• bit nr 2 ma wartość jeden, gdy $y < y_{\mathrm{min}}$ (poniżej);
• bit nr 3 ma wartość jeden, gdy $y > y_{\mathrm{max}}$ (powyżej).

Kody są wykorzystywane do szybkiego akceptowania lub odrzucenia odcinków:

• Jeśli kody obu końców odcinka są równe 0 (suma logiczna (operacja OR) daje wynik 0000), wówczas jest on akceptowany ponieważ w całości znajduje się wewnątrz prostokąta (na rys. odcinek zielony).
• Jeśli wynikiem iloczynu logicznego (operacji AND) kodów odcinka jest liczba różna od zera (oba kody odcinków posiadają 1 na co najmniej jednym tym samym miejscu), oznacza to, że odcinek w całości znajduje się poza prostokątem (na rys. niebieskie odcinki).

(Na rys. czerwone odcinki znajdują się poza prostokątem. Suma logiczna daje wynik poprawny - różny od 0000. Jednak wynik iloczynu logicznego równa się 0000, dlatego odcinki nie zostają odrzucone (uznaje się jako nieokreślone). Po wykonaniu algorytmu dochodzimy do sytuacji, w której cały obcięty odcinek leży poza prostokątem obcinającym i algorytm kończy działanie odrzucając czerwone linie).

W pozostałych przypadkach potrzebne są dodatkowe obliczenia i algorytm przebiega następująco:

1. Wybierany jest koniec odcinka leżący poza prostokątem, a więc mający niezerowy kod; jeśli kody obu końców są niezerowe to można wybrać dowolny z nich.
2. Wyznaczany jest punkt przecięcia odcinka z jedną z prostych. Wybór prostych determinuje kod wybranego końca. Np. jeśli ustawiony jest bit nr 2, to znaczy, że należy znaleźć przecięcie z prostą $y = y_{\mathrm{min}}$. Jeśli w kodzie ustawionych jest więcej bitów, to można wybrać dowolną prostą - ważne jest jedyne, aby zawsze wybierać je w takiej samej kolejności (w przykładach przyjęto, że jest to: góra, dół, lewa, prawa).
3. Następnie odcinek jest przycinany do tego punktu - koniec wybrany w punkcie pierwszym jest zastępowany przez punkt przecięcia.
4. Kody końców odcinka są testowane tak jak opisano wyżej. Algorytm powtarza się dopóki jeden z dwóch testów nie będzie prawdziwy, tzn. aż odcinka nie będzie można w całości zaakceptować, albo odrzucić.

Liczba iteracji potrzebnych do obcięcia odcinka może wynosić od 0 do 4.

Przykład

Obcinanie odcinka AB:

1. wybierany jest punkt B (1);
2. wyznaczane jest przecięcie z prostą $y=y_{\mathrm{max}}$ - punkt C (2);
3. nowy odcinek ma końce AC i znajduje się w całości w prostokącie - w tym miejscu algorytm kończy się (3).

Obcinanie odcinka DE:

1. wybierany jest punkt D (1);
2. wyznaczane jest przecięcie z prostą $y=y_{\mathrm{max}}$ - punkt F (2);
3. nowy odcinek ma końce EF, algorytm jest kontynuowany (3);
4. wybierany jest punkt E (1);
5. wyznaczane jest przecięcie z prostą $y=y_{\mathrm{min}}$ - punkt G (2);
6. nowy odcinek ma końce FG, algorytm jest kontynuowany (3);
7. wybierany jest punkt F (1);
8. wyznaczane jest przecięcie z prostą $x=x_{\mathrm{max}}$ - punkt H (2);
9. nowy odcinek ma końce GH i znajduje się w całości w prostokącie - w tym miejscu algorytm kończy się (3).

Zobacz też

• okienkowanie

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.