已经处理退化边的多边形裁剪算法

//编译环境：Visual C++ 6.0，EasyX_20190219(beta)
#include<graphics.h>
#include<conio.h>
#include<iostream>
#define max 30
using namespace std;

//设置裁剪框的大小和位置,裁剪多边形顶点和顶点数，以全局变量给出
double xl=5,xr=140,yt=190,yb=74;
int inlength=9;
POINT Vertex[]={ {110,84},{160,94},{90,169},{90,94},{70,90},{50,230}, {165,230},{175,89},{163,54} };
//求多边形的一条边sp和裁剪边point0 point1的交点
void Intersect(POINT S,POINT P,POINT point0,POINT point1,POINT &I)
{
	if(point0.y==point1.y)//水平裁剪边
	{
		I.y=point0.y;
		I.x=S.x+(point0.y-S.y)*(P.x-S.x)/(P.y-S.y);
	}
	else//竖直裁剪边
	{
		I.x=point0.x;
		I.y=S.y+(point0.x-S.x)*(P.y-S.y)/(P.x-S.x);
	}
}

//测试顶点与裁剪边的内外关系
bool Inside(POINT text,POINT point0,POINT point1)
{
	if(point1.x>point0.x){//裁剪边为窗口的下边
		if(text.y>=point0.y)
			return true;}

	else if(point1.x<point0.x){//裁剪边为窗口的上边
        if(text.y<=point0.y)
			return true;}

	else if(point1.y>point0.y){//裁剪边为窗口的右边
		if(text.x<=point0.x)
			return true;}

	else if(point1.y<point0.y){//裁剪边为窗口的左边
		if(text.x>=point0.x)
			return true;}

	return false;
}

//将新的定点加入结果多边形顶点表
void Output(POINT newpoint,int &length,POINT outps[])
{
	outps[length].x=newpoint.x;
	outps[length].y=newpoint.y;
	length++;
}

//裁剪算法
void SutherlandHodgmanPolygonClip(int inlength,POINT inpoints[],int &outlength,POINT outpoints[],POINT point0,POINT point1)
{
	POINT S,P,I;
	int j;
	outlength=0;
	S=inpoints[inlength-1];
	for(j=0;j<inlength;j++)
	{
		P=inpoints[j];
		if(Inside(P,point0,point1))
		{ 
			if(Inside(S,point0,point1))
			{Output(P,outlength,outpoints);}
			else
			{
				Intersect(S,P,point0,point1,I);
				Output(I,outlength,outpoints);
				Output(P,outlength,outpoints);}}
		else if(Inside(S,point0,point1))
		{
			Intersect(S,P,point0,point1,I);
			Output(I,outlength,outpoints);}
		S=P;}
}

int main()
{
	POINT Edge[]={ {xr,yb},{xr,yt},{xl,yt},{xl,yb} };
	initgraph(1000,900);
	polygon(Edge,4);
	setcolor(RED);
	polygon(Vertex,inlength);
    int i;
	POINT OutPts1[max],OutPts2[max],OutPts3[max],OutPts4[max];
	int length1,length2,length3,length4;
    SutherlandHodgmanPolygonClip(inlength,Vertex,length1,OutPts1,Edge[0],Edge[1]);//右边窗口裁剪边
	SutherlandHodgmanPolygonClip(length1,OutPts1,length2,OutPts2,Edge[1],Edge[2]);//下边窗口裁剪边
	SutherlandHodgmanPolygonClip(length2,OutPts2,length3,OutPts3,Edge[2],Edge[3]);//左边窗口裁剪边
	SutherlandHodgmanPolygonClip(length3,OutPts3,length4,OutPts4,Edge[3],Edge[0]);//上边窗口裁剪边
	MOUSEMSG m;
	while(true)
	{		  
		  m=GetMouseMsg();
		  switch(m.uMsg)
		  {
		    case WM_LBUTTONDOWN:
				cleardevice();
				setcolor(RED);
				polygon(Edge,4);
				setcolor(YELLOW);
				polygon(OutPts4,length4);
				for(i=0;i<length4;i++)
				{OutPts4[i].x+=300;}
				polygon(OutPts4,length4);
				break;
			case WM_RBUTTONDOWN:
				return 0;
		  }
	}
	_getch();
	closegraph();
	return 0;
}

以上是按照右下左上的顺序进行裁剪的，当然读者可以按照自己的习惯进行调整。

