计算机图形学课程设计 多边形的裁剪算法

153 作为新的P 1P 2线段从算法的第一步重新开始执行。

反之，则以线段P m P 2为新的线段P 1P 2（如图4.83中的线段c ）从算法的第一步重新开始执行。

反复执行上述3步，直至找到离P 1点最远的可见点为止。

这个过程确定了距离P 1点最远的可见点。

然后对调该线段的两个端点，以线段P 2P 1为新的P 1P 2线段，重新开始实施该算法过程，就可以确定出距离P 2点最远的可见点。

这样，位于窗口内可见段的两个可见端点就确定了。

从这个算法我们可以看到，整个裁剪过程总是在执行第一步或第二步时结束。

这种结果表明：被裁剪的线段要么完全处于窗口之外而被排除掉；要么能在窗口内得到一个距对应端点最远的可见点，这个可见点可能是原直线段的一个端点，也可能是线段在被不断地中点再分过程中，最终得到的刚好和窗口边框相重的那个中点。

这里要注意的是：在判断中点和窗口边框相重时，一般不需要坐标值一定相等，也不大可能，只要在精度许可的前提下，给出一个误差允许范围即可。

4.6.3 多边形裁剪前面我们讨论了直线段裁剪，多边形裁剪是以直线段裁剪为基础，但又不同于直线段的裁剪。

多边形裁剪要比一条直线段裁剪复杂得多。

图4.84所示为用一个矩形窗口去裁剪多边形将会遇到各种不同情况，其中图4.84（a ）所示为一个完整的多边形被裁剪成两个独立的多边形；图4.84（b ）所示为一个凹多边形被裁剪成几个小多边形；图4.84（c ）所示为多边形G 经矩形窗口裁剪后出现G 1和G 2两个多边形，究竟是G 1还是G 2呢？裁剪多边形要解决两个问题，一是一个完整的封闭多边形经裁剪后一般不再是封闭的，需要用窗口边界适当部分来封闭它；二是矩形窗口的4个角点在裁剪中是否要与其他交点连线。

由于这两个问题使得我们不能简单地应用直线段裁剪方法，而需要去研究适合多边形裁剪特点的算法。

图4.84 多边形裁剪多边形裁剪方法很多，例如逐边裁剪法、双边裁剪法、分区编码裁剪法等，这里仅介绍逐边裁剪法。

weiler-atherton多边形裁剪算法weileratherton多边形裁剪算法，又称为weiler-atherton算法，是一种用于对多边形进行裁剪的算法。

它可以被用于计算机图形学中的裁剪任务，如可视化、图像处理和计算机辅助设计等领域。

本文将详细介绍weileratherton多边形裁剪算法的原理、步骤和实现方法。

1. 算法原理：weileratherton多边形裁剪算法是基于边界点的引入和处理的。

该算法将两个多边形相互之间进行裁剪，并生成裁剪结果。

算法使用四个边界点集合，分别为输入多边形的边界点集合(输入多边形顶点经过一系列处理得到)，裁剪多边形的外部边界点集合和内部边界点集合，以及裁剪结果的边界点集合。

2. 算法步骤：weileratherton多边形裁剪算法的具体步骤如下：(1) 初始化：创建输入多边形的边界点集合、裁剪多边形的外部边界点集合和内部边界点集合，并将输入多边形的边界点添加至外部边界点集合中。

(2) 遍历输入多边形的每条边：对于输入多边形的每条边，判断其与裁剪多边形的相交情况。

(3) 相交情况处理：若相交情况为内部相交或外部相交，则根据交点生成新的内部边界点，并添加至相应的边界点集合中。

(4) 构造裁剪结果：根据输入多边形的边界点集合和裁剪多边形的内部边界点集合，生成裁剪结果的边界点集合。

(5) 根据边界点集合构造裁剪结果：根据裁剪结果的边界点集合，绘制裁剪结果多边形。

3. 算法实现：weileratherton多边形裁剪算法的实现可以使用编程语言来完成。

一种常用的实现方法是通过遍历输入多边形的每个边，利用线段与裁剪多边形的边界的相交情况判断是否产生交点，并根据交点生成新的边界点。

具体的实现步骤如下：(1) 初始化输入和裁剪多边形的边界点集合。

(2) 遍历输入多边形的每条边，对于每条边，判断其与裁剪多边形的每条边的相交情况。

(3) 根据相交情况，判断是否生成交点，如果有生成交点，则根据交点生成新的边界点，并添加至相应的边界点集合中。

简单多边形裁剪算法摘要：多边形裁剪算法与线性裁剪算法具有更广泛的实用意义，因此它是目前裁剪研究的主要课题。

本文主要介绍了一种基于多边形顶点遍历的简单多边形裁剪算法，它有效降低了任意多边形裁剪复杂度。

通过记录交点及其前驱、后继信息，生成结果多边形，该算法简化了交点的数据结构，节省了存储空间，降低了算法的时间复杂度，具有简单、易于编程实现、运行效率高的特点。

关键词：多边形裁剪；交点；前驱；后继；矢量数组一、技术主题的基本原理简单多边形裁剪算法综合考虑现有多边形裁剪算法的优缺点，它是一种基于多边形顶点遍历来实现简单多边形裁剪工作的。

其主要的原理是遍历多边形并把多边形分解为边界的线段逐段进行裁剪，输出结果多边形。

二、发展研究现状近年来,随着遥感绘图、CAD辅助设计、图象识别处理技术的发展,图形裁剪算法从最初在二维平面上线和图形的裁剪扩展到三维空间里体和场的裁剪,国内外相继提出不少行之有效的算法,但越来越复杂的图形和计算也对算法的速度和适用性提出了越来越高的要求。

因此,不断简化算法的实现过程,完善细节处理,满足大量任意多边形的裁剪也就成了当今算法研究的焦点之一。

以往多边形裁剪算法不是要求剪裁多边形是矩形，就是必须判断多边形顶点的顺时针和逆时针性，即存在不实用或者是增加了多边形裁剪算法的难度。

为了解决现在的问题，我们研究现在的新多边形算法，其中，裁剪多边形和被裁剪多边形都可以是一般多边形，且不需要规定多边形输入方向。

它采用矢量数组结构，只需遍历剪裁多边形和被裁剪多边形顶点即完成多边形的裁剪，具有算法简单、运行效率高的特点。

三、新算法设计1、算法的思想本算法是为了尽量降低任意多边形裁剪算法复杂度而提出的，其主要思想是采用矢量数组结构来遍历裁剪多边形和被裁多边形顶点，记录裁剪多边形和被裁减多边形交点及其前驱、后继信息，并通过记录相邻交点的线段，然后通过射线法选择满足条件的线段，之后进行线段连接，输出对应的裁剪结果。

河南理工大学万方科技学院课程设计报告2010 — 2011学年第二学期课程名称计算机图形学设计题目多边形裁剪算法学生姓名孙晓芳学号**********专业班级计算机科学与技术10升指导教师侯守明2011 年6 月29 日目录目录目录 (I)第1章程序运行环境................................................................................... 错误!未定义书签。

1.1 程序运行环境的简单介绍................................................................. 错误!未定义书签。

1.2 程序运行环境的安装......................................................................... 错误!未定义书签。

1.3 多边形裁剪算法设计的内容........................................................................... 第2章直线裁剪和多边形裁剪的简单比较 (4)2.1 直线裁剪的介绍 (4)2.1.1 直线裁剪的基本原理………………………………………......................................2.1.2 直线裁剪算法的分类以及和窗口交点参数值的计算……………………………..2.2 多边形裁剪介绍 (9)2.2.1 多边形裁剪的基本思想……………………………………………………………..2.2.2 多边形和窗口相交的判定方法…………………………………………..第3章多边形裁剪方法的详细介绍 (12)3.1 Sutherland-Hodgman算法………………………………………………………………….3.2 多边形裁剪算法的流程图 (12)3.3多边形裁剪算法的实现 (13)第4章代码的实现 (14)第5章总结 (21)参考文献 (22)第1章程序的运行环境1.1 程序运行环境的简单介绍本次设计主要是运用了程序设计语言主要以C/C++语言为主，开发平台为Visual C++。

一、实验目标1.了解Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的基本思想；2.掌握Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法的算法实现；二、实验内容本次实验主要是实现Cohen-SutherLand线段裁剪算法、Liang-Barsky线段裁剪算法、SutherLand-Hodgeman多边形裁剪算法。

