维基百科
科恩－苏泽兰算法
| 此條目需要补充更多来源。 (2018年8月22日) |
科恩－苏泽兰算法（英語：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); } 参考文献
- ^ 张义宽. 计算机图形学. 西安: 西安电子科技大学出版社. 2004.