Algorytm Cohena-Sutherlanda

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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[edytuj | edytuj kod]

Cohen sutherland kody.svg

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).


Algorytm Cohen sutherland.svg

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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]


Bibliografia[edytuj | edytuj kod]

  • 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.