Cohen-sutherland线段裁剪算法思想：该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。

只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。

对剩余部分，把它作为新的线段看待，又从头开始考虑。

两遍循环之后，就能确定该线段是部分截留下来，还是全部舍弃。

Cohen-sutherland线段裁剪算法步骤：1、分区编码延长裁剪边框将二维平面分成九个区域，每个区域各用一个四位二进制代码标识。

各区代码值如图中所示。

四位二进制代码的编码规则是：(1)第一位置1：区域在左边界外侧(2)第二位置1：区域在右边界外侧(3)第三位置1：区域在下边界外侧(4)第四位置1：区域在上边界外侧裁剪窗口内（包括边界上）的区域，四位二进制代码均为0。

设线段的两个端点为P1（x1，y1）和P2（x2，y2），根据上述规则，可以求出P1和P2所在区域的分区代码C1和C2。

2、判别根据C1和C2的具体值，可以有三种情况：（1）C1=C2＝0，表明两端点全在窗口内，因而整个线段也在窗内，应予保留。

（2）C1&C2≠0（两端点代码按位作逻辑乘不为0），即C1和C2至少有某一位同时为1，表明两端点必定处于某一边界的同一外侧，因而整个线段全在窗外，应予舍弃。

一、实验目的：直线段的裁剪：编码裁剪算法，中点分割裁剪算法。

二、实验内容：//BasicGraph.cpp//请将下列裁剪程序补充完整，并用注释说明是何种裁剪算法void Encode (int x,int y,int *code,int XL,int XR,int YB,int YT) {//请将此程序补充完整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;}//编码裁剪算法：void C_S_Line(POINT &p1,POINT &p2,int XL,int XR,int YB,int YT) {//请将此程序补充完整int x1,x2,y1,y2,x,y,code1,code2,code;x1=p1.x; x2=p2.x; y1=p1.y; y2=p2.y;Encode(x1,y1,&code1,XL,XR,YB,YT);Encode(x2,y2,&code2,XL,XR,YB,YT);while(code1!=0||code2!=0){if((code1&code2)!=0) return;code=code1;if(code1==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;Encode(x,y,&code1,XL,XR,YB,YT);}else{x2=x;y2=y;Encode(x,y,&code2,XL,XR,YB,YT);}}p1.x=x1;p1.y=y1;p2.x=x2;p2.y=y2;}int IsInArea(POINT point,int XL,int XR,int YB,int YT){//请将此程序补充完整if(point.x>=XL && point.x<=XR && point.y>YB && point.y<YT) return 1;else return 0;}int NotIntersect(POINT begin,POINT end,int XL,int XR,int YB,int YT) {//请将此程序补充完整int maxx,maxy,minx,miny;maxx=(begin.x>end.x)?begin.x:end.x;minx=(begin.x<end.x)?begin.x:end.x;maxy=(begin.y>end.y)?begin.y:end.y;miny=(begin.y<end.y)?begin.y:end.y;if(maxx<XL|| minx>XR||maxy<YB||miny>YT) return 1;else return 0;}//中点裁剪算法：POINT ClipMid(POINT begin,POINT end,int XL,int XR,int YB,int YT){//请将此程序补充完整POINT mid,temp;if(IsInArea(begin,XL,XR,YB,YT)) temp=begin;else if(NotIntersect(begin,end,XL,XR,YB,YT)) temp=begin;else{mid.x=(begin.x+end.x)/2;mid.y=(begin.y+end.y)/2;if(abs(mid.x-end.x)<=1&& abs(mid.y-end.y)<=1) temp=mid;else{if(NotIntersect(begin,mid,XL,XR,YB,YT))temp=ClipMid(mid,end,XL,XR,YB,YT);elsetemp=ClipMid(begin,mid,XL,XR,YB,YT);}}return temp;}//Liang-Barsky直线裁剪算法：void ClipParameter(POINT &p1,POINT &p2,int XL,int XR,int YB,int YT) {float u1=0.0,u2=1.0;float dx=p2.x-p1.x,dy=p2.y-p1.y;if(clipTest(-dx,p1.x-XL,&u1,&u2))if(clipTest(dx,XR-p1.x,&u1,&u2))if(clipTest(-dy,p1.y-YB,&u1,&u2))if(clipTest(dy,YT-p1.y,&u1,&u2)){if(u2<1.0){p2.x=p1.x+u2*dx;p2.y=p1.y+u2*dy;}if(u1>0.0){p1.x=p1.x+u1*dx;p1.y=p1.y+u1*dy;}}}int clipTest(float p,float q,float *u1,float *u2){float r;int remainFlag=1;if(p<0.0){r=q/p;if(r>*u2) remainFlag=0;else if(r>*u1) *u1=r;}else if(p>0.0){r=q/p;if(r<*u1) remainFlag=0;else if(r<*u2) *u2=r;}else //*p=0if(q<0.0) remainFlag=0;return remainFlag;}//逐边裁剪算法：//typedef struct tRes { int yes,isIn; POINT pout;} Res;Res TestIntersect(int edge,int type,POINT p1,POINT p2){//判断p2是否在所裁剪的窗边edge的内侧，是否与p1点分别在窗边edge的异侧float dx,dy,m;Res res;int isIn=0,yes=0;POINT pout;dy=p2.y-p1.y;dx=p2.x-p1.x;m=dy/dx;switch(type){case 1: /*right*/if(p2.x<=edge){isIn=1;if(p1.x>edge)yes=1;}else if(p1.x<=edge)yes=1;break;case 2: /*bottom*/if(p2.y>=edge){isIn=1;if(p1.y<edge)yes=1;}else if(p1.y>=edge)yes=1;break;case 3: /*left*/if(p2.x>=edge){isIn=1;if(p1.x<edge)yes=1;}else if(p1.x>=edge)yes=1;break;case 4: /*top*/if(p2.y<=edge){isIn=1;if(p1.y>edge)yes=1;}else if(p1.y<=edge)yes=1;default: break;}if(yes){if((type==1) || (type==3)){ pout.x=edge;pout.y=p1.y+m*(pout.x-p1.x);}if((type==2) || (type==4)){ pout.y=edge;pout.x=p1.x+(pout.y-p1.y)/m;}}res.isIn=isIn;res.yes=yes;res.pout=pout;return res;}int clipSingleEdge(int edge,int type,int nin,POINT pin[50],POINT pout[50])/*对多边形pin与窗边edge进行裁剪，返回裁剪后的多边形pout及点数*/ {int i,k=0;POINT p;Res res;p.x=pin[nin-1].x;p.y=pin[nin-1].y;for(i=0;i<nin;i++){res=TestIntersect(edge,type,p,pin[i]);if(res.yes){ pout[k].x=res.pout.x;pout[k].y=res.pout.y;k++;} if(res.isIn){ pout[k].x=pin[i].x;pout[k].y=pin[i].y;k++;}p.x=pin[i].x;p.y=pin[i].y;}return k;}void ClipEdgePolygon(POINT ps[50],int &n,int XL,int XR,int YB,int YT) { /*对多边形ps进行逐边裁剪*/int n1=0,n2=0;POINT pt[50];n1=clipSingleEdge(XR,1,n,ps,pt);n2=clipSingleEdge(YB,2,n1,pt,ps);n1=clipSingleEdge(XL,3,n2,ps,pt);n2=clipSingleEdge(YT,4,n1,pt,ps);n=n2;}//多边形编码裁剪算法：void ClipEncodePolygon(POINT ps[50],int &n,int XL,int XR,int YB,int YT) {POINT tp[50];int k=0,m;int code1,code2,code;int x,y;for(int i=0;i<n-1;i++){Encode(ps[i].x,ps[i].y,&code1,XL,XR,YB,YT);Encode(ps[i+1].x,ps[i+1].y,&code2,XL,XR,YB,YT);code=code1;m=i;for(int j=0;j<2;j++){if((code1 & code2)!=0) //线段两端都在窗口外的同一侧{switch(code){case 1:x=XL;y=ps[m].y;break;case 2:x=XR;y=ps[m].y;break;case 4:x=ps[m].x;y=YB;break;case 5:x=XL;y=YB;break;case 6:x=XR;y=YB;break;case 8:x=ps[m].x;y=YT;break;case 9:x=XL;y=YT;break;case 10:x=XR;y=YT;break;}tp[k].x=x;tp[k].y=y;k++;}else if((code1 & code2)==0) //线段两端不在窗口的同一侧{if(code==0){tp[k]=ps[m];k++;}else if ((LEFT & code) !=0) //线段与左边界相交 {x=XL;y=ps[i].y+(ps[i+1].y-ps[i].y)*(XL-ps[i].x)/(ps[i+1].x-ps[i].x);if(y>YB && y<YT){tp[k].x=x;tp[k].y=y;k++;}}else if((TOP & code)!=0) //线段与上边界相交{y=YT;x=ps[i].x+(ps[i+1].x-ps[i].x)*(YT-ps[i].y)/(ps[i+1].y-ps[i].y);if(x>XL && x<XR){tp[k].x=x;tp[k].y=y;k++;}}else if((RIGHT & code)!=0) //线段与右边界相交 {x=XR;y=ps[i].y+(ps[i+1].y-ps[i].y)*(XR-ps[i].x)/(ps[i+1].x-ps[i].x);if(y>YB && y<YT){tp[k].x=x;tp[k].y=y;k++;}}else if((BOTTOM & code) != 0) //线段与下边界相交 {y=YB;x=ps[i].x+(ps[i+1].x-ps[i].x)*(YB-ps[i].y)/(ps[i+1].y-ps[i].y);if(x>XL && x<XR){tp[k].x=x;tp[k].y=y;k++;}}}code=code2;m++;}//for(j)}//for(i)for(i=0;i<k;i++)ps[i]=tp[i];n=k;}//函数的调用，裁剪窗口的调整//DrawView.cpp文件//裁剪窗口的调整CDrawView::CDrawView(){/************请在此函数中将裁剪窗口大小调整为长度100单位像素，宽度50单位像素的矩形********/// TODO: add construction code here//m_pWidth=1;m_pStyle=PEN_STYLE_SOLID;m_pColor=RGB(0,0,0);m_FFlag=0;m_FColor=RGB(0,0,0);m_HFlag=0;CurrentDraw=DRAW_VCLINE;m_Num=0;m_Drag=0;m_HCursor=AfxGetApp()->LoadStandardCursor(IDC_CROSS);//DrawType=0;ClipFlag=0;ClipType=-1;XL=200;XR=300;YB=150;YT=200;//XL=200;XR=500;YB=150;YT=400;ClipWindowColor=RGB(192,192,50);}void CDrawView::OnDraw(CDC* pDC){CDrawDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);// TODO: add draw code for native data hereif(ClipFlag){CPen NewPen,*pOldPen;NewPen.CreatePen(PS_DASH,1,ClipWindowColor);pOldPen=pDC->SelectObject(&NewPen);pDC->MoveTo(XL,YB);pDC->LineTo(XR,YB);pDC->LineTo(XR,YT);pDC->LineTo(XL,YT);pDC->LineTo(XL,YB);}int index;index=pDoc->GetShapeNumber();for(int i=0;i<index;i++)pDoc->GetShape(i)->Drawing(pDC);}void CDrawView::OnInitialUpdate(){CSize sizeTotal;sizeTotal.cx = 640; sizeTotal.cy = 480;SetScrollSizes(MM_TEXT, sizeTotal);// TODO: Add your specialized code here and/or call the base class }void CDrawView::OnLButtonDown(UINT nFlags, CPoint point){// TODO: Add your message handler code here and/or call defaultCClientDC dc(this);OnPrepareDC(&dc);dc.DPtoLP(&point);m_pPrev=point;m_pOrigin=point; //点击鼠标左键作为拖动绘图的第一点m_Drag=1;SetCapture();RECT rect;GetClientRect(&rect);ClientToScreen(&rect);ClipCursor(&rect);CScrollView::OnLButtonDown(nFlags, point);}//函数调用处void CDrawView::OnLButtonUp(UINT nFlags, CPoint point){// TODO: Add your message handler code here and/or call defaultif(m_Drag){m_Drag=0;ReleaseCapture();ClipCursor(NULL);CDrawDoc *pDoc=GetDocument();CShape *pShape;POINT p1,p2;if(CurrentDraw==DRAW_VCLINE || CurrentDraw==DRAW_DDALINE ||CurrentDraw==DRAW_MIDLINE || CurrentDraw==DRAW_BSHLINE){if(ClipFlag){switch(ClipType){/****************编码裁剪函数调用处*************/case CLIP_ENCODE:C_S_Line(m_pOrigin,m_pPrev,XL,XR,YB,YT); break; /****************中点分割裁剪函数调用处************/case CLIP_MIDPOINT: ClipMid(m_pPrev,m_pOrigin,XL,XR,YB,YT);p1=ClipMid(m_pPrev,m_pOrigin,XL,XR,YB,YT);p2=ClipMid(m_pOrigin,m_pPrev,XL,XR,YB,YT);m_pOrigin=p1;m_pPrev=p2;break;case CLIP_PARAMETER:ClipParameter(m_pOrigin,m_pPrev,XL,XR,YB,YT);break;}}pShape=newCLine(m_pOrigin,m_pPrev,m_pWidth,m_pStyle,m_pColor,DrawType);pDoc->AddShape(pShape);}if(CurrentDraw==DRAW_RECTANGLE){if(ClipType==CLIP_WINDOW){XL=m_pOrigin.x;XR=m_pPrev.x;YB=m_pOrigin.y;YT=m_pPrev.y;}else{pShape=newCRectangle(m_pOrigin,m_pPrev,m_pWidth,m_pStyle,m_pColor,m_FFlag,m_FColor,m_HFlag,m_Hatch);pDoc->AddShape(pShape);}}if( CurrentDraw==DRAW_VCCIRCLE || CurrentDraw==DRAW_MIDCIRCLE || CurrentDraw==DRAW_BSHCIRCLE){pShape=newCCircle(m_pOrigin,m_pPrev,m_pWidth,m_pStyle,m_pColor,m_FFlag,m_FColor,m_HFlag,m_Hatch,DrawType);pDoc->AddShape(pShape);}if(CurrentDraw==DRAW_VCELLIPSE || CurrentDraw==DRAW_MIDELLIPSE) {pShape=newCEllipse(m_pOrigin,m_pPrev,m_pWidth,m_pStyle,m_pColor,m_FFlag,m_FColor,m_HFlag,m_Hatch,DrawType);pDoc->AddShape(pShape);}pDoc->UpdateAllViews(NULL);}CScrollView::OnLButtonUp(nFlags, point);}三实验结果：四、实验总结通过这次试验使我了解到如何运用计算机程序对窗口进行剪裁，了解到编码剪裁算法直观方便，速度较快，中点分割剪裁算法不用进行乘除运算，剪裁效率高,Liang-Barsky直线裁剪算法更快。

