liangbarsk.cpp

良友栋裁减算法裁减多边形

#include<GL/glut.h>
#include<math.h>

const int nVerts=6;//多边形顶点数
const int maxVerts=10;//裁剪后最大顶点个数
int countVerts=0;//顶点计数
bool flag=true;

class wcPt2D
{
private:
	GLfloat x,y;
public:
	wcPt2D()
	{
		x=y=0.0;
	}
	void setCoords(GLfloat xCoord,GLfloat yCoord)
	{
		x=xCoord;
		y=yCoord;
	}
	GLfloat getx()const
	{
		return x;
	}
	GLfloat gety()const
	{
		return y;
	}
};

wcPt2D Pverts[nVerts];//原多边形
wcPt2D CPverts[maxVerts];//裁剪后多边形
wcPt2D winMin,winMax;//定义裁剪窗口

GLint clipTest(GLfloat p,GLfloat q,GLfloat &u1,GLfloat &u2)
{
	GLfloat r;
	GLint returnValue=true;
	if(p<0.0)
	{
		r=q/p;
		if(r>u2)
			returnValue=false;
		else
			if(r>u1)
				u1=r;
	}
	else
		if(p>0.0)
		{
			r=q/p;
			if(r<u1)
				returnValue=false;
			else if(r<u2)
				u2=r;
		}
		else
			if(q<0.0)
				returnValue=false;
	return (returnValue);
}

void isAddVerts(wcPt2D p1,wcPt2D p2)//逆时针添加可能的裁剪窗口顶点
{
	if(p1.getx()==winMax.getx())//p1在右边界
	{
		if(p1.gety()!=winMax.gety())
		{
			if(p2.getx()!=winMax.getx())
			{
				CPverts[countVerts].setCoords(winMax.getx(),winMax.gety());
				countVerts++;
				if(p2.gety()!=winMax.gety())
				{
					CPverts[countVerts].setCoords(winMin.getx(),winMax.gety());
					countVerts++;
					if(p2.getx()!=winMin.getx())
					{
						CPverts[countVerts].setCoords(winMin.getx(),winMin.gety());
						countVerts++;
					}
				}
			}
		}
		else
		{
			if(p2.gety()!=winMax.gety())
			{
				CPverts[countVerts].setCoords(winMin.getx(),winMax.gety());
				countVerts++;
				if(p2.getx()!=winMin.getx())
				{
					CPverts[countVerts].setCoords(winMin.getx(),winMin.gety());
					countVerts++;
				}
			}
		}
		
	}

	else if(p1.gety()==winMax.gety())//p1在上边界
	{
		if(p1.getx()!=winMin.getx())
		{
			if(p2.gety()!=winMax.gety())
			{
				CPverts[countVerts].setCoords(winMin.getx(),winMax.gety());
				countVerts++;
				if(p2.getx()!=winMin.getx())
				{
					CPverts[countVerts].setCoords(winMin.getx(),winMin.gety());
					countVerts++;
					if(p2.gety()!=winMin.gety())
					{
						CPverts[countVerts].setCoords(winMax.getx(),winMin.gety());
						countVerts++;
					}
				}
			}
		}
		else
		{
			if(p2.getx()!=winMin.getx())
			{
				CPverts[countVerts].setCoords(winMin.getx(),winMin.gety());
				countVerts++;
				if(p2.gety()!=winMin.gety())
				{
					CPverts[countVerts].setCoords(winMax.getx(),winMin.gety());
					countVerts++;
				}
			}
		}
		
	}
	
	else if(p1.getx()==winMin.getx())//p1在左边界
	{
		if(p1.gety()!=winMin.gety())
		{
			if(p2.getx()!=winMin.getx())
			{
				CPverts[countVerts].setCoords(winMin.getx(),winMin.gety());
				countVerts++;
				if(p2.gety()!=winMin.gety())
				{
					CPverts[countVerts].setCoords(winMax.getx(),winMin.gety());
					countVerts++;
					if(p2.getx()!=winMax.getx())
					{
						CPverts[countVerts].setCoords(winMax.getx(),winMax.gety());
						countVerts++;
					}
				}
			}
		}
		else
		{
			if(p2.gety()!=winMin.gety())
			{
				CPverts[countVerts].setCoords(winMax.getx(),winMin.gety());
				countVerts++;
				if(p2.getx()!=winMax.getx())
				{
					CPverts[countVerts].setCoords(winMax.getx(),winMax.gety());
					countVerts++;
				}
			}
		}
		
	}

	else if(p1.gety()==winMin.gety())//p1在下边界
	{
		if(p1.getx()!=winMax.getx())
		{
			if(p2.gety()!=winMin.gety())
			{
				CPverts[countVerts].setCoords(winMax.getx(),winMin.gety());
				countVerts++;
				if(p2.getx()!=winMax.getx())
				{
					CPverts[countVerts].setCoords(winMax.getx(),winMax.gety());
					countVerts++;
					if(p2.gety()!=winMax.gety())
					{
						CPverts[countVerts].setCoords(winMin.getx(),winMax.gety());
						countVerts++;
					}
				}
			}
		}
		else
		{
			if(p2.getx()!=winMax.getx())
			{
				CPverts[countVerts].setCoords(winMax.getx(),winMax.gety());
				countVerts++;
				if(p2.gety()!=winMax.gety())
				{
					CPverts[countVerts].setCoords(winMin.getx(),winMax.gety());
					countVerts++;
				}
			}
		}
		
	}
	
}

