Algorytm Cohena-Sutherlanda

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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]

Cohen sutherland kody.svg

Prostokąt obcinający jest wyznaczony przez cztery proste równoległe do osi: , , , . 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 (punkt znajduje się po lewej prostokąta);
  • bit nr 1 ma wartość jeden, gdy (po prawej);
  • bit nr 2 ma wartość jeden, gdy (poniżej);
  • bit nr 3 ma wartość jeden, gdy (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ą . 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]

Obcinanie odcinka AB:

  1. wybierany jest punkt B (1);
  2. wyznaczane jest przecięcie z prostą - 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ą - 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ą - 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ą - 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]


Bibliografia[edytuj]

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