電腦圖形學經典：Cohen-Sutherland 編碼裁剪演算法 C 语言完整实现

演算法原理

Cohen-Sutherland 線段裁剪演算法將平面分為 9 區域，每個端點賦予 4 位元編碼 (上/下/左/右)，透過邏輯運算快速判斷線段完全內部、完全外部、或需計算交點。

區域編碼定義

#define LEFT   1  // 0001
#define RIGHT  2  // 0010
#define BOTTOM 4  // 0100
#define TOP    8  // 1000

核心流程

1. 計算兩端點編碼 code1, code2
2. Trivial Accept：code1 == 0 && code2 == 0 → 線段完全在視窗內，直接繪製
3. Trivial Reject：code1 & code2 != 0 → 線段完全在視窗某側外部，直接捨棄
4. 需裁剪：選擇編碼非零的端點，依其編碼計算與視窗邊界交點，替換該端點，重新計算編碼，回步驟 2

完整程式碼 (Turbo C 圖形庫版)

#include 
#include 

#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
#define FALSE 0
#define TRUE 1

void Line_Clipping(float x1, float y1, float x2, float y2,
                   float xw_xmin, float yw_ymin, float xw_xmax, float yw_ymax) {
    int draw = FALSE, done = FALSE;
    int code1, code2, code;
    float x, y;

    code1 = get_code(x1, y1, xw_xmin, yw_ymin, xw_xmax, yw_ymax);
    code2 = get_code(x2, y2, xw_xmin, yw_ymin, xw_xmax, yw_ymax);

    while (!done) {
        if (code1 == 0 && code2 == 0) { draw = TRUE; done = TRUE; }
        else if (code1 & code2) { done = TRUE; }
        else {
            code = (code1 != 0) ? code1 : code2; // 選取編碼非零的端點
            if (code & TOP) {
                y = yw_ymax;
                x = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
            } else if (code & BOTTOM) {
                y = yw_ymin;
                x = x1 + (y - y1) * (x2 - x1) / (y2 - y1);
            } else if (code & RIGHT) {
                x = xw_xmax;
                y = y1 + (x - x1) * (y2 - y1) / (x2 - x1);
            } else if (code & LEFT) {
                x = xw_xmin;
                y = y1 + (x - x1) * (y2 - y1) / (x2 - x1);
            }
            if (code == code1) { x1 = x; y1 = y; code1 = get_code(x1, y1, ...); }
            else               { x2 = x; y2 = y; code2 = get_code(x2, y2, ...); }
        }
    }
    if (draw) { setcolor(8); line(x1, y1, x2, y2); }
}

int get_code(float x, float y, float xmin, float ymin, float xmax, float ymax) {
    int code = 0;
    if (y > ymax) code |= TOP;
    else if (y < ymin) code |= BOTTOM;
    if (x > xmax) code |= RIGHT;
    else if (x < xmin) code |= LEFT;
    return code;
}

void main() {
    float x1=76, y1=40, x2=60, y2=80;
    float xw_xmin=50, xw_xmax=80, yw_ymin=50, yw_ymax=70;
    int gdriver=DETECT, gmode;
    initgraph(&gdriver, &gmode, "C:\\TURBOC2");
    setcolor(5);
    line(x1, y1, x2, y2);           // 原始線段
    rectangle(xw_xmin, yw_ymin, xw_xmax, yw_ymax); // 裁剪視窗
    getch();
    cleardevice();
    setcolor(8);
    rectangle(xw_xmin, yw_ymin, xw_xmax, yw_ymax);
    Line_Clipping(x1, y1, x2, y2, xw_xmin, yw_ymin, xw_xmax, yw_ymax); // 裁剪結果
    getch();
    closegraph();
}

關鍵幾何計算

• 與上/下邊界交點：已知 y，求 x = x1 + (y-y1)*(x2-x1)/(y2-y1)
• 與左/右邊界交點：已知 x，求 y = y1 + (x-x1)*(y2-y1)/(x2-x1)
• 需處理垂直/水平線段分母為 0 的特殊情況 (實務加判斷)

現代化移植建議

• 替換 graphics.h 為 SDL2 / OpenGL / Cairo / Qt 等跨平台圖形庫
• 將座標型別改為 double 提升精度
• 封裝為 clipLine(Line&, Rect) 通用函式，回傳裁剪後線段或空
• 擴充至 3D (Cyrus-Beck 演算法) 或多邊形裁剪 (Sutherland-Hodgman)

教學價值

此演算法展示「空間分區編碼 + 位元運算 + 參數方程式求交」的經典組合，是電腦圖形學、GIS、遊戲碰撞偵測的基石。建議手動推導幾個測試案例的編碼變化過程，內化邏輯判斷流程。