Wikiszótár

Cohen-Sutherland-algoritmus

Magyar

Kiejtés

  • IPA: [ ˈt͡soɦɛnʃuthɛrlɒndɒlɡoritmuʃ]

Főnév

Cohen-Sutherland-algoritmus

  1. (matematika)

Cohen-Sutherland-algoritmus

A Cohen-Sutherland-algoritmus egy hatékony és széles körben használt vágóalgoritmus (clipping algorithm) a 2D vonalszakaszok téglalap alakú ablakhoz való vágására. Az algoritmus segítségével meghatározhatjuk, hogy egy vonalszakasz mely részei maradnak láthatók a vágási ablakon belül.


Alapfogalmak

  1. Vágási ablak:

    • A képernyő vagy a koordinátatér egy téglalap alakú része, amelyen belül szeretnénk látni a vonalszakaszokat.
    • Definiálható a bal alsó és jobb felső sarka által: ( (x_{}, y_{}) ) és ( (x_{}, y_{}) ).

  2. Vonalak osztályozása:

    • Teljesen belül: A vonal a vágási ablakon belül található.
    • Teljesen kívül: A vonal nem metszi a vágási ablakot.
    • Részben belül: A vonal metszi a vágási ablak szélét.

  3. Regionális kódok (outcode-ok):

    • A vágási ablak körüli tér 9 régióra oszlik, és minden pont egy 4 bites kóddal (outcode) kerül leírásra:
      • Bitpozíciók (fentről lefelé): TOP, BOTTOM, RIGHT, LEFT.

    Az alábbi ábrában látható a kódok kiosztása:

         1010 | 1000 | 1001
     ------------------
     0010 | 0000 | 0001
     ------------------
     0110 | 0100 | 0101
    • A középső ( 0000 ) kód jelzi a téglalap belsejét.
    • Példa:
      • ( 1000 ): A pont a felső régióban van.
      • ( 0101 ): A pont a bal alsó régióban van.


Működési elv

  1. Regionális kódok kiszámítása:
    • A vonalszakasz két végpontjára kiszámoljuk a regionális kódokat (outcode-ok).
  2. Gyors ellenőrzések:
    • Elfogadás: Ha mindkét végpont regionális kódja ( 0000 ) (teljesen belül).
    • Elutasítás: Ha a két végpont regionális kódjának bitenkénti ÉS művelete nem egyenlő nullával (teljesen kívül).
    • Részleges vágás: Ha a vonalszakasz egy része belül van, a másik része pedig kívül.
  3. Vágás:
    • A vonal és a vágási ablak szélei közötti metszéspontokat kiszámoljuk.
    • A vonalat az új metszéspontokkal újra ellenőrizzük, amíg végül teljesen belülre nem kerül.


Példa a működésre

Tételezzük fel, hogy adott egy vágási ablak: - ( x_{} = 10 ), ( y_{} = 10 ), - ( x_{} = 30 ), ( y_{} = 30 ).

Vonalszakasz: ( (x_1, y_1) = (5, 5) ) és ( (x_2, y_2) = (35, 35) ).

  1. Regionális kódok kiszámítása:
    • ( (5, 5) ) regionális kódja: ( 0101 ) (bal és alsó régió).
    • ( (35, 35) ) regionális kódja: ( 1001 ) (felső és jobb régió).
  2. Gyors ellenőrzés:
    • A két kód bitenkénti ÉS művelete: ( 0101 & 1001 = 0001 ), tehát a vonal metszi a téglalapot.
  3. Vágás:
    • Kiszámítjuk a metszéspontokat a vágási ablak szélein, és csak a látható részt tartjuk meg.


Python Implementáció

Az alábbi implementáció a Cohen-Sutherland-algoritmust mutatja be: 

# Regionális kódok bitértékei
INSIDE = 0  # 0000
LEFT   = 1  # 0001
RIGHT  = 2  # 0010
BOTTOM = 4  # 0100
TOP    = 8  # 1000

# Regionális kód kiszámítása
def compute_code(x, y, x_min, y_min, x_max, y_max):
    code = INSIDE
    if x < x_min: code |= LEFT
    elif x > x_max: code |= RIGHT
    if y < y_min: code |= BOTTOM
    elif y > y_max: code |= TOP
    return code

def cohen_sutherland(x1, y1, x2, y2, x_min, y_min, x_max, y_max):
    code1 = compute_code(x1, y1, x_min, y_min, x_max, y_max)
    code2 = compute_code(x2, y2, x_min, y_min, x_max, y_max)
    accept = False

    while True:
        if code1 == 0 and code2 == 0:  # Teljesen belül
            accept = True
            break
        elif (code1 & code2) != 0:  # Teljesen kívül
            break
        else:
            code_out = code1 if code1 != 0 else code2
            if code_out & TOP:
                x = x1 + (x2 - x1) * (y_max - y1) / (y2 - y1)
                y = y_max
            elif code_out & BOTTOM:
                x = x1 + (x2 - x1) * (y_min - y1) / (y2 - y1)
                y = y_min
            elif code_out & RIGHT:
                y = y1 + (y2 - y1) * (x_max - x1) / (x2 - x1)
                x = x_max
            elif code_out & LEFT:
                y = y1 + (y2 - y1) * (x_min - x1) / (x2 - x1)
                x = x_min

            if code_out == code1:
                x1, y1 = x, y
                code1 = compute_code(x1, y1, x_min, y_min, x_max, y_max)
            else:
                x2, y2 = x, y
                code2 = compute_code(x2, y2, x_min, y_min, x_max, y_max)

    if accept:
        print(f"Látható vonalszakasz: ({x1}, {y1}) és ({x2}, {y2})")
    else:
        print("A vonalszakasz nem látható.")

# Példa használat
x_min, y_min, x_max, y_max = 10, 10, 30, 30  # Vágási ablak
x1, y1, x2, y2 = 5, 5, 35, 35  # Vonalszakasz koordinátái

cohen_sutherland(x1, y1, x2, y2, x_min, y_min, x_max, y_max)

Kimenet:

Látható vonalszakasz: (10.0, 10.0) és (30.0, 30.0)

Előnyök:

  1. Hatékony, mivel a regionális kódok alapján gyorsan eldönthető, hogy egy vonal látható-e.
  2. Csökkenti a szükséges számítások számát.

Hátrányok:

  1. Csak téglalap alakú vágási ablakokra alkalmazható.
  2. Bonyolultabb, ha nem lineáris objektumokra kell alkalmazni.


Alkalmazások:

  • Számítógépes grafika: 2D-s grafikák optimalizált megjelenítése.
  • Geometriai számítások: Látványvonalak kiszámítása és rajzolása.
  • Térképészeti szoftverek: Navigációs rendszerekben szakaszok korlátozása a látható területre.

Fordítások

Tartalom

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Cohen-Sutherland-algoritmus&oldid=3480708”