Algorytm Cohena-Sutherlanda - Google

Algorytm Cohena-Sutherlanda

Z Wikipedii

Skocz do: nawigacji, 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.

[edytuj] Algorytm

Prostokąt obcinający jest wyznaczony przez cztery proste równoległe do osi: xmin, xmax, ymin, ymax.

Te proste dzielą 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 < xmin (punkt znajduje siÄ™ po lewej prostokÄ…ta);
  • bit nr 1 ma wartość jeden, gdy x > xmax (po prawej);
  • bit nr 2 ma wartość jeden, gdy y < ymin (poniżej);
  • bit nr 3 ma wartość jeden, gdy y > ymax (powyżej).


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 = ymin. 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.

[edytuj] Przykład

Obcinanie odcinka AB:

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

[edytuj] Przykładowy program

Przykładowy program napisany w języku Python, który losuje odcinek i obcina go algorytmem Cohena-Sutherlanda, a następnie zapisuje do pliku obrazek przedstawiający proste, prostokąt obcinający oraz odcinek wyjściowy i odcinek obcięty.

# -*- coding: iso-8859-2 -*-
 
def Cohen_Sutherland(xa,ya, xb,yb, x_min,x_max,y_min,y_max):
        '''
        Funkcja obcina odcinek algorytmem Cohena-Sutherlanda
 
        xa,ya, xb,yb - współrzędne końców odcinka
        x_min, x_max, y_min, y_max - granice prostokÄ…ta
        '''
 
        def code(x,y):
                '''
                Funkcja wyznacza kod 4-bitowy dla podanego punktu
                '''
                b0 = int(y > y_max)
                b1 = int(y < y_min) << 1
                b2 = int(x > x_max) << 2
                b3 = int(x < x_min) << 3
                return b0 | b1 | b2 | b3
 
        def top(code):    return (code & 0x01) != 0
        def bottom(code): return (code & 0x02) != 0
        def left(code):   return (code & 0x04) != 0
        def right(code):  return (code & 0x08) != 0
 
        code_a = code(xa,ya)
        code_b = code(xb,yb)
        while True:
                # 1. Sprawdzenie, czy odcinek w całości znajduje się w
                #    prostokącie obcinającym - jeśli tak, zwracane są jego współrzędne.
                if code_a == 0 and code_b == 0:
                        return ((xa,ya), (xb,yb))
 
                # 2. Sprawdzenie, czy odcinek w całości znajduje się poza
                #    prostokątem obcinającym - jeśli tak jest funkcja kończy się.
                if (code_a & code_b) != 0:
                        return None
 
                # 3. Wybranie punktu (a właściwie kodu punktu), który
                #    znajduje siÄ™ poza prostokÄ…tem
                if code_a != 0:
                        code_o = code_a
                else:
                        code_o = code_b
 
                # 5. Obcianie:
                # 5a. przez prostÄ… y=y_max
                if top(code_o):
                        t = (y_max-ya)/float(yb-ya)
                        x = xa + t*(xb-xa)
                        y = y_max
                # 5b. przez prostÄ… y=y_min
                elif bottom(code_o):
                        t = (y_min-ya)/float(yb-ya)
                        x = xa + t*(xb-xa)
                        y = y_min
                # 5c. przez prostÄ… x=x_max
                elif left(code_o):
                        x = x_max
                        t = (x_max-xa)/float(xb-xa)
                        y = ya + t*(yb-ya)
                # 5d. przez prostÄ… x=x_min
                elif right(code_o):
                        x = x_min
                        t = (x_min-xa)/float(xb-xa)
                        y = ya + t*(yb-ya)
 
                # 6. Odrzucenie punktu, który znajduje się poza prostokątem
                #    (tego, który w 3. kroku został wybrany) i zastąpienie
                #    go punktem przecięcia.
                if code_o == code_a:
                        xa = x
                        ya = y
                        code_a = code(x,y)
                else:
                        xb = x
                        yb = y
                        code_b = code(x,y)
 
if __name__ == '__main__':
        import Image
        import ImageDraw
        from random import randint
 
        rozdzielczosc = r = 500 # rozdzielczość obrazka
        image = Image.new("RGB", (rozdzielczosc, rozdzielczosc))
        draw  = ImageDraw.Draw(image)
 
        # Granice prostokÄ…ta obcinajÄ…cego
        y_min = 130
        y_max = 370
        x_min = 50
        x_max = 450
 
        # Współrzędne odcinka (losowe)
        xa = randint(0,rozdzielczosc)
        ya = randint(0,rozdzielczosc)
        xb = randint(0,rozdzielczosc)
        yb = randint(0,rozdzielczosc)
 
        # Obcięcie alg. Cohena-Sutherlanda - zmienna 'obciety_odcinek' zawiera albo
        # współrzędne obciętego odcinka, albo None, gdy odcinek znajdował się
        # poza prostokÄ…tem obcinajÄ…cym
        obciety_odcinek = Cohen_Sutherland(xa,ya, xb,yb, x_min,x_max, y_min,y_max)
 
        # Rysowanie:
        draw.rectangle([0,0,r,r], fill="#fff")
        # * prostych y=y_min, y=y_max, x=x_min, x=x_max
        draw.line([0,y_min, r,y_min], fill="#aaa")
        draw.line([0,y_max, r,y_max], fill="#aaa")
        draw.line([x_min,0, x_min,r], fill="#aaa")
        draw.line([x_max,0, x_max,r], fill="#aaa")
 
        # * prostokÄ…ta obcinajÄ…cego wyznaczonego przez te proste
        draw.rectangle([x_min,y_min,x_max,y_max], outline="#000")
 
        # * obcinanego odcinka
        draw.line([xa,ya,xb,yb], fill="#0f0")
 
        # * jeśli istnieje, obciętego odcinka
        if obciety_odcinek:
                draw.line(obciety_odcinek, fill="#f00", width=2)
 
        # Zapisanie obrazka
        image.save('Cohen_Sutherland.png', 'PNG')

Sondaż: Drzewiecki przetrwa wojnę
"Rzeczpospolita": Ponad połowa (53 procent) Polaków jest zadowolona, że doszło do porozumienia rządu z FIFA i nie grozi nam już odebranie Euro 2012. Prawie połowa Polaków (49 procent) uważa jednak wycofanie kuratora z PZPN za porażkę rządu Donalda Tuska - wynika z sondażu "Rzeczpospolitej".
TVP Info: Tusk nie wiedział o powołaniu kuratora w PZPN
Minister sportu Mirosław Drzewiecki nie miał zgody premiera na wniosek do Trybunału Arbitrażowego o wprowadzenie kuratora do PZPN - dowiedział się nieoficjalnie serwis internetowy tvp.info.
MON ukarze dowódcę, bo zaprosił prezydenta?
"Rzeczpospolita": Dowódca pułku komandosów w Lublińcu pułkownik Dariusz Dachowicz może stracić stanowisko. Według dziennika, kierownictwu MON nie spodobał się pomysł zaproszenia na święto jednostki prezydenta Lecha Kaczyńskiego.
Szansa na przełom w Moskwie ws. Katynia
"Dziennik Polski": Rosyjscy prawnicy sądzą, że już 24 października może zapaść w Rosji decyzja o rehabilitacji polskich ofiar NKWD, zamordowanych w Katyniu.
"Andrzeju, nie będziesz uniewinniony"
- Ten werdykt to wstyd dla sądu w Szamotułach, a nie dla mnie - powiedziała w TVN 24 Renata Beger. Była posłanka Samoobrony została skazana przez sąd za fałszowanie podpisów na listach wyborczych.
Linki: Strona g³ówna