科恩-薩瑟蘭算法

科恩－薩瑟蘭算法（英語：Cohen–Sutherland algorithm），是計算機圖形學直線段裁剪算法的一種，由丹尼·科恩和伊萬·薩瑟蘭兩人提出。

算法描述

科恩－薩瑟蘭算法主要分三步進行：

第一步

將矩形窗口四條邊界延長，則整個被平面分成九個區域。

每個區域內的點都對應着一個四位二進制區位碼。

任何位賦值1，代表端點落在相應的位置上，否則該位置為0。例如，如果端點在裁剪窗口內，則區位碼為0000，如果端點在矩形裁剪窗口的左下角，則區位碼為0101。

根據要裁剪線段P1P2的端點坐標求出相應的編碼值C1和C2。

第二步

判斷P1、P2的位置。

若C1=C2=0，即P1、P2的編碼全為零，線段P1P2在窗口內，保留線段P1P2，過程結束。

否則，若C1∧C2≠0，即作P1、P2編碼的邏輯與，結果為非零時，表示P1、P2在窗口的同側，棄之，過程結束。

否則，線段必有一端點在窗口外，令該點為P1，進行下一步。

第三步

根據P1點的編碼值，確定其在哪條邊界線之外，求線段與該邊界線的交點P，交點把線段分成兩段，捨去P1P段，把交點P作為剩餘線段的P1端點重新進行第二步。

線段a經第二步測試為窗口內線段（C1=C2=0），取之。線段b經第二步測試為窗口外同側線段（C1∧C2≠0），棄之。線段c需在第三步求出與窗口邊界的交點P3，捨去P1P3段，把P3作為新的P1再進行第二步測試，又到第三步求出與窗口邊界的交點P4，捨去P4P2段，再把P4作為新的P2，經第二步測試為窗口內線段，取之。

示例代碼

C語言

#define LEFT 1
#define TOP 8
#define RIGHT 2
#define BOTTOM 4
 
void encode (x, y, color)
float x,y;
int *code; {
	int c = 0;
	if ( x <XL)
		c = c|LEFT;
    else if ( x> XR)
		c = c|RIGHT;
    if (y < YB)
		c = c|BOTTOM;
    else if (y > YT)
		c = c|TOP;
    *code = c;
    return;
}

void Swappoint (x1, y1, x2, y2)
float *x1,*y1,*x2*,x2; {
    float t;
    t = *x1; *x1 = *x2; *x2 = t;
    t = *y1; *y1 = *y2; *y2 = t;
}
 
void SwapCode (code1, code2)
int *code1,*code2; {
    int t;
    t = *code1; *code1 = *code2; *code2 = t;
}
 
/*(x1,y1)与(x2,y2)是线段端点坐标，其他四个参数分别为窗口左、右、上、下四个边界*/
C_S_Line_Clip (x1, y1, x2, y2, XL, XR, YT, YB)
float x1,y1,x2,y2, XL, XR,YT, YB; {
    int code1, code2, code;
    encode (x1, y1, &code1);
    encode (x2, y2, &code2);
    while (code1 != 0 && code2 != 0) {
        if (code1 & code2 != 0)
            return;
        if (code1 == 0) {
            SwapPoint (&x1, &y1, &x2, &y2);
            SwapCode (&code1, &code2);
        }
        code = code1;
        if (LEFT & code != 0) { /*线段与左边界相交*/
            x = XL;
            y = y1+(y2-y1)*(XL-x1)/(x2-x1);
        }
        else if (RIGHT & code != 0) { /*线段与右边界相交*/
            x = XR;
            y = y1+(y2-y1)*(XR-x1)/(x2-x1);
        }
        else if (TOP & code !=0) { /*线段与上边界相交*/
            y = YT;
            x = x1+(x2-x1)*(YT-y1)/(y2-y1);
        }
        else if (BOTTOM & code != 0) { /*线段与下边界相交*/
            y = YB;
            x = x1+(x2-x1)*(YB-y1)/(y2-y1);
        }
        x1 = x;
        y1 = y;
        encode (x, y, code1);
    }
    line (x1, y1, x2, y2);
}