多边形裁剪算法多边形裁剪算法多边形裁剪是用线段对一些形状进行处理的一种常见算法。

它通常用于地图显示、机械加工以及其他基于图形的计算机图形系统中。

裁剪有一个边界框，其中包含可被裁剪的部分，以及无法被裁剪的区域。

多边形裁剪指的是在边界框内裁剪掉不符合要求的部分，只保留符合边界框的多边形。

下面将介绍一种基本的多边形裁剪算法——贝尔格罗夫多边形裁剪算法。

贝尔格罗夫多边形裁剪算法(Brelgorff Polygon Clipping Algorithm)是一种用于生成裁剪多边形轮廓的算法，由荷兰科学家Berlgorff于1890年发明。

它主要用于多边形裁剪。

贝尔格罗夫多边形裁剪算法的思想是：从一个多边形的起点，每次移动到下一个顶点，v，判断是否在裁剪区域内，若在裁剪区域内，则标记当前顶点v为可视边界，否则为不可视边界；然后，从v移动到下一个顶点，只要发现在裁剪区域外的边界，就必须标记下一个顶点为可视边界；最后，当发现多边形完全不在裁剪区域内时，就会将多边形的所有顶点都标记为不可视边界。

贝尔格罗夫多边形裁剪算法的实现方式如下：第一步：设置多边形的顶点序列。

第二步：从多边形的起点开始遍历顶点，检查每个顶点是否在裁剪区域内，将在裁剪区域内的顶点标记为可视边界，将在裁剪区域外的顶点标记为不可视边界。

第三步：对不可视边界进行处理，若两个不可视边界之间有一个可视边界，则以可视边界为结束位置，将不可视边界之间的边加入到多边形的边界框中；若两个不可视边界之间没有可视边界，则以最后一个不可视边界为结束位置，将不可视边界之间的边加入到多边形的边界框中。