Sutherland-Hodgman算法也叫逐边裁剪法，该算法是萨瑟兰德(I．E．Sutherland)和霍德曼(Hodgman)在1974年提出的。这种算法采用了分割处理、逐边裁剪的方法。一，基本思想: 一次用窗口的一条边裁剪多边形。 考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分:可见一侧；不可见一侧。多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种情况（1）仅输出1个顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的1个交点I；情况（4）输出线段SP与裁剪线的1个交点I和1个终点P**

顺时针访问多边形各条边，可以以上面的基本思想来对上图多边形进行裁剪，可以得到正确的结果二、算法实现：　　1、已知：多边形顶点数组src，顶点个数n，
　 　　　　　定义新多边形顶点数组dest。　　2、赋初值：用变量flag来标识：
　　　　　　　　　　0表示在内侧，1表示在外侧。 3、对多边形的n条边进行处理，对当前点号的考虑为：0～n-1。
　　　for(i=0；i<n；i++)
　　　{
　　　　if(当前第i个顶点是否在边界内侧？) {
　　　　　if(flag!=0) /前一个点在外侧吗？/
　　　　　{
　　　　　　flag=0；/从外到内的情况，将标志置0,作为下一次循环的前一点标志/
　　　　　　(dest + j) =求出交点；　/将交点dest放入新多边形/ j++；
}
　　　　　
　　　　　(dest + j)= (src + i)； /将当前点srci放入新多边形/ j++；
}
　　　else
　　　{
　　　　　if(flag==0) /前一个点在内侧吗？/
　　　　　{
　　　　　　flag=1；/从内到外的情况，将标志置1,作为下一次循环的前一点标志/
　　　　　　(dest + j) =求出交点；　/将交点dest放入新多边形/ j++；
}
　　 }
　　　　s= (src + i)； /将当前点作为下次循环的前一点/
　}三，算法特点：　　Sutherland－Hodgeman多边形裁剪算法具有一般性，被裁剪多边形可以是任意凸多边形或凹多边形，裁剪窗口不局限于矩形，可以是任意凸多边形。
　　上面的算法是多边形相对窗口的一条边界进行裁剪的实现，对于窗口的每一条边界依次调用该算法程序，并将前一次裁剪的结果多边形作为下一次裁剪时的被裁剪多边形，即可得到完整的多边形裁剪程序。//点在有向线段那侧/向量叉积法 　　为简单计，测试点表示为P点。假设窗口边界方向为顺时针，如图中所示，对于其中任一边界向量，从向量起点A向终点B看过去： 　　如果被测试点P在该边界线右边(即内侧)，AB×AP的方向与X-Y平面垂直并指向屏幕里面，即右手坐标系中Z轴的负方向。 　　反过来，如果P在该边界线的左边(即外侧)，这时AB×AP的方向与X-Y平面垂直并指向屏幕外面，即右手坐标系中Z轴的正方向。 　　设：点P(x，y)、点A(xA，yA)、点B(xB，yB)， 　　　　向量AB={(xB-xA)，(yB-yA)}， 　　　　向量AP={(x-xA)，(y-yA)}， 　　那么AB×AP的方向可由下式的符号来确定： V=(xB-xA)·(y-yA)-(x-xA)·(yB-yA) // V为AB叉乘AP的结果向量中的z分量 　　因此，当V≤0时，P在边界线内侧； 　　　　而V>0时，P在边界线外侧。/typedef point{ int x; int y;}RtPoint; typedef struct{ RtPoint sp; //裁剪窗口边界向量起点 RtPoint ep; //裁剪窗口边界向量终点}_RtInSide; static int _RtInSide(RtVector vector, RtPoint point) // 计算上面的V，vector为裁剪窗口边界向量，point为上面的p点{ return (vector.ep.x - vector.sp.x) * (point.y - vector.sp.y) - (vector.ep.y - vector.sp.y) * (point.x - vector.sp.x);} //多边形点必须是顺时针方向// src保存的是裁剪窗口坐标点，应该是顺时针方向保存，num为裁剪窗口边界数量，dest保存裁剪后的多边形顶点数组，total为dest大小int rtPrunePSH(RtPoint src, int num, RtPoint** dest, int* total){ int i = 0, j = 0, k = -1, flag = 0; RtPoint start, stop;//被剪裁多边形的边向量起点和终点 RtPoint sp, ep;//剪裁窗口边界向量的起点和终点 RtPoint* temp = NULL; // temp保存针对某一裁剪窗口边界裁剪后的新坐标 temp = (RtPoint*)malloc(sizeof(RtPoint) * 3 * (*total)); if (temp == NULL) return -1; sp = *(src + num - 1); for ( i = 0; i < num; i++)//剪裁窗口 { ep = *(src + i); start = *((*dest) + *total - 1); flag = _RtInSide(rtVector(sp, ep), start) > 0 ? 0 : 1; //在外侧，flag为0，在内侧时flag为1 for ( j = 0; j < *total; j++)//被剪裁的多边形 { stop = *((*dest) + j); if (_RtInSide(rtVector(sp, ep), stop) <= 0)//当前第i个顶点是否在边界内侧 { if (flag == 0)/前一个点在外侧吗？/ { flag = 1;/从外到内的情况，将标志置1,作为下一次循环的前一点标志/ k++; CRtPoint point; CRtPoint st(sp.x, sp.y), et(ep.x, ep.y); CRtLine v1(st, et);//v1为由窗口边界向量起点sp和终点ep组成的直线 st.SetData(start.x, start.y); et.SetData(stop.x, stop.y); //v2为由多边形当前边起点start和终点stop组成的直线 CRtLine v2(st, et); v2.Intersect(v1,point); //两直线求交运算，交点保存到point数组里面 (temp + k)->x = point[0];/将交点放入新多边形/ (temp + k)->y = point[1]; } k++; *(temp + k) = stop;/将当前点pi放入新多边形/ } else { if (0 != flag)/前一个点在内侧吗？/ { flag = 0;/从内到外的情况，将标志置1,作为下一次循环的前一点标志/ k++; CRtPoint point; // 同上面一样 CRtPoint st(sp.x, sp.y), et(ep.x, ep.y); CRtLine v1(st, et); st.SetData(start.x, start.y); et.SetData(stop.x, stop.y); CRtLine v2(st, et); v2.Intersect(v1,point); (temp + k)->x = point[0];/将交点放入新多边形/ (temp + k)->y = point[1]; } } start = stop;/将当前点作为下次循环的前一点/ } sp = ep; *total = k + 1; // k+1为一次裁剪后生成的新坐标点的数量 memcpy(*dest, temp, sizeof(RtPoint) * (*total)); k = -1; } return 0;}
转载来源：http://blog.csdn.net/juyingmin/article/details/5611458
https://blog.csdn.net/damotiansheng/article/details/43274183

