一、前言
Sutherland-Cohen算法
它叫，“苏泽兰抠恨算法” :smile:
用矩形框裁剪直线。
整体思想
首先，判断直线是否完全在裁剪矩形内，或者完全在矩形框外。
若不能得出以上两种结论，则计算出线段与矩形边界的交点。交点把直线分成两段(若两个交点，则先看其中一个交点)，把完全在窗口外的舍去，然后再对另一条再做判断。
P.S 具体实现中，并非是将窗口外的舍去，其本质也就是找出新的两个线段端点(被切割部分)，然后再将其画出罢了。
二、实现效果
三、分区编码
先说说判断端点位置用的分区编码
将屏幕分成九个区域，用四位0、1编码为每一个区域编码。
- 最中间，是裁剪的矩形框区域，内部为0000.
- 其左侧部分，也就是x值小于XL部分，其第四位编码均为1；
- 其右侧部分，也就是x值大于XR部分，其第三位编码均为1，
- 其上部，也就是y值大于YT部分，其第一位编码均为1；
- 其下部，也就是y值小于YB部分，第第二位编码均为1.
如下，（笛卡尔平面坐标系，非屏幕坐标系）
四、具体实现步骤
4.1总体思路
对直线两端点p1、p2进行编码，
p1、p2编码分别记为，code1、code2。
code1={a1、b1、c1、d1}
code2={a2、b2、c2、d2}
其中，ai，bi，ci、di的取值范围为{0，1}，i={1，2}
若ai=bi=ci=di=0，此情况为直线在矩形同一外域，则显示整条直线。否则，进行第三步
对四位编码逐位判断。
若a1=1或者a2=1，则该点在矩形框的上部，也就是“三、分区编码”中的情况“4”。则求直线与矩形框的纵坐标的y的最小值(屏幕坐标系)，将该点坐标移为交点(也就相当于删去交点以上部分)
若b1=1或者b2=1，则该点在矩形框的下部，也就是“三、分区编码”中的情况“5”。则求直线与矩形框的纵坐标的y的最大值(屏幕坐标系)，将该点坐标移为交点(也就相当于删去交点以下部分)
若c1=1或者c2=1，则该点在矩形框的右部，也就是“三、分区编码”中的情况“3”。则求直线与矩形框的横坐标的x的最大值(屏幕坐标系)，将该点坐标移为交点(也就相当于删去交点以右部分)
若d1=1或者d2=1，则该点在矩形框的左部，也就是“三、分区编码”中的情况“2”。则求直线与矩形框的横坐标的y的最小值(屏幕坐标系)，将该点坐标移为交点(也就相当于删去交点以左部分)
至于”矩形框的上部“，则是在视觉上而言。以上皆是。
画出直线。(此时会只画出被移动端点后的直线)
4.2 C#代码实现
4.2.1 各参数含义
- x1, y1, x2, y2：输入直线两端坐标；
- code1, code2：两端点的编码，各四位。
- done：是否剪裁完毕的标志，True：剪裁完。
- display：是否需显示的标志，True：显示直线x1, y1, x2, y2。
- m：直线之斜率。
- mark：是否需要进行交换标志。
4.2.1 方法功能描述
1）主算法为clip_a_line。它调用四个子程序，功能分别为：
2）encode(x, y, c)：功能为：判断点（x, y）所在的区域，赋予c以相应的编码。
3）accept(c1, c2)：功能为：根据两端点的编码c1, c2，判断直线是否在窗口之内。
4）reject(c1, c2)：功能为：根据两端点的编码c1, c2，判断直线是否在窗口之外。
5）swap_if_needed(x1, y1, x2, y2, c1, c2)；功能为：判断（x1, y1）是否在窗口之外，如否，则将x1, y1, c1值与x2, y2, c2值交换
4.2.3 代码部分
using System;
using System.Drawing;
using System.Windows.Forms;
namespace Cohen_Sutherland
{
public partial class Form1 : Form
{
static Graphics graphics;
static Bitmap bitmap;
public Form1()
{
InitializeComponent();
graphics = panel1.CreateGraphics();
bitmap = new Bitmap(panel1.Width, panel1.Height);
}
Pen linepen = new Pen(Color.Red, 2);//原始画线画笔
Pen linepen1 = new Pen(Color.Green, 2);//裁剪画笔
Pen Ectanglepen = new Pen(Color.Blue, 2);//矩形画笔
private void button_DrawrEctangle_Click(object sender, EventArgs e)
{
Point p1 = new Point(260, 200);
Point p2 = new Point(410, 200);
Point p3 = new Point(410, 350);
Point p4 = new Point(260, 350);
Point[] points;
points = new Point[] { p1, p2, p3, p4 };
graphics.DrawPolygon(Ectanglepen, points);
graphics.DrawImage(bitmap, 0, 0, panel1.Width, panel1.Height);
}
private void button_DrawLine_Click(object sender, EventArgs e)
{
graphics.DrawLine(linepen, 190, 180, 460, 290);
}
private void button_Clip_Click(object sender, EventArgs e)
{
clip_a_line(190, 180, 460, 290, 260, 200, 410, 350);
}
//为p1、p2端点编码
public void encode(int x, int y, int[] code, int xw_min, int xw_max, int yw_min, int yw_max)
{
int i;
for (i = 0; i < 4; i++)
code[i] = 0;
if (x < xw_min)
code[3] = 1;
else
if (x > xw_max)
code[2] = 1;
if (y > yw_max)
code[1] = 1;
else
if (y < yw_min)
code[0] = 1;
}
//主函数，总控
public void clip_a_line(int x1, int y1, int x2, int y2, int xw_min, int yw_min, int xw_max, int yw_max)
{
int[] code1 = new int[4];//p1端点的编码
int[] code2 = new int[4];//p2端点的编码
int done;
int display;
float m;//直线斜率
int x11, x22, y11, y22, mark;
done = 0; // done为是否剪裁完毕的标志变量
display = 0; // display为是否显示直线的标志变量
while (done == 0)
{
x11 = x1;
x22 = x2;
y11 = y1;
y22 = y2;
encode(x1, y1, code1, xw_min, xw_max, yw_min, yw_max); // 为起点编码
encode(x2, y2, code2, xw_min, xw_max, yw_min, yw_max); // 为终点编码
if (accept(code1, code2) == 1) // 判断直线两端点是否都在剪裁框内，是则剪裁完毕，显示直线
{
done = 1;
display = 1;
break;
}
else if (reject(code1, code2) == 1) // 判断直线两端点是否在剪裁框的同一外域，是则剪裁完毕，显示直线
{
done = 1;
break;
}
//mark是否交换p1、p2的标志等于1则交换
//swap_if_needed方法只是判断出是否需要交换、并返回是否需要交换的标志mark
mark = swap_if_needed(code1, code2); // mark的意义是:swap_if_needed中是否交换过code1[4]和code2[4]
if (mark == 1) // 若交换过，mark = swap_if_needed = 1,否则mark = swap_if_needed = 0
{
x1 = x22; // 若mark = 1，交换两端点坐标
x2 = x11;
y1 = y22;
y2 = y11;
}
if (x1 == x2) // 斜率不存在的情况。即，x1=x2，则令斜率为 -1
m = -1;
else
m = (float)(y2 - y1) / (float)(x2 - x1);// 计算斜率
// 根据起点p1编码的每一位，对直线进行剪裁，实际上是移动起点的坐标
//【注意】：处于屏幕坐标系下
if (code1[0] == 1) //判断编码第一位，为1，则该点在视觉上处于“上侧”，屏幕坐标系上则p1纵坐标小于矩形纵坐标最小值。
{
if (x1 != x2)
x1 += (int)((yw_min - y1) / m);//x1移动到直线与yw_min交点处。
y1 = yw_min;//将p1的y1移为矩形纵坐标最小值。
}
else
if (code1[1] == 1)
{
if (x1 != x2)
x1 -= (int)((y1 - yw_max) / m);
y1 = yw_max;
}
else
if (code1[2] == 1)
{
y1 -= (int)((x1 - xw_max) * m);
x1 = xw_max;
}
else
if (code1[3] == 1)
{
y1 += (int)((xw_min - x1) * m);
x1 = xw_min;
}
}
if (display == 1)
{// 若显示直线标志为1，则画出直线
graphics.Clear(Color.White);//清空屏幕
//画出裁剪矩形
Point p1 = new Point(xw_min, yw_min);
Point p2 = new Point(xw_max, yw_min);
Point p3 = new Point(xw_max, yw_max);
Point p4 = new Point(xw_min, yw_max);
Point[] points;
points = new Point[] { p1, p2, p3, p4 };
graphics.DrawPolygon(Ectanglepen, points);
//画出直线
graphics.DrawLine(linepen1, x1, y1, x2, y2);
}
}
//判断p1、p2是否都在矩形内部
public int accept(int[] code1, int[] code2)
{
int i, flag;
flag = 1;
for (i = 0; i < 4; i++)
if ((code1[i] == 1) || (code2[i] == 1))
{
flag = 0;
break;
}
return (flag);
}
//判断p1、p2是否都在矩形外部
public int reject(int[] code1, int[] code2)
{
int i, flag;
flag = 0;//否
for (i = 0; i < 4; i++)
if ((code1[i] == 1) && (code2[i] == 1))
{
flag = 1;//是
break;
}
return (flag);
}
//p1、p2是否需要被交换
public int swap_if_needed(int[] code1, int[] code2)
{
int i, flag1, flag2, tmp;
flag1 = 1;
for (i = 0; i < 4; i++)
if (code1[i] == 1)
{
flag1 = 0;//code1中存在1，即在点外部。不需要交换
break;
}
flag2 = 1;
for (i = 0; i < 4; i++)
if (code2[i] == 1)
{
flag2 = 0;//code2中存在1，即点在外部。不需要交换
break;
}
if ((flag1 == 0) && (flag2 == 0))//说明两个编码中的含有1，则不能交换
return (0);
if ((flag1 == 1) && (flag2 == 0))//此时code1需要被交换，code2不需要被交换，
{ //将二者编码进行交换。
for (i = 0; i < 4; i++)
{
tmp = code1[i];
code1[i] = code2[i];
code2[i] = tmp;
}
return (1); //返回需要交换坐标的信号，在总控方法中对坐标进行交换
}
return (0); //返回不需要交换坐标的信号。
}
}
}五、流程图
5.1clip_a_line(总控方法)
5.2 encode方法
5.3 reject方法
5.4 accept方法
5.5 swap_if_needed方法
