Algorytm Cohena-Sutherlanda

Algorytm Cohena-Sutherlanda – analityczny algorytm 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_{\min },$ $x_{\max },$ $y_{\min },$ $y_{\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_{\min }$ (punkt znajduje się po lewej prostokąta);
• bit nr 1 ma wartość jeden, gdy $x>x_{\max }$ (po prawej);
• bit nr 2 ma wartość jeden, gdy $y<y_{\min }$ (poniżej);
• bit nr 3 ma wartość jeden, gdy $y>y_{\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_{\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órna, dolna, 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 jest to opisane 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_{\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_{\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_{\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_{\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ż

• algorytm Lianga-Barsky’ego
• 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.