algorytm.org

Algorytm Cohena-Sutherlanda

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Algorytm Cohena-Sutherlanda
Ocena użytkowników:***** / 7
SłabyŚwietny 
Wpisany przez Tomasz Lubiński, 12 grudnia 2009 15:15

Załóżmy, że mamy dany pewien zbiór odcinków oraz okno, które definiuje nam obszar widziany przez użytkownika. W zależności od wielkości okna oraz jego położenia część odcinków znajdzie się w oknie - powinna zostać pokazana, a część znajdzie się poza oknem - nie powinna być brana pod uwagę. Takie zadanie sprawnie można rozwiązać za pomocą algorytmu Cohena-Sutherlanda.

Końce odcinków zakodujemy zgodnie z rysunkiem poniżej:

Algorytm Cohena-Sutherlanda - kody regionów


Jeżeli koniec odcinka znajduje się poza oknem:
  • z lewej strony - ustaw bit pierwszy,
  • z prawej strony - ustaw bit drugi,
  • z dołu - ustaw bit trzeci,
  • z góry - ustaw bit czwarty.

Jak wynika z rysunku każdy koniec może mieć włączone:
  • 0 bitów - znajduje się w oknie,
  • 1 bit - znajduje się z boku albo nad albo pod oknem,
  • 2 bity - znajduje się z poza oknem pod ukosem.

Algorytm Cohena-Sutherlanda działa w następujących krokach.
  1. Zakoduj odcinki zgodnie ze wzorem powyżej.
  2. Jeżeli suma logiczna (or) obydwóch kodów końców odcinka jest równa zero, wówczas cały odcinek mieści się w oknie.
  3. Jeżeli iloczyn logiczny (and) obydwóch kodów końców odcinka jest różny od zero, wówczas z pewnością cały odcinek mieści się poza oknem.
  4. W pozostałych przypadkach należy obliczyć punkty przecięcia odcinka z krawędziami okna.

Na rysunku poniżej przedstawiono proste przypadki wykryte przez algorytm - punkt 2 (odcinki zielone) oraz punkt 3 (odcinki czerwone).

Algorytm Cohena-Sutherlanda - przypadki proste


W przypadkach złożonych - punkt 4 postępujemy następująco: wybieramy dowolny koniec o niezerowym kodzie (czyli znajdujący się poza oknem) i na podstawie jego współrzędnych oraz kodu obliczamy punkt przecięcia z osią okna. Jeżeli przyjmiemy, że lewa krawędź okna ma współrzędną x równą LEFT, prawa strona natomiast ma współrzędną x równą RIGHT, oraz analogicznie górna krawędź ma współrzędną y równą TOP, a dolna ma współrzędną y równą BOTTOM, to punkt przecięcia (x, y) dla odcinka o współrzędnych (x1, y1), (x2, y2) obliczymy z następujących wzorów:

  • jeżeli pierwszy bit jest ustawiony:
    y = y_1 + (y_2-y_1) * \frac{LEFT-x_1}{x_2-x_1}\\ x = LEFT
  • jeżeli drugi bit jest ustawiony:
    y = y_1 + (y_2-y_1) * \frac{RIGHT-x_1}{x_2-x_1}\\ x = RIGHT
  • jeżeli trzeci bit jest ustawiony:
    x = x_1 + (x_2-x_1) * \frac{BOTTOM-y_1}{y_2-y_1}\\ y = BOTTOM
  • jeżeli czwarty bit jest ustawiony:
    x = x_1 + (x_2-x_1) * \frac{TOP-y_1}{y_2-y_1}\\ y = TOP

W jednym kroku obcinamy odcinek tylko względem jednej krawędzi okna. Po obliczeniu punktu przecięcia odrzucamy część poza oknem, obliczamy nowy kod końca i sprawdzamy, który z przypadków teraz spełnia odcinek. Jeżeli jest to warunek opisany w punkcie drugim, to odrzuciliśmy część będącą poza oknem i została nam już część w całości do pokazania w oknie (odcinki: żółto-niebiesko-żółty, oraz żółto-niebieski na schemacie poniżej), jeżeli jest to warunek opisany w punkcie trzecim to całą resztę również należy odrzucić bo znajduje się poza oknem (odcinek żółty na schemacie poniżej), jeżeli natomiast cały czas odcinek spełnia warunek opisany w punkcie czwartym to musimy dokonać kolejnego cięcia - wykonujemy je tak długo aż nowo powstały odcinek nie spełni warunku z punktu drugiego bądź trzeciego.

Algorytm Cohena-Sutherlanda - przypadki złożone

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Tomasz LubińskiC#MS Visual Studio .net
.cs
.cs
***** / 2
Andrzej BoruckiC#MS Visual C# Express 2010
.cs
.cs
***** / 0
Tomasz LubińskiC/C++Borland Builder 6
.cpp
.cpp
***** / 1
Tomasz LubińskiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 28 sierpnia 2012 20:14
Dodaj komentarz