Python 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.
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 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')
C#
Ten sam algorytm zaimplementowany w języku C#, który obcina odcinek algorytmem Cohena-Sutherlanda, a następnie rysuje go.
public class AlgorithmCohenSutherland
float minX, minY, maxX, maxY;
public AlgorithmCohenSutherland(float minX, float minY, float maxX, float maxY)
this.minX = minX; this.minY = minY; this.maxX = maxX; this.maxY = maxY;
public byte Code(float x, float y)
byte code = 0;
code |= Convert.ToByte(y > this.maxY); code |= Convert.ToByte(Convert.ToUInt16(y this.maxX) << 2); code |= Convert.ToByte(Convert.ToUInt16(x < this.minX) << 3);
return code;
public bool IsTop(byte code)
return (code & 0x01) != 0;
public bool IsBottom(byte code)
return (code & 0x02) != 0;
public bool IsLeft(byte code)
return (code & 0x04) != 0;
public bool IsRight(byte code)
return (code & 0x08) != 0;
public void DrawLine(Graphics g, Pen pen, PointF P1, PointF P2)
byte codeP1 = this.Code(P1.X, P1.Y);
byte codeP2 = this.Code(P2.X, P2.Y);
while (true)
if (codeP1 == 0 && codeP2 == 0)
// rysuje g.DrawLine(pen, P1, P2);
return;
if ((codeP1 & codeP2) != 0)
return;
byte tmp_code;
if (codeP1 != 0)
tmp_code = codeP1;
else
tmp_code = codeP2;
float t = 0, x = 0, y = 0;
if (this.IsTop(tmp_code))
t = (this.maxY - P1.Y) / (P2.Y - P1.Y); x = P1.X + t * (P2.X - P1.X); y = this.maxY;
else if (this.IsBottom(tmp_code))
t = (this.minY - P1.Y) / (P2.Y - P1.Y); x = P1.X + t * (P2.X - P1.X); y = this.minY;
else if (this.IsLeft(tmp_code))
t = (this.maxX - P1.X) / (P2.X - P1.X); x = this.maxX; y = P1.Y + t * (P2.Y - P1.Y);
else if (this.IsRight(tmp_code))
x = this.minX; t = (this.minX - P1.X) / (P2.X - P1.X); y = P1.Y + t * (P2.Y - P1.Y);
if (tmp_code == codeP1)
P1.X = x; P1.Y = y;
codeP1 = this.Code(x, y);
else
P2.X = x; P2.Y = y;
codeP2 = this.Code(x, y);
Licencja Kod pythonowy:
Kod C#: