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.
Vágási ablak:
Vonalak osztályozása:
Regionális kódok (outcode-ok):
Az alábbi ábrában látható a kódok kiosztása:
1010 | 1000 | 1001
------------------
0010 | 0000 | 0001
------------------
0110 | 0100 | 0101
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) ).
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)
Látható vonalszakasz: (10.0, 10.0) és (30.0, 30.0)