第四步：对可视边界进行处理，遍历可视边界，将可视边界添加到多边形的边界框中。

第五步：根据多边形的边界框计算出裁剪后的多边形轮廓，即裁剪后的多边形。

贝尔格罗夫多边形裁剪算法具有以下特点：实现简单，复杂度较低，多边形裁剪时不要求多边形的顶点按边界框顺序排列，且可以处理任意多边形。

贝尔格罗夫多边形裁剪算法是一种常用的多边形裁剪算法，它对图形的显示、机械加工以及其他基于图形的计算机图形系统有着重要的应用。

多边形裁剪的Sutherland—Hodgman算法1>. Sutherland—Hodgman多边形裁剪算法思想该算法的基本思想是每次用窗口的一条边界及其延长线来裁剪多边形的各边。

多边形通常由它的顶点序列来表示，经过裁剪规则针对某条边界裁剪后，结果形成新的顶点序列，又留待下条边界进行裁剪，…，直到窗口的所有边界都裁剪完毕，算法形成最后的顶点序列，才是结果多边形（它可能构成一个或多个多边形）。

当多边形一个顶点Pi相对于窗口某条边界及其延长线进行剪裁时，不外乎下列四种情况（即裁剪规则）：1、顶点Pi在内侧，前一顶点Pi-1也在内侧，则将Pi纳入新的顶点序列；2、顶点Pi在内侧，前一顶点Pi-1在外侧，则先求交点Q，再将Q、Pi依次纳入新的顶点序列；3、顶点Pi在外侧，前一顶点Pi-1在内侧，则先求交点Q，再将Q纳入新的顶点序列；4、顶点Pi与前一顶点Pi-1均在外侧，则顶点序列中不增加新的顶点。

