丹·科恩和伊凡·苏泽兰直线段裁剪算法，是计算机图形学直线段裁剪算法的一种，由丹·科恩（Dan Cohen）和伊凡·苏泽兰（Ivan Sutherland）两人提出。

算法思想

算法描述

算法思想

丹·科恩和伊凡·苏泽兰直线段裁剪算法主要分三步进行。

1．将矩形窗口四条边界延长，则整个被平面分成九个区域，如图1所示，每个区域内的点都对应着一个四位二进制区位码，其各位含义如如图2所示。

任何位赋值1，代表端点落在相应的位置上，否则该位置为0。例如，如果端点在裁剪窗口内，则区位码为0000，如果端点在矩形裁剪窗口的左下角，则区位码为0101。

根据要裁剪线段P1P2的端点坐标求出相应的编码值C1和C2。

2．判断P1、P2的位置。

若C1=C2=0，即P1、P2的编码全为零，线段P1P2在窗口内，保留线段P1P2，过程结束。

否则，若C1∧C2≠0，即作P1、P2编码的逻辑与，结果为非零时，表示P1、P2在窗口的同侧，弃之，过程结束。

否则，线段必有一端点在窗口外，令该点为P1，进行下一步。

3．根据P1点的编码值，确定其在哪条边界线之外，求线段与该边界线的交点P，交点把线段分成两段，舍去P1P段，把交点P作为剩余线段的P1端点重新进行第二步。

如图3所示，线段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);

}