Cohen-SutherLand算法

算法理论

算法总体思想是，对于每条线段$P_1P_2$，(1)若$P_1P_2$全在窗口内，取之；(2)若$P_1P_2$明显在窗口外，弃之；(3)若无法满足上述两条件，则把线段分为两段，窗口外的可弃之，剩下的重复处理。
为方便处理，将图形区按下表分类：

1001	1000	1010
0001	0000	0010
0101	0100	0110

于是每个点可以根据上图获得一个区域码。对于某个线段，若：
code1=code2=0，则线段在窗口内
(code1&code2)!=0，则线段在窗口的同侧，线段在窗口外
否则即为第三种情况。则将窗口外的端点与边界求交点，替换原有交点，继续计算。

中点分割算法的理论与上述算法基本类似，就是求线段端点的方法不同，使用二分法寻找边界点，而非直接计算。

算法实现

#include<iostream>
#include<algorithm>
#include<opencv2\core\core.hpp>
#include<opencv2\highgui\highgui.hpp>
#include"MyLine.h"

#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
#define WIDTH 1000
#define HEIGHT 500

using namespace std;
using namespace cv;

int xl, xr, yb, yt;

void DDALine(Mat& m, const int x0, const int y0, const int x1, const int y1, const cv::Vec3b& v);
int Encode(int x, int y);
void Cohen_SutherLand(Mat& m, MyLine& L);