2>. Sutherland—Hodgman多边形裁剪算法步骤考虑多边形相对于一条边界及其延长线进行裁剪的算法：1．从主函数得到待裁剪多边形的顶点序列P[][2]、顶点序列数n、窗口一条边界参数xl（假如为矩形窗口的左边界）；2．赋初值：将顶点序列中的最后一个顶点赋给前一顶点S；设置初始标志flag：if(S在边界内侧)flag=0;else flag=1；设新的顶点序列数j=0；3．对多边形各顶点进行裁剪规则处理，结果放入新的多边形顶点序列Q[][2]中：for(对第一个顶点直到最后一个顶点，逐一处理）{if(Pi在边界内侧){if(flag!=0){flag=0;求交点并放入新的多边形顶点序列Qj中；j++；}将当前顶点放入新的多边形顶点序列Qj中：Qj=Pi；j++；}else{if(flag==0){flag=1;求交点并放入新的多边形顶点序列Qj中；j++；}}将当前顶点赋给S：S=Pi；}4．做返回准备：将新的多边形顶点序列Q又逐一放回原多边形顶点序列P中：P=Q；将新的多边形顶点数j放回原多边形顶点数n中：n=j；///////////////////////////////////////////////////////////////////// ///////////////////-----多边形裁剪的Sutherland—Hodgman算法---------/////////////////////////////////////////////////////////////////////// ////////////////void CMyClip_AView::ClipedgeL(CPoint polypoint[], CPoint clipwindow[], UINT polynum)/*其中参数polypoint[]为多边形顶点,clipwindow[]为裁剪窗口顶点,polynum 为多边形顶点数目*/{//找出裁剪窗口边界long xl,xr,yt,yb;UINT i;xl=clipwindow[0].x;xr=clipwindow[0].x;yt=clipwindow[0].y;yb=clipwindow[0].y;for(i=1;i<=4;i++){if(xl>clipwindow[i].x)xl=clipwindow[i].x;if(xr<clipwindow[i].x)xr=clipwindow[i].x;if(yb>clipwindow[i].y)yb=clipwindow[i].y;if(yt<clipwindow[i].y)yt=clipwindow[i].y;}//CPoint B[Polygon_Num],C[Polygon_Num];UINT m_nA,m_nB;int x,y;long tem1,tem2;m_nA=polynum;/*记载原始多边形顶点顶点个数*/m_nB=0;/*记载新生成多边形顶点顶点个数*/for(i=0;i<m_nA;i++){if(polypoint[i].x<xl && polypoint[i+1].x<xl) /*判断的多边形边两个端点都在外部，不做处理*/{continue;/*如果是这种情况，那么就对继续对下一条多边形边作判断，也就是说下面的判断不用做了*/}if(polypoint[i].x>=xl && polypoint[i+1].x>=xl) /*边两个端点都在内部，保留*//*因为每个保留的点在数组中只出现一次，且下一次判断时第二个端点一定会要取到，因此只保留的两个点中的第一个*/{B[m_nB].x =polypoint[i].x ;B[m_nB].y =polypoint[i].y ;m_nB=m_nB+1;continue;}if(polypoint[i].x<xl && polypoint[i+1].x>=xl)/*边两个端点起点在外部，终点在内部，求交点，然后交点，终点都应该送入临时数组*/{/*保留交点*/x=xl;tem1=(xl-polypoint[i].x);//tem2=(xl-x1)*dy/dx+y1;//y/x=dy/dx---->y=x*dy/dxtem2=tem1*(polypoint[i+1].y-polypoint[i].y)/(polypoint[i+1].x-polypoint[i].x)+polypoi nt[i].y;y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB=m_nB+1;continue;}if(polypoint[i].x>=xl && polypoint[i+1].x<xl)/*起点在内部，终点在外，求交点，然后起点，交点送入临时数组*/{ /*保留内部点*/B[m_nB].x =polypoint[i].x ;B[m_nB].y =polypoint[i].y ;m_nB=m_nB+1;/*保留交点*/tem1=(xl-polypoint[i].x);tem2=tem1*(polypoint[i+1].y-polypoint[i].y)/(polypoint[i+1].x-polypoint[i].x)+polypoi nt[i].y;y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB=m_nB+1;continue;}}//把第一个点的数据拷贝到最后//形成裁剪后的多边形if(i==m_nA){B[m_nB]=B[0];}//下------------------m_nA=0;for(i=0;i<m_nB;i++){if(B[i].y<yb && B[i+1].y<yb)//两个点全在下方{continue;//下一条边}if(B[i].y>=yb && B[i+1].y>=yb)//p1,p2都在yb上方{C[m_nA].x =B[i].x;C[m_nA].y =B[i].y;m_nA++;continue;}if(B[i].y<yb && B[i+1].y>=yb)//p1在下，P2在上,留交点，外－＞内{y=yb;tem1=yb-B[i].y;//tem2=x1+(yb-y1)*dx/dytem2=tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y) + B[i].x;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}if(B[i].y>=yb && B[i+1].y<yb)//p1在上方，P2在下方，留P1和交点,内－外{//save p1C[m_nA].x=B[i].x;C[m_nA].y=B[i].y;m_nA++;//留交点y=yb;tem1=yb-B[i].y;//tem2=x1+(yb-y1)*dx/dytem2=tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y)+B[i].x;x=tem2;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}}//形成第二次裁剪多边形if(i==m_nB){C[m_nA]=C[0];}//右------------------m_nB=0;for(i=0;i<m_nA;i++){if(C[i].x>xr && C[i+1].x>xr)//P1，P2都在右方--go next{continue;}if(C[i].x<=xr && C[i+1].x<=xr)//P1，P2都在左方，留P1{B[m_nB].x =C[i].x;B[m_nB].y =C[i].y;m_nB++;continue;}if(C[i].x>xr && C[i+1].x<=xr)//P1在右方，P2在左方，留交点{x=xr;tem1=C[i].x-xr;tem2=C[i].y-tem1*(C[i+1].y-C[i].y)/(C[i+1].x-C[i].x);y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB++;continue;}if(C[i].x<=xr && C[i+1].x>xr)//P1在内，P2在外，留P1和交点{//save p1B[m_nB].x =C[i].x;B[m_nB].y =C[i].y;m_nB++;//save 交点x=xr;tem1=C[i].x-xr;tem2=C[i].y-tem1*(C[i+1].y-C[i].y)/(C[i+1].x-C[i].x);y=tem2;B[m_nB].x =x;B[m_nB].y =y;m_nB++;continue;}}//三次裁剪后的新多边形if(i==m_nA){B[m_nB]=B[0];}//上-------------------m_nA=0;for(i=0;i<m_nB;i++){if(B[i].y>yt && B[i+1].y>yt)//p1,p2都在上方,next{continue;}if(B[i].y<=yt && B[i+1].y<=yt)//p1,p2都在下方,留P1{C[m_nA].x =B[i].x;C[m_nA].y =B[i].y;m_nA++;continue;}if(B[i].y>yt && B[i+1].y<=yt)//P1在上方，P2在下方外－＞内,留交点{y=yt;tem1=B[i].y-yt;//tem2=x1+(yb-y1)*dx/dytem2=B[i].x-tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y);x=tem2;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}if(B[i].y<=yt && B[i+1].y>yt)//P1在下方，P2在上方，内－＞外，留P1和交点{//save p1,,,C[m_nA].x =B[i].x;C[m_nA].y =B[i].y;m_nA++;//save 交点y=yt;tem1=B[i].y-yt;//tem2=x1+(yb-y1)*dx/dytem2=B[i].x-tem1*(B[i+1].x-B[i].x)/(B[i+1].y-B[i].y);x=tem2;C[m_nA].x =x;C[m_nA].y =y;m_nA++;continue;}}//形成裁剪后的多边形if(i==m_nB){C[m_nA]=C[0];}CClientDC dc(this);CPen tempen;tempen.CreatePen(PS_SOLID,1,RGB(255,0,0));dc.SelectObject(tempen);dc.MoveTo(C[0]);for(i=1;i<=m_nA;i++){dc.LineTo(C[i]);}}//.....。

一个有效的多边形裁剪算法摘要:多边形多裁剪与线剪裁相比具有更广泛的实用意义,因此它是目前裁剪研究的主要课题.提出了一个多边形裁剪多边形的有效算法.其中的多边形都可以是一般多边形,既可以是凹多边形,也可以是有内孔的多边形.该算法不仅可以求多边形的“交”(多边形裁剪),而且可以求多边形的“并”和“差”.它是以所提出的一系列新方法和新技术为基础而形成的.首先,该算法使用单线性链表数据结构,与其他使用双链表或树结构的算法相比,具有占用空间少及处理速度快的特点;其次,找到了两个多边形之间进、出点之间的关系.再通过合理的数据结构处理,减少了算法对多边形链表的遍历次数,而且允许多边形既可以按顺时针方向也可以按逆时针方向输入.最后,判断和计算交点是裁剪算法的主要工作.提出了一个具有最少计算量的交点判断和计算方法,进一步加快了算法的运行速度.与其他同类算法进行了比较,结果表明,新算法具有最简单的结构和最快的执行速度.正文:1.基本概念与定义.为了便于下面对算法的讲解,本节首先介绍有关多边形裁剪的一些基本概念及术语.(1) 多边形的边的方向与内外区域的关系.如果多边形的边的方向是顺时针的(即多边形的顶点是以顺时针的顺序输入的),则在沿着多边形的边走时,右侧区域为多边形的内部;相反,如果多边形的边的方向是逆时针的,则在沿着多边形的边走时,左侧区域为多边形的内部.对于具有孔洞的多边形,只要把内孔边界和外边界以相反的方向表示,由上面的规则判断多边形的内部仍然适用.(2) 进点和出点的定义.设I是多边形S和C的一个交点,如果S沿着S的边界的方向在I点从C的外部进入C的内部,则称I为对于C的一个进点.反之,如果S在I点从C的内部出到C的外部,则称I为对于C的一个出点.例如,对于如图1所示的多边形C和S及其交点I,若S的方向为逆时针方向S 1→S2→S3→S4→S5,则I5I1I3是对于C的进点,I4I2I6是对于C的出点.如果S的方向为顺时针方向S5→S4→S3→S2→S1,则对于C来说,I2I4I6是进点,I1I5I3是出点(3) 进点和出点的判定.假设多边形S的一条边Si Si+1与另一多边形C有交点.当点Si是C的外点时,则沿着S的走向,边Si Si+1与C的第一个交点I必是C的进点;而当Si是C的内点时,I必是C的出点.由于沿着S的边界对于C的进点和出点是交替出现的(两多边形的边重合或者两多边形在顶点处相交的情况除外.这类特殊情况的处理将在第5节进行讨论),所以,只需判断第1个交点是进点还是出点,其他交点的进出性则可依次确定.对于一个多边形裁剪另一个多边形的过程,就是求两个多边形的相交区域(我们称其为结果多边形或输出多边形).结果多边形是由实体多边形位于裁剪多边形内的边界和裁剪多边形位于实体多边形内的边界组成的.2.新算法的数据结构多边形裁剪算法需要一个适当的数据结构来存储多边形及交点,并能够在其上进行正确的操作.在Weiler的算法中,输入多边形组成一个树形结构.Greiner-Hormann算法采用双向链表的结构,每个多边形由一个双向链表来表示.每找到一个交点,就将其分别插入到实体多边形和裁剪多边形的两个双向链表中.Greiner-Hormann算法使用了线性链表,与Weiler算法的树形结构相比降低了数据结构的复杂性.本文的算法采用单链表来表示所有的多边形(输入和输出),与Greiner-Hormann算法的双向链表结构相比,不仅由于少用了一个指针域而节省了存储空间,而且还进一步降低了数据结构的复杂性.我们知道,在插入一个交点时,双向链表所需修改的指针数是单链表的2倍,因此,对单链表的操作不仅简单,而且也省时.新算法的每个多边形由一个单链表来表示,单链表的每一个结点按序(多边形顶点输入的顺序)存储着多边形的一个顶点.最后一个结点的指针指向第1个结点(循环单链表).每个链表由一个头指针指向其第1个结点,实体多边形链表的第1个结点由头指针HeadS指示;裁剪多边形链表的第一个结点由头指针HeadC指示.结点的结构定义如下(其中coordinates表示坐标类型,用于存储顶点或交点的坐标值;pointer表示指针类型):Vertex={x, y: coordinates;inters, used: Boolean;next: pointer;}交点的数据结构如下:Intersection={x, y: coordinates;inters, used: Boolean;next1, next2: pointer;}其中的指针域用于将交点分别插入到两个多边形的单链表中,第1指针域next1用于插入实体多边形链表;第2个指针域next2用于插入裁剪多边形链表.这样的数据结构定义使算法在求出一个交点时只需建立1个Intersection(交点)类型的结点,并分别插入到两个多边形的单链表中,而不像Greiner-Hormann算法那样,要建立两个交点类型的结点,然后将每一个插入到一个多边形的链表中,而插入到两个链表中的这两个交点类型的结点之间也要用指针域neighbor彼此相连.应该注意的是,实体多边形链表中的交点的进出性是对裁剪多边形而言的,而裁剪多边形链表中的交点的进出性则是对实体多边形而言的.在这两个数据结构的定义中,布尔类型域inters用于区分该结点是否Intersection(交点)类型的结点;used域用于有多个输出多边形时.所有交点的used域的初值都为0,当一个交点被输出时,其used域被置为1.裁剪结果可能得到多个分立的输出多边形,因此需要设立一个指针链表Out,其每个结点有一个指针域polygon指向一个输出多边形链表的第一个结点.该指针链表的结点结构如下:Out={polygon: pointer;next: pointer;}图2给出了对图1的多边形进行裁剪时,Greiner-Hormann算法和新算法所使用的数据结构.可见,新算法的数据结构要比Greiner-Hormann算法简单得多.3.新算法新算法分为3个阶段.第1个阶段,判断及计算第1个交点,并由其进出性判断两个多边形是否同向.如果不同向,则将裁剪多边形链表反向,然后将该交点插入到两个多边形的链表中.第2阶段,依次以实体多边形的每一个边对裁剪多边形进行直线裁剪操作,判断及计算其余交点,并以正确的顺序插入到两个多边形的链表中.第3阶段,遍历整个链表,输出最终结果.我们以下面的引理开始算法第1阶段的描述.引理1. 如果两个相交多边形的边的取向相同(均为顺时针或逆时针方向),则对一个多边形是进点的交点对另一个多边形必是出点.证明:设分别属于两个相交多边形S和C的两个相交边为Se 和Ce,我们首先考虑两个相交多边形的边的取从下向上穿过S(图3a的情况)),则由图3显然可见,C经过交点从多边形S内走向S外,即该交点是对于多边形S的出点;而另一方面,边S向均为顺时针方向的情况.在这种情况下,多边形边的右侧为多边形内侧(在图3中由阴影表示).考虑两边之间的夹角,由于此夹角是由两边的相对位置决定的,所以我们可以将一个边的方向固定而讨论另一个边方向变化的各种情况.在图3中,设Se 边的方向是从左向右固定不变的,如果Ce的正向与Se的正向的夹角在0o~180o之间(即Ceeee则是经过该交点从多边形C外走向C内,即该交点是对于多边形C的进点如果Ce 的正向与Se的正向的夹角在180o~360o之间(即Ce从上向下穿过Se(如图3(b)所示),则由图显然可见,该交点对于多边形S是进点,而对于多边形C则是出点.这就是我们要证明的结论.对于两个相交多边形的边的取向均为逆时针方向的情况,可用相同的方法证明该引理. □根据该引理,对其中一个多边形求出一个进点或出点以后,在两个多边形方向相同的情况下,其对另一个多边形的进出性也就确定了.这样,如果两个多边形的方向相同,则在求出交点时只需判断和标记它对其中一个多边形是进点还是出点.它对另一个多边形的进出性则相反.而由第1节的讨论可知,由于沿着一个多边形的边界,在其上的进点和出点是交替出现的.所以只需标记第1个交点是进点还是出点,其他交点的进出性则可依次确定.最终我们得出一个结论:如果两个多边形的方向相同,则要标记所有交点对于两个多边形的进出性,只需标记任何一个多边形链表中的第1个交点的进出性即可(在后面的算法描述中,我们用变量Sin来标记实体多边形链表中的第1个交点对于裁剪多边形是否为进点).因此,新算法的第1步就要是判断两个多边形是否同向.如果不同向,则将裁剪多边形链表反向,使两个多边形的方向相同.判断两个多边形是否同向,是通过判断一个交点(如第1个交点)对于两个多边形的进出性来完成的.如果该点对于实体多边形的进出性与对于裁剪多边形的进出性不同,则可知两个多边形取向相同;否则,两个多边形的取向相反.新算法将交点的计算与进出性判断合成一步进行.当一个多边形的一个边对另一个多边形进行直线裁剪操作之后,如果有交点,即可根据交点在这个边上的排序的奇偶性来确定交点对另一个多边形的进出性.这样在计算交点的同时也确定了该交点的进出性.详细的描述见第4节.下面是算法的第1部分的形式描述,其中指针变量PS和PC分别指向实体多边形链表和裁剪多边形链表中正在被处理的当前结点.另外,我们把由结点PS↑和其下一个结点PS↑.next↑定义的边简称为由PS指向的边.PS=HeadS;Repeat以PS指向的边与裁剪多边形进行直线裁剪操作(即求交点的操作,见第4节);if (上述直线裁剪操作有交点) then{如图2所示,将每个交点(可能有多个)按其在该边上的顺序插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间;由Sin标记插入到实体多边形链表中的第1个交点对于裁剪多边形的进出性,Sin=1表示进;令PF指向第1个交点结点,以备算法的第3阶段使用;将PC指向该交点在裁剪多边形上的对应边;以PC指向的边与实体多边形进行直线裁剪操作;求出上述第1个交点对于实体多边形的进出性;if上述第1个交点对于实体多边形和裁剪多边形的进出性相同 then 逆转裁剪多边形的链表;令PS指向实体多边形的下一个边;转到算法的第2阶段;}令PS指向实体多边形的下一个边;until PS=HeadS;两个多边形无交点,算法结束;在第2阶段,算法从第1阶段求出交点的那个实体多边形边的下一个边开始,用每一个实体多边形边与裁剪多边形求交点,并如图2所示,给每个交点建立一个包含该交点坐标的新的交点结点,然后将其插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间.例如,一个交点是由结点PS↑和其下一个结点PS↑.next↑所定义的实体多边形的边与由结点PC↑和其下一个结点PC↑.next↑所定义的裁剪多边形的边相交形成的,那么该交点结点就应该被插入到实体多边形链表的结点PS↑和其下一个结点PS↑.next↑之间,同时被插入到裁剪多边形链表的结点PC↑和其下一个结点PC↑.next↑之间.当一个边上有多个交点时,则以该边的方向为序将这些交点插入其中.例如,如果该边的方向是从左向右的斜线,则可按交点的x坐标的大小顺序插入这些交点.在这个阶段,算法不需要标记交点的进出性,因为如前所述,算法只需在第1阶段用变量Sin来标记实体多边形链表中的第1个交点对于裁剪多边形的进出性,其余交点对于两个多边形的进出性便由如前所述的规律可知.下面是算法的第2部分的形式描述.Repeat以PS指向的边与裁剪多边形进行直线裁剪操作;if (上述直线裁剪操作有交点) then 将每个交点按其在该边上的顺序插入到实体多边形链表和裁剪多边形链表的对应相交边的两个结点之间;令PS指向实体多边形的下一个边;until PS=HeadS;转到算法的第3阶段;在算法的第3阶段,通过遍历已插入交点结点的实体多边形和裁剪多边形链表来跟踪结果多边形的边界,最后产生输出多边形链表.跟踪一个结果多边形的边界是以实体多边形链表中的一个进点(对于裁剪多边形)开始的.从该进点到实体多边形链表中的下一个交点(记为N1)之间的实体多边形的边界全部是结果多边形的边界.N1既是对于裁剪多边形的出点也是对于实体多边形的进点,因此从N1点开始到裁剪多边形链表中的下一个交点之间的裁剪多边形的边界全部是结果多边形的边界(如图1所示).输出这些边界.重复此过程,一直到回到实体多边形链表中的开始进点为止,便跟踪输出了一个结果多边形.在上述过程中,实体多边形链表中的进点(对于裁剪多边形)的used域被标记为1,以表明从它开始的边界已经被输出过.“used域”用于有多个结果多边形的情况.算法第3阶段的遍历是以实体多边形链表的顺序进行的.从实体多边形链表中的第1个进点开始,如果该进点(当前进点)的used域为0(表明它未被输出过),则将其置为1,并执行上一段所述的跟踪过程输出一个结果多边形;如果该进点的used域为1,则走到实体多边形链表的下一个进点,即该进点的下一个交点的下一个交点(如前所述,在多边形链表中交点的进出性是相隔分布的).以下一个进点为当前进点,重复此过程,一直到回到实体多边形链表中的第1个进点为止.所有的进点都被访问过,所有的结果多边形也都被输出.至此,算法结束.下面是算法第3阶段的形式描述.if Sin=0 then 令PF指向实体多边形链表中的下一个交点结点,以确保PF指向第1个进点;PP=PF;repeatif PP所指的交点结点的used域为0 then{PO=PP;建立一个新的输出多边形链表,并将指向该链表的头指针加入到指针链表Out的最后(在polygon域当中);repeat将PO所指的交点结点(一定是进点)的used域置为1;将从PO所指的交点结点开始(用next1指针域)到下一个交点结点(记为N1)之前的实体多边形链表中的结点加入到输出多边形链表的最后,并使PO指向N1;将从PO所指的交点结点开始(用next2指针域)到下一个交点结点(记为N2)之前的裁剪多边形链表中的结点加入到输出多边形链表的最后,并使PO指向N2;until PO=PP}else 使PP指向实体多边形链表中的下一个进点结点(即下一个交点结点的下一个交点结点);until PP=PF;算法结束,输出多边形链表由指针链表Out的polygon域指出.该算法不仅可以求多边形的“交”(多边形裁剪),而且稍加修改就可以求多边形的“并”和“差”.只要输出多边形从出点到入点的边(而不是上述的从入点到出点)即可得到多边形的“并”.要得到多边形的“差”也很简单,只需使两个多边形一个顺时针取向,另一个逆时针取向即可.对于有内孔的多边形,只要把内孔边界和外边界以相反的方向表示,则第1节的多边形的边的方向与内外区域的关系仍然适用.此时,只判断实体多边形和裁剪多边形的外边界方向即可:若方向相同,则不必调整;若方向相反,则把裁剪多边形的链表反向.然后,分别求出实体多边形的内、外边界与裁剪多边形的内、外边界的交点,并把交点插入到相应的数据结构中.最后遍历所有交点求出输出结果多边形.为了使算法能够裁剪有内孔的多边形,只需对上述算法进行少量的修改.用一个链表来表示有内孔的多边形时会多出一条边,如图4中的边C1C9.为了避免出现这种情况,我们采用如下的方法:将多边形链表的第1个结点换成上述交点结点的结构,即具有两个指针域next1和next2.其中next1用于指向多边形的外边界的第2个结点,而next2用于指向多边形的内边界的第1个结点.内边界的第1个结点同样具有两个指针域next1和next2,如果有第2个内孔,则由next2指向;如果没有,其next2指针域为空.这样,对多边形链表(可能包括多个边界链表)遍历的结束条件就不是回到链表的第1个结点了,而是回到其next2指针域为空的第1个结点.在算法中,每个边界的第1个结点都设一个头指针Head指向,自然区别于其他结点。

SutherlandHodgman多边形裁剪算法Sutherland-Hodgman多边形裁剪算法是一种用于裁剪二维多边形的算法，它是由伊恩·萨瑟兰（Ian Sutherland）和威廉·霍德曼（William E. Hodgman）在1962年提出的。

这种算法基于线段裁剪的思想，通过迭代过程逐步减少多边形的顶点数量，直到多边形完全被裁剪为止。

一、算法步骤1.初始化：将待裁剪的多边形P和裁剪多边形Q的边界表示为一系列的顶点。

设P的顶点集合为{p0, p1, , pn}，Q的顶点集合为{q0, q1, , qm}。

2.排序：将P的所有顶点按照逆时针（或顺时针）的顺序排列，将Q的所有顶点也按照逆时针（或顺时针）的顺序排列。

3.初始化裁剪结果：将裁剪结果设为一个空的多边形R。

4.迭代过程：从i=0开始，依次进行以下步骤，直到i=n或j=m：a. 确定P的第i个顶点pi是否在Q的边界内部（即判断pi是否在Q的凸壳上）。

如果pi不在Q的边界内部，则直接将pi添加到裁剪结果R中。

b. 如果pi在Q的边界内部，则找到Q边界上与pi最近的两个点，记为qi1和qi2。

根据这两个点的位置，将P的第i个顶点pi分割成两个部分，分别位于qi1和qi2之间的线段以及线段外的部分。

将这两个部分分别添加到R中。

c. 将i增加1，如果i<n，跳转到步骤4.4开始下一轮迭代；否则结束迭代。

5.返回结果：将R作为裁剪结果输出。

二、算法复杂度Sutherland-Hodgman多边形裁剪算法的时间复杂度为O(n+m)，其中n和m分别为待裁剪多边形P和裁剪多边形Q的顶点数量。

这是因为每次迭代过程中，我们最多只处理n个P的顶点和m个Q的顶点。

空间复杂度为O(n+m)，因为我们需要存储P和Q的顶点以及裁剪结果R的多边形表示。

三、算法应用Sutherland-Hodgman多边形裁剪算法可以用于各种需要裁剪二维多边形的场景，如计算机图形学中的视口裁剪、图像处理中的形状裁剪等。

图形学中的多边形裁剪与扫描线算法一、多边形裁剪与扫描线算法多边形裁剪和扫描算法是计算机图形学中常用的技术，用于处理在屏幕上显示的多边形的裁剪和填充。

裁剪是指将多边形中超出指定区域的部分去除，而扫描算法则是用来填充多边形的内部区域。

这两种算法通常结合使用，以实现对图形的精确裁剪和填充。

二、裁剪算法1. Cohen-Sutherland算法Cohen-Sutherland算法是一种常用的线段裁剪算法，它将平面分成九个部分，并用四位编码来表示线段的位置关系。

当线段与裁剪区域相交时，根据编码判断线段的起点和终点位置，然后将线段裁剪到裁剪区域内。

这样就可以快速有效地进行线段裁剪。

2. Sutherland-Hodgman算法Sutherland-Hodgman算法是用来对多边形进行裁剪的算法，它通过对多边形的每条边进行裁剪，最终得到裁剪后的多边形。

该算法的优势在于可以处理凸多边形和凹多边形，并且可以处理不规则的裁剪区域。

三、扫描线填充算法1.扫描线填充算法的原理扫描线填充算法是一种经典的多边形填充算法，其基本原理是从上到下逐行扫描屏幕，并根据扫描线与多边形边界的交点来确定每个像素点的颜色。

通过这种方法，可以有效地填充多边形的内部区域，并且可以处理复杂的多边形。

2.扫描线算法的实现步骤扫描线填充算法的实现步骤包括扫描线的生成、边界与扫描线的交点计算、交点排序、填充颜色等过程。

在每一行扫描时，通过计算扫描线与多边形的交点，然后对这些交点进行排序，最后通过填充算法来填充多边形的内部。

四、多边形裁剪与扫描算法的应用多边形裁剪与扫描算法在计算机图形学中有着广泛的应用。

例如，在计算机辅助设计(CAD)领域，这些算法被用于对图形进行裁剪和填充，以实现图形的精确显示和编辑。

另外，在计算机游戏开发中，多边形裁剪与扫描算法也被用于实现场景的渲染和光照效果。

五、总结多边形裁剪与扫描算法是计算机图形学中重要的技朧，通过裁剪算法可以实现对图形的剪切和编辑，而扫描算法则可以实现对图形的填充和显示。

裁剪算法详解在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。

因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。

这个选择过程称为裁剪。

最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。

但那样太费时，一般不可取。

这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。

所以一般采用先裁剪再扫描转换的方法。

(a)裁剪前(b) 裁剪后图1.1 多边形裁剪1直线段裁剪直线段裁剪算法比较简单，但非常重要，是复杂图元裁剪的基础。

因为复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。

常用的线段裁剪方法有三种：Cohen-Sutherland,中点分割算法和梁友栋－barskey算法。

1.1 Cohen-Sutherland裁剪该算法的思想是：对于每条线段P1P2分为三种情况处理。

（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。

（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。

（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。

其中一段完全在窗口外，可弃之。

然后对另一段重复上述处理。

为使计算机能够快速判断一条直线段与窗口属何种关系，采用如下编码方法。

延长窗口的边，将二维平面分成九个区域。

每个区域赋予4位编码CtCbCrCl.其中各位编码的定义如下：图1.2 多边形裁剪区域编码图5.3线段裁剪裁剪一条线段时，先求出P1P2所在的区号code1,code2。

若code1=0,且code2=0，则线段P1P2在窗口内，应取之。

若按位与运算code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。

可判断线段完全在窗口外，可弃之。

否则，按第三种情况处理。

求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。

多边形分割算法一、引言多边形分割算法是计算机图形学中的一个重要问题。

在实际应用中，多边形分割算法被广泛应用于计算机游戏、建筑设计、CAD等领域。

本文将介绍多边形分割的基本概念和常见算法。

二、多边形分割基本概念1. 多边形多边形是由若干个线段组成的封闭图形。

每条线段称为多边形的一条边，相邻两条边之间的夹角称为内角。

多边形可以分为凸多边形和凹多边形两种。

2. 多边形分割将一个凸或凹多边形划分成若干个不相交的子多边形，使得每个子多边形都是凸多边形，这个过程就称为多边形分割。

3. 三角剖分三角剖分是指将一个复杂的凸或凹多边形划分成若干个三角形。

三角剖分是一种特殊的多边形分割方法，它可以使得每个子图元（三角形单元）面积最小且相互之间没有重叠部分。

三、常见的多变性分割算法1. 三角剖分法三角剖分是最常见的多边形分割算法，它将多边形划分成若干个三角形。

三角剖分有很多种方法，如Delaunay三角剖分、Ear Clipping Triangulation等。

2. 对角线交换法对角线交换法是一种将凸多边形划分为若干个凸子多边形的算法。

该算法首先选择一个顶点，然后从该点开始依次连接其他顶点，如果连接的线段不在多边形内部，则将其作为对角线，将多边形划分为两个子多边形。

接下来再对每个子多边形递归进行划分。

3. 梯形切割法梯形切割法是一种利用梯形进行切割的算法。

该算法首先将多边形按照从上到下的顺序排序，然后依次连接相邻两条线段所在的梯形的上底和下底，直到所有的梯形都被覆盖。

这样就可以将凸或凹多边形划分为若干个凸子多边形。

4. 空间扫描线算法空间扫描线算法是一种基于扫描线的算法。

该算法首先将多边形按照从上到下的顺序排序，然后从上到下依次扫描每一条水平线段，同时记录当前扫描线段与多边形相交的所有线段。

当扫描到某个顶点时，如果该点是凸顶点，则将其加入划分结果中，并删除与该顶点相邻的所有线段；如果该点是凹顶点，则选择与该点相邻的两条线段中跨越最小角度的一条作为对角线，并将多边形划分为两个子多边形。

大学实验报告学院：计算机科学与信息学院专业：软件工程班级：102班** 实验组实验时间指导教师成绩实验工程名称实验五直线和多边形的裁剪实验目的掌握直线段的裁剪算法以及多边形的裁剪算法实验要求熟练掌握直线段的裁剪算法以及多边形的裁剪算法的根本原理，并编写测试代码进展实验。

实验原理Cohen-Sutherland直线剪裁算法以区域编码为根底，将窗口及其周围的，8个方向以4 bit的二进制数进展编码。

右图所示的编码方法将窗口及其邻域分为5个区域：⑴域：区域(0000)。

⑵上域：区域(1001, 1000, 1010)。

⑶下域：区域(0101, 0100, 0110)。

⑷左域：区域(1001, 0001, 0101)。

⑸右域：区域(1010, 0010, 0110)。

当线段的两个端点的编码的逻辑"与〞非零时，线段为显然不可见的，对*线段的两个端点的区号进展位与运算，可知这两个端点是否同在视区的上、下、左、右；Cohen-Sutherland直线剪裁算法的算法思想是：对于每条线段P1P2分为三种情况处理。

〔1〕假设P1P2完全在窗口，则显示该线段P1P2简称"取〞之。

〔2〕假设P1P2明显在窗口外，则丢弃该线段，简称"弃〞之。

〔3〕假设线段既不满足"取〞的条件，也不满足"弃〞的条件，则在交点处把线段分为两段。

其while (code1 != 0 || code2 != 0) {if ((code1 & code2) != 0) {// 两端点的编码相与不为0，表示直线在窗口外return;}if (code1 != 0) {code = code1;} else {code = code2;}if ((LEFT & code) != 0) {// 直线的端点与矩形窗口的左边编码相与！=0* = *L;y = y1 + (y2 - y1) * (*L - *1) / (*2 - *1);// 求直线与矩形窗口的左边界的交点} elseif ((RIGHT & code) != 0) {// 直线的端点与矩形窗口的右边编码相与！=0* = *R;y = y1 + (y2 - y1) * (*R - *1) / (*2 - *1);// 求直线与矩形窗口的右边界的交点} elseif ((BOTTOM & code) != 0) {// 直线的端点与矩形窗口的下边编码相与！=0y = YB;* = *1 + (*2 - *1) * (YB - y1) / (y2 - y1);// 求直线与矩形窗口的下边界的交点} elseif ((TOP & code) != 0) {// 直线的端点与矩形窗口的上边编码相与！=0y = YT;* = *1 + (*2 - *1) * (YT - y1) / (y2 - y1);// 直线的端点与矩形窗口的上// 边编码相与！=0}if (code == code1) {*1 = *;y1 = y;code1 = encode(*, y);} else {*2 = *;y2 = y;code2 = encode(*, y);}}g.drawLine((int) (*1 + 0.5), (int) (y1 + 0.5), (int) (*2 + 0.5),(int) (y2 +0.5));}二、多边形裁剪的核心代码为：通过点集画直线或者多边形：privatevoid draw() {//通过点集画直线或者多边形for (int i = 1; i < points.size(); i++) {Point p1 = new Point();p1 = points.get(i);int *1 = (int) p1.get*();int y1 = (int) p1.getY();Point p2 = new Point();p2 = points.get(i - 1);int *2 = (int) p2.get*();int y2 = (int) p2.getY();g.drawLine(*1, y1, *2, y2);}}多边形的裁剪函数：private Point[] cutPicture(Point[] point, Point[] edge) {// 剪裁函数，参数为〔点集，边〕Point[] intersectPoint = new Point[20];//存放交点的集合for (int j = 0; j < 20; j++) {intersectPoint[j] = new Point();}Point s = new Point();Point p = new Point();Point t = new Point();int i = 0;int length = point.length;s = point[length - 1];for (int j = 0; j < length; j++) {p = point[j];if (inside(p, edge)) {// sp在窗口，情况1if (inside(s, edge)) {intersectPoint[i] = p;i += 1;} else {// s在窗口外，情况4t = intersect(s, p, edge);intersectPoint[i] = t;i += 1;intersectPoint[i] = p;i += 1;}} elseif (inside(s, edge)) {// s在窗口，p在窗口外，情况3t = intersect(s, p, edge);intersectPoint[i] = t;i += 1;}// 情况2没有输出s = p;}List<Point> tempList = new ArrayList<Point>();for (int k = 0; k < i; k++) {if (intersectPoint[k] != null) {Point pt = intersectPoint[k];tempList.add(pt);}}Point[] temp = new Point[tempList.size()];for (int j = 0; j < tempList.size(); j++) {temp[j] = new Point();temp[j] = tempList.get(j);}intersectPoint = temp;return intersectPoint;}判断点是否在裁剪边的可见侧：privateboolean inside(Point point, Point[] edge) {//判断点是否在裁剪边的可见侧// 裁剪边为窗口下边if ((edge[0].y == edge[1].y) && (edge[0].* < edge[1].*)) {if (point.y >= edge[0].y) {returntrue;}}// 裁剪边为窗口上边if ((edge[0].y == edge[1].y) && (edge[0].* > edge[1].*)) {if (point.y <= edge[0].y) {returntrue;}}// 裁剪边为窗口右边if ((edge[0].* == edge[1].*) && (edge[0].y < edge[1].y)) {if (point.* <= edge[0].*) {returntrue;}}// 裁剪边为窗口左边if ((edge[0].* == edge[1].*) && (edge[0].y > edge[1].y)) {if (point.* >= edge[0].*) {returntrue;}}returnfalse;}直线段与窗口边界求交：private Point intersect(Point s, Point p, Point[] edge) {//直线段与窗口边界求交，并返回交点Point t = new Point();if (edge[0].y == edge[1].y) {// 水平裁剪边t.y = edge[0].y;t.* = s.* + (edge[0].y - s.y) * (p.* - s.*) / (p.y - s.y);} elseif (edge[0].* == edge[1].*) {// 垂直裁剪边t.* = edge[0].*;t.y = s.y + (edge[0].* - s.*) * (p.y - s.y) / (p.* - s.*);}return t;}鼠标的监听类〔部类〕：class MouseMonitor e*tends MouseAdapter {//通过鼠标的单击获取点，并画出直线或者多边形publicvoid mouseClicked(MouseEvent e) {points.add(e.getPoint());if (points.size() > 1) {draw();}}}键盘的监听类〔部类〕：class KeyMonitor e*tends KeyAdapter {// 键盘控制publicvoid keyPressed(KeyEvent e) {switch (e.getKeyCode()) {case KeyEvent.VK_R:// 清空画布和点集panel.repaint();points.removeAll(points);break;case KeyEvent.VK_W://对裁剪窗口的处理g.setColor(Color.RED);g.drawRect(*L, YB, *R - *L, YT - YB);//存放裁剪窗口的边top = new Point[2];// 存放裁剪窗口的上边top[0] = new Point(*L, YB);top[1] = new Point(*R, YB);right = new Point[2];//存放裁剪窗口的右边right[0] = new Point(*R, YB);right[1] = new Point(*R, YT);bottom = new Point[2];//存放裁剪窗口的下边bottom[0] = new Point(*R, YT);bottom[1] = new Point(*L, YT);left = new Point[2];//存放裁剪窗口的左边left[0] = new Point(*L, YT);left[1] = new Point(*L, YB);break;case KeyEvent.VK_A://对直线段进展裁剪g.setColor(Color.GREEN);Point p1 = points.get(0);Point p2 = points.get(1);lineCut(p1.get*(), p1.getY(), p2.get*(), p2.getY()); break;case KeyEvent.VK_B://对多边形进展裁剪source = new Point[points.size()];//得到多边形的点for (int i = 0; i < points.size(); i++) {source[i] = points.get(i);}g.setColor(Color.GREEN);wT = cutPicture(source, top);//得到多边形与裁剪窗口上边的交点wR = cutPicture(wT, right);//得到多边形与裁剪窗口右边的交点wB = cutPicture(wR, bottom);//得到多边形与裁剪窗口下边的交点wL = cutPicture(wB, left);//得到多边形与裁剪窗口左边的交点第二种情况：线段在裁剪窗口的部，线段完全可见。