实验三图形裁剪算法实现

实验三图形裁剪算法实现实验学时：2学时实验类型：验证型实验要求：必修在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法，多边形裁剪示意图，如图1-1所示。（a）裁剪前（b）裁剪后图1-1多边形裁剪示意图直线裁剪1．直线和窗口的关系直线和窗口的关系如图1-2所示，可以分为如下3类：（1）整条直线在窗口内。此时，不需剪裁，显示整条直线。（2）整条直线在窗口外，此时，不需剪裁，不显示整条直线。（3）部分直线在窗口内，部分直线在窗口外。此时，需要求出直线与窗框的交点，并将窗口外的直线部分剪裁掉，显示窗口内的直线部分。直线剪裁算法有两个主要步骤。首先将不需剪裁的直线挑出，即删去在窗外的直线。然后，对其余直线，逐条与窗框求交点，并将窗口外的部分删去。2．Cohen-Sutherland直线剪裁算法以区域编码为基础，将窗口及其周围的8个方向以4bit的二进制数进行编码。如图1-3所示的编码方法将窗口及其邻域分为5个区域。图1-2直线与窗口的关系（1）内域：区域（0000）。（2）上域：区域（1001，1000，1010）。（3）下域：区域(0101,0100,0110)。（4）左域：区域(1001,0001,0101)。图1-3窗口及其邻域的5个区域及与直线的关系（5）右域：区域(1010,0010,0110)。当线段的两个端点的编码的逻辑“与”非零时，线段显然为不可见的。对某线段的两各端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右。算法的主要思想是，对每条直线，如P1P2利用以下步骤进行判断：①对直线两端点P1、P2编码分别记为C1(P1)={a1,b1,c1,d1}，C2(P2)={a2,b2,c2,d2}其中，ai、bi、ci、di取值范围为{1,0}，i∈{1,2}。②如果ai=bi=ci=di=0，则显示整条直线，取出下一条直线，返回步骤①；否则，进入步骤③。③如果|a1–a2|=1，则求直线与窗上边（y=yw–max）的交点，并删去交点以上部分。如果|b1–b2|=1，|c1–c2|＝1，|d1–d2|=1，进行类似处理。④返回步骤①判断下一条直线。多边形裁剪多边形裁剪算法的关键在于，通过剪裁，要保持窗口内多边形的边界部分，而且要将窗框的有关部分按一定次序插入多边形的保留边界之间，从而使剪裁后的多边形的边仍然保持封闭状态，以便填色算法得以正确实现，多边形裁剪原理示意图，如图1-4所示。（a）剪裁的多边形（b）按直线剪裁的多边形（c）按多边形剪裁后的多边形图1-4多边形裁剪原理示意图1（1）Sutherland-Hodgman算法思路：将多边形的各边先相对于窗口的某一条边界进行裁剪，然后将裁剪结果再与另一条边界进行裁剪，如此重复多次，便可得到最终结果。（2）实现方法：①设置两个表。输入顶点表（向量）——用于存放被裁剪多边形的顶点p1–pm。输出顶点表（线性链表）——用于存放裁剪过程中间结果的顶点q1–qn。②输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。③相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪。（3）具体操作步骤如下：①Pi若位于边界线的可见一侧，则Pi送给输出顶点表。②Pi若位于边界线的不可见一侧，则将其舍弃。③除第一个顶点外，还要检查每一个Pi和前一顶点Pi–1是否位于窗口边界的同一侧，若不在同一侧，则需计算出交点送给输出顶点表。④最后一个顶点Pn则还要与P1一起进行同样的检查。如下图1-6所示，是上述多边形裁剪的原理示意图。p4p3p2p6p1q2q1q8q7q5q6q5q6q8q7q4q3p3q2q1q3q4图1-6多边形裁剪原理示意图2图形裁剪编程1．程序设计功能说明如图1-7所示为图形裁剪的实用程序运行时的主界面，首先根据界面提示，在用户区双击，出现所需要裁剪的各种线段，再单击菜单中“图形裁剪”，可选择其下拉菜单的各图形裁剪选项完成各种图形裁剪（在窗口中红矩形框外的线段或多边形被裁减掉）。图1-7“图形裁剪”程序主界面2．程序设计步骤程序“图形裁剪”的设计步骤如下：（1）创建工程名称为“图形裁剪”单文档应用程序框架（参看上面单文档应用程序框架的建立）。（2）编辑菜单资源。设计如图1-8所示的菜单项。在工作区的ResourceView标签中，单击Menu项左边“+”，然后双击其子项IDR_MAINFRAME，并根据表1-9中的定义编辑菜单资源。表1-9菜单资源表菜单标题菜单项标题标示符ID图形裁剪线段裁剪ID_CLIPLINE多边形裁剪ID_CLIPPOLYGON（3）添加消息处理函数。利用ClassWizard（建立类向导）为应用程序添加与菜单项相关的消息处理函数，ClassName栏中选择CMyView，根据表1-10建立如下的消息映射函数，ClassWizard会自动完成有关的函数声明。表1-10菜单项的消息处理函数菜单项ID消息消息处理函数ID_CLIPLINECONMMANOnIDTRANSLATIONID_CLIPPOLYGONCONMMANOnIDROTATION（4）添加代码，在图形裁剪应用程序的相应文件中添加如下黑体字部分代码。①在“图形裁剪View.h”文档中的适当位置添加定义存储线段端点的数组。classCMyView:publicCView{protected://createfromserializationonlypublic:CPointptset[N];图1-8图形裁剪切界面};②在“图形裁剪View.cpp”文档中的适当位置手工添加以下黑体部分代码。#includestdafx.h#include图形裁剪.h#endif#defineLEFT1#defineRIGHT2#defineBOTTOM4#defineTOP8#defineXL100#defineXR300#defineYT100#defineYB250//////////////////////////////////////////////////////////////////voidCMyView::OnDraw(CDC*pDC)//功能为程序开始呈现下面的界面{CMyDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);//TODO:adddrawcodefornativedatahereCPennewpen(PS_SOLID,1,RGB(255,0,0));CPen*old=pDC-SelectObject(&newpen);pDC-Rectangle(CRect(XL,YT,XR,YB));//剪切窗口，可通过修改上面的对应数据修改裁剪矩形框//需要剪切的各种线段，可通过修改数据修改线段（见图1-9）ptset[0]=CPoint(120,150);ptset[1]=CPoint(170,110);ptset[2]=CPoint(0,190);ptset[3]=CPoint(350,150);ptset[4]=CPoint(0,250);ptset[5]=CPoint(150,230);ptset[6]=CPoint(200,50);ptset[7]=CPoint(120,150);图1-9线段剪切ptset1[0]=CPoint(20,150);ptset1[1]=CPoint(170,110);ptset1[2]=CPoint(250,150);ptset1[3]=CPoint(200,230);ptset1[4]=CPoint(20,150);pDC-TextOut(0,0,双击,出现要剪切的线段);pDC-TextOut(0,0,双击鼠标右键,出现要剪切的多边形);pDC-SelectObject(old);}////////////////////////////////////////////////////////////////////处理双击左键消息函数，得到要进行裁剪的直线段voidCMyView::OnLButtonDblClk(UINTnFlags,CPointpoint){CDC*pDC=GetDC();CPennewpen(PS_SOLID,1,RGB(255,0,0));CPen*old=pDC-SelectObject(&newpen);flag=1;for(inti=0;iN;i++){pDC-MoveTo(ptset[i]);pDC-LineTo(ptset[i+1]);i++;}CView::OnLButtonDblClk(nFlags,point);}voidCMyView::OnClipline()//线段裁剪消息处理函数{CDC*pDC=GetDC();CPennewpen(PS_SOLID,1,RGB(0,255,0));CPen*old=pDC-SelectObject(&newpen);if(flag!=1){MessageBox(请先双击,警告！);}（如图1-10所示）else{floatx,y,x1,x2,y1,y2;inti;intcode1,code2;RedrawWindow();//求两端点所在区号codefor(i=0;iN;i++,i++){intc=0;if(ptset[i].xXL)c=c|LEFT;elseif(ptset[i].xXR)c=c|RIGHT;if(ptset[i].yYB)c=c|BOTTOM;elseif(ptset[i].yYT)c=c|TOP;code1=c;c=0;if(ptset[i+1].xXL)c=c|LEFT;elseif(ptset[i+1].xXR)c=c|RIGHT;if(ptset[i+1].yYB)c=c|BOTTOM;elseif(ptset[i+1].yYT)c=c|TOP;code2=c;//线段与区域的相交情况（见图1-11）if(code1!=0&&code2!=0&&(code1&code2)==0){if((LEFT&code1)!=0)//线段与左边界相交{图1-10警告图示窗图1-11线段剪切结果x=XL;y=ptset[i].y+(ptset[i+1].y-ptset[i].y)*(XL-ptset[i].x)/(ptset[i+1].x-ptset[i].x);}elseif((RIGHT&code1)!=0)//线段与右边界相交{x=XR;y=ptset[i].y+(ptset[i+1].y-ptset[i].y)*(XR-ptset[i].x)/(ptset[i+1].x-ptset[i].x);}elseif((BOTTOM&code1)!=0)//线段与下边界相交{y=YB;x=ptset[i].x+(ptset[i+1].x-ptset[i].x)*(YB-ptset[i].y)/(ptset[i+1].y-ptset[i+1].y);}elseif((TOP&code1)!=0)//线段与上边界相交{y=YT;x=ptset[i].x+(ptset[i+1].x-ptset[i].x)*(YT-ptset[i].y)/(ptset[i+1].y-ptset[i].y);}ptset[i].x=x;ptset[i].y=y;if((LEFT&code2)!=0)//线段与左边界相交{x=XL;y=ptset[i].y+(ptset[i+1].y-ptset[i].y)*(XL-ptset[i].x)/(ptset[i+1].x-ptset[i].x);}elseif((R