int main(){
    vector<MyLine> lv;
    int n,i;
    int x1, y1, x2, y2;
    cout << "please input the number of lines" << endl;
    cin >> n;
    for (i = 1; i <= n; i++){
        cout << "please input the coordinates of the vertexes of the No." << i << " line" << endl;
        cin >> x1 >> y1 >> x2 >> y2;
        lv.push_back(MyLine(MyPoint(x1, y1), MyPoint(x2, y2)));
    }
    cout << "please input the border of the screen, xl, xr, yb, yt" << endl;
    cin >> xl >> xr >> yb >> yt;
    Mat imageROI = Mat(HEIGHT, WIDTH, CV_8UC3, Scalar(255, 255, 255));
    for (i = 0; i < HEIGHT; i++){
        imageROI.at<Vec3b>(i, xl) = Vec3b(0, 0, 0);
        imageROI.at<Vec3b>(i, xr) = Vec3b(0, 0, 0);
    }
    for (i = 0; i < WIDTH; i++){
        imageROI.at<Vec3b>(yb, i) = Vec3b(0, 0, 0);
        imageROI.at<Vec3b>(yt, i) = Vec3b(0, 0, 0);
    }//draw border
    //Cohen-SutherLand
    vector<MyLine>::iterator iter;
    for (iter = lv.begin(); iter != lv.end(); iter++){
        Cohen_SutherLand(imageROI, *iter);
    }
    namedWindow("显示结果");
    imshow("显示结果", imageROI);
    waitKey();
}

int Encode(int x, int y){
    int code=0;
    if (x < xl){
        code = code | LEFT;
    }
    else if (x>xr){
        code = code | RIGHT;
    }
    if (y < yb){
        code = code | BOTTOM;
    }
    else if (y>yt){
        code = code | TOP;
    }
    return code;
}

void Cohen_SutherLand(Mat& m, MyLine& L){
    int code1, code2, code;
    float x, y, x1, y1, x2, y2;
    x1 = L.getP1().GetX();
    y1 = L.getP1().GetY();
    x2 = L.getP2().GetX();
    y2 = L.getP2().GetY();
    code1 = Encode(x1, y1);
    code2 = Encode(x2, y2);
    while (code1 != 0 || code2 != 0){
        if ((code1&code2) != 0){
            return;
        }
        code = code1;
        if (code == 0){
            code = code2;
        }
        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);
        }
        if ((BOTTOM&code) != 0){
            y = yb;
            x = x1 + (x2 - x1)*(yb - y1) / (y2 - y1);
        }
        else if ((TOP&code) != 0){
            y = yt;
            x = x1 + (x2 - x1)*(yt - y1) / (y2 - y1);
        }
        if (code == code1){
            x1 = x;
            y1 = y; 
            code1 = Encode(x, y);
        }
        else{
            x2 = x;
            y2 = y;
            code2 = Encode(x, y);
        }
    }
    DDALine(m, x1, y1, x2, y2, Vec3b(0, 0, 0));
    return;
}

结果：
算法总体比较简单，就是!=与&的优先级需要注意一下。

Liang-Barskey算法

算法理论

首先需要介绍Cyrus-Beck算法，可以对多边形区域进行裁剪。对于某线段，用参数方程表示为:

$$P(t)=(P_2-P_1)t+P_1$$ 对于凸多边形上的任意一点有：
$$N\bullet (P(t)-A)>0$$ 则线段必定通过多边形的内侧。其中N是该点法向量。
故可见线段的参数区间为： $$\begin{cases} N\bullet (P(t)-A)>0\\ 0\leqslant t\leqslant 1\\ \end{cases}$$ 实际计算时，只需要求出 $t_{min}$和 $t_{max}$，即可求出线段的两端点。上式可变为：
$$\begin{cases} N\bullet ((P_2-P_1)t+P_1-A)>0\\ 0\leqslant t\leqslant 1\\ \end{cases}$$ $$\begin{cases} N\bullet (P_1-A)+N\bullet (P_2-P_1)>0\\ 0\leqslant t\leqslant 1\\ \end{cases}$$ 当 $N\bullet (P_2-P_1)=0$时，线段与对应边平行，当 $N\bullet (P_1-A)>0$时线段与多边形相交。若与线段在多边形外，直接跳出循环；若线段在多边形内，则继续判断下一条边。
当 $N\bullet (P_2-P_1)\not=0$时，令 $t_i=\frac{N_i\bullet (P_1-A_i)}{N_i\bullet (P_2-P_1)}$，判定条件为：
$$\begin{cases} t\geqslant t_i, 当N_i\bullet(P_2-P_1)>0\\ t\leqslant t_i, 当N_i\bullet(P_2-P_1)<0\\ 0\leqslant t \leqslant 1 \end{cases}$$
由于上述方法需要指定法向量的方向，与边上的任意点，实现起来比较麻烦，直接实现Liang-Barskey算法。Liang-Barskey将上述流程中的多边形特定为矩形，过程便简单了许多，如下表所示：