bool lineClipLiangBarsk(wcPt2D p1,wcPt2D p2)
{
	GLfloat u1=0.0,u2=1.0,dx=p2.getx()-p1.getx(),dy;

	if(clipTest(-dx,p1.getx()-winMin.getx(),u1,u2))
		if(clipTest(dx,winMax.getx()-p1.getx(),u1,u2))
		{
			dy=p2.gety()-p1.gety();
			if(clipTest(-dy,p1.gety()-winMin.gety(),u1,u2))
				if(clipTest(dy,winMax.gety()-p1.gety(),u1,u2))
				{
					if(u1==0.0)
					{
						CPverts[countVerts].setCoords(p1.getx()+u2*dx,p1.gety()+u2*dy);
						countVerts++;
					}
					else if(u1>0.0&&u2<=1.0)
					{
						wcPt2D tmp;
						tmp.setCoords(p1.getx()+u1*dx,p1.gety()+u1*dy);
						if(!flag)
						{
							isAddVerts(CPverts[countVerts-1],tmp);
							flag=true;
						}
						CPverts[countVerts].setCoords(tmp.getx(),tmp.gety());
						countVerts++;
						CPverts[countVerts].setCoords(p1.getx()+u2*dx,p1.gety()+u2*dy);
						countVerts++;
					}
					return true;
				}
		}
	return false;
}

void init()
{
	glClearColor(1.0,1.0,1.0,0.0);

	glMatrixMode(GL_PROJECTION);
	gluOrtho2D(0.0,200.0,0.0,150.0);
}
void initPolygon()
{
	Pverts[0].setCoords(50.0,50.0);
	Pverts[1].setCoords(120.0,60.0);
	Pverts[2].setCoords(150.0,80.0);
	Pverts[3].setCoords(110.0,130.0);
	Pverts[4].setCoords(70.0,110.0);
	Pverts[5].setCoords(30.0,75.0);
}
void initClipWindow()
{
	winMin.setCoords(35.0,55.0);
	winMax.setCoords(110.0,90.0);
}
void showClipWindow()
{
	glBegin(GL_LINE_LOOP);
	glVertex2f(winMin.getx(),winMin.gety());
	glVertex2f(winMax.getx(),winMin.gety());
	glVertex2f(winMax.getx(),winMax.gety());
	glVertex2f(winMin.getx(),winMax.gety());
	glEnd();
}
void showPolygon(wcPt2D *verts,int n)
{
	glBegin(GL_POLYGON);
	for(int i=0;i<n;i++)
		glVertex2f(verts[i].getx(),verts[i].gety());
	glEnd();
}
void clip()
{
	for(int i=0;i<nVerts;i++)
	{
		if(!lineClipLiangBarsk(Pverts[i],Pverts[(i+1)%nVerts]))
			flag=false;
	}
	
}
void displayFcn()
{
	glClear(GL_COLOR_BUFFER_BIT);
	glColor3f(0.0,0.0,1.0);
	initPolygon();
	initClipWindow();
	showPolygon(Pverts,nVerts);//原多边形显示
	glColor3f(0.0,0.0,0.0);
	showClipWindow();//裁剪窗口显示
	glColor3f(1.0,0.0,0.0);
	clip();
	showPolygon(CPverts,countVerts);
	glFlush();
}

int main(int argc,char **argv)
{
	glutInit(&argc,argv);
	glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);
	glutInitWindowPosition(50,100);
	glutInitWindowSize(400,300);
	glutCreateWindow("Liang-Barsk Programme");

	init();
	glutDisplayFunc(displayFcn);
	glutMainLoop();
	return 0;
}