algorytm.org Algorithms Geometria obliczeniowa Algorytm Cohena-Sutherlanda  
Home AlgorithmsData structuresAlgorithmics turorialPractiseDesign patternsIT Law SitemapPortal historyContributors ForumToolsWrite an articleSearch 

Algorytm Cohena-Sutherlanda
User Rating: / 3
PoorBest 
Written by Tomasz Lubiński   
Saturday, 12 December 2009 15:15
There are no translations available.

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 = y1 + (y2-y1) * (LEFT-x1) / (x2-x1)
    x = LEFT
  • jeżeli drugi bit jest ustawiony:
    y = y1 + (y2-y1) * (RIGHT-x1) / (x2-x1)
    x = RIGHT
  • jeżeli trzeci bit jest ustawiony:
    x = x1 + (x2-x1) * (BOTTOM-y1) / (y2-y1);
    y = BOTTOM
  • jeżeli czwarty bit jest ustawiony:
    x = x1 + (x2-x1) * (TOP-y1) / (y2-y1);
    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


.

Author Progam language Comment Download Rate
Tomasz Lubiński C# MS Visual Studio .net
Implementation in C#
/ 1
Tomasz Lubiński C/C++ Borland Builder 6
Implementation in C/C++
/ 0
Tomasz Lubiński Delphi/Pascal Borland Delphi 5
Implementation in Delphi/Pascal
/ 0
 
Add your implementation for this algorithm
  • Login first
File:
Progam language:
Comment:
  To be able to add your implementation, login first



Last Updated on Tuesday, 25 May 2010 22:37
 

Add comment







Danation
Donate us


RSS Channels
Articles
Implementations
Comments
Forum


Bookmarks








Poll
Czy znalazłeś na stronach www.algorytm.org to czego szukałeś?
 

www.algorytm.org (c) 2000-2010