边	内法向量	边上一点	$P_1-A$	$t=\frac{N_i\bullet (P_1-A_i)}{N_i\bullet (P_2-P_1)}$
x=XL	(1,0)	(XL,y)	(x1-XL,y1-y)	$\frac{x_1-XL}{-(x_2-x_1)}$
x=XR	(-1,0)	(XR,y)	(x1-XR,y1-y)	$\frac{-(x_1-XR)}{x_2-x_1}$
y=YB	(0,1)	(x,YB)	(x1-x,y1-YT)	$\frac{y_1-YT}{-(y_2-y_1)}$
y=YT	(0,-1)	(x,YT)	(x1-x,y1-YB)	$\frac{-(y_1-YB)}{y_2-y_1}$

算法实现

#include<iostream>
#include<algorithm>
#include<opencv2\core\core.hpp>
#include<opencv2\highgui\highgui.hpp>
#include"MyLine.h"
#include"MyVector.h"

#define WIDTH 1000
#define HEIGHT 500
#define XL 100
#define XR 800
#define YB 50
#define YT 400

using namespace std;
using namespace cv;

void DDALine(Mat& m, int x0, int y0, int x1, int y1, const cv::Vec3b& v);
void Liang_Barskey(Mat& m, MyPoint& P1, MyPoint& P2);
bool NoReject(double denom, double nom, double& tl, double& tu);

int main(){
    vector<MyLine> lv;
    int n, i, j;
    int x1, y1, x2, y2;
    cout << "please input the number of lines" << endl;
    cin >> n;
    for (i = 1; i <= n; i++){
        cout << "please input the coordinates of the vertexes of the No." << i << " line" << endl;
        cin >> x1 >> y1 >> x2 >> y2;
        lv.push_back(MyLine(MyPoint(x1, y1), MyPoint(x2, y2)));
    }
    Mat imageROI = Mat(HEIGHT, WIDTH, CV_8UC3, Scalar(255, 255, 255));
    for (i = 0; i < HEIGHT; i++){
        imageROI.at<Vec3b>(i, XL) = Vec3b(0, 0, 0);
        imageROI.at<Vec3b>(i, XR) = Vec3b(0, 0, 0);
    }
    for (i = 0; i < WIDTH; i++){
        imageROI.at<Vec3b>(YB, i) = Vec3b(0, 0, 0);
        imageROI.at<Vec3b>(YT, i) = Vec3b(0, 0, 0);
    }//draw border
    vector<MyLine>::iterator iter;
    for (iter = lv.begin(); iter != lv.end(); iter++){
        Liang_Barskey(imageROI, (*iter).getP1(), (*iter).getP2());
    }
    namedWindow("显示结果");
    imshow("显示结果", imageROI);
    waitKey();
}

void Liang_Barskey(Mat& m, MyPoint& P1, MyPoint& P2){
    double tl = 0, tu = 1;
    double tmin, tmax;
    MyVector v = MyVector(P1, P2);
    double dx = v.GetX();
    double dy = v.GetY();
    MyPoint Pmin, Pmax;
    if (NoReject(-dx, P1.GetX() - XL, tl, tu) && NoReject(dx, XR - P1.GetX(), tl, tu) && NoReject(-dy, P1.GetY() - YB, tl, tu) && NoReject(dy, YT - P1.GetY(), tl, tu)){
        tmin = tl;
        tmax = tu;
        Pmin = P1 + (v*tmin);
        Pmax = P1 + (v*tmax);
        DDALine(m, Pmin.GetX(), Pmin.GetY(), Pmax.GetX(), Pmax.GetY(),Vec3b(0,0,0));
    }
    return;
}

bool NoReject(double denom, double nom, double& tl, double& tu){
    float t;
    if (denom < 0){
        t = nom / denom;
        if (t>tu)
            return false;
        else if (t > tl)
            tl = t;
    }
    else if (denom > 0){
        t = nom / denom;
        if (t < tl)
            return false;
        else if (t < tu)
            tu = t;
    }
    else if (nom < 0)
        return false;
    else
        return true;
}

其中运算符重载部分省略。
结果：
这次感觉C++很多坑还是要注意。一些地方为了利用引用避免拷贝构造，却没注意变量已经析构了，还有头文件互相引用等问题。感觉写起来还是很乱，不知道是不是C++的特性使然。