Algorytm Cohena-Sutherlanda

Algorytm Cohena-Sutherlanda

Algorytm Cohena-Sutherlanda to metoda obcinania dwuwymiarowych odcinków przez prostokąt obcinający, której boki są równoległe do osi układu współrzędnych. Znajduje zastosowanie głównie w grafice komputerowej, na przykład w okienkowaniu.

Opis Algorytmu

Prostokąt obcinający jest zdefiniowany przez cztery linie: $x\_\backslash min,\; x\_\backslash max,\; y\_\backslash min,\; y\_\backslash max$, co dzieli płaszczyznę na dziewięć obszarów. Każdemu z nich przypisano 4-bitowe kody, które określają położenie punktu względem prostokąta:

• Bit 0: (punkt po lewej)
• Bit 1: $x\; >\; x\_\backslash max$ (punkt po prawej)
• Bit 2: (punkt poniżej)
• Bit 3: $y\; >\; y\_\backslash max$ (punkt powyżej)

Kody te służą do szybkiej oceny, czy odcinek jest wewnątrz lub na zewnątrz prostokąta:

• Jeśli kody obu końców odcinka wynoszą 0 (0000), odcinek jest akceptowany.
• Jeśli wynik iloczynu kodów jest różny od 0, odcinek jest odrzucany.

W przeciwnym razie algorytm wymaga dalszych obliczeń:

1. Wybierz koniec odcinka leżący poza prostokątem.
2. Oblicz punkt przecięcia odcinka z jedną z prostych, zależnie od kodu wybranego końca.
3. Przytnij odcinek do tego punktu.
4. Powtórz proces, aż odcinek zostanie zaakceptowany lub odrzucony.

Algorytm może wymagać od 0 do 4 iteracji do obcięcia odcinka.

Przykłady Obcinania

Obcinanie odcinka AB:

1. Wybierz punkt B (1).
2. Oblicz przecięcie z prostą $y=y\_\backslash max$ – punkt C (2).
3. Nowy odcinek AC znajduje się w całości w prostokącie, algorytm kończy się (3).

Obcinanie odcinka DE:

1. Wybierz punkt D (1).
2. Oblicz przecięcie z prostą $y=y\_\backslash max$ – punkt F (2).
3. Nowy odcinek EF, kontynuuj algorytm (3).
4. Wybierz punkt E (1).
5. Oblicz przecięcie z prostą $y=y\_\backslash min$ – punkt G (2).
6. Nowy odcinek FG, kontynuuj (3).
7. Wybierz punkt F (1).
8. Oblicz przecięcie z prostą $x=x\_\backslash max$ – punkt H (2).
9. Nowy odcinek GH znajduje się w całości w prostokącie, algorytm kończy się (3).