编码裁减法的实现.doc

编码裁减法的实现一、 实验原理当用户在平面上定义了一个窗口后，总是希望把落在窗口内的部分图形映象到视图区中，而把窗口以外的图形运用裁减方法统统裁掉，不予输出。这种平面上的图形受该平面上的矩形窗口的裁减称为二维裁减。裁减的基本目的是判断图形元素是否在所考虑的区域内。如果在区域内，则进一步求出在区域内的那一部分。因此裁减处理包含两部分内容：（1） 点在区域内外的判断，即看点是否满足：；（2） 计算图形元素与区域边界的交点。编码裁减法是一种基本的二维裁减算法。它是用区域检查的办法有效的识别可以直接接受或直接舍弃的线段，只有不属于这两种情况的线段才需要计算交点。二、 基本算法与实现如图一所示，其中为窗口的四条边界。任何以条线段的端点，根据其坐标所在的区域都可以赋予4位二进制代码。设最左边的位为第一位，则其含义如下：第一位为1，表示端点在上方；第二位为1，表示端点在下方；第三位为1，表示端点在右方；第四位为1，表示端点在左方；否则相应位置零。各区域编码如图一所示。 1001（9） 1000（8） 1010（A） 0001（1） 0000 0010（2） 0101（5） 0100（4） 0110（6） 图一由图可知，如果线段两个端点的4位编码全为零，则此线段全部在窗口内，可直接接收（accept=1）；如果对线段的两个端点的4位编码进行逻辑与（按位乘）运算，结果为非零，则此线段全部在窗口之外，可直接舍弃；否则，这条线段既不能直接接受，也不能直接舍弃，它可能与窗口相交。此时，需要对线段进行再分割，即找到与窗口一个边框的交点。根据交点位置，也赋予4位代码，并对分割后的线段进行检查：或者接受，或者舍弃，或者再次进行分割。重复这一过程，直到全部线段均被舍弃或被接受为止。设两端分别为，核心程序实现如下（源程序见附录）：while(done!=1) c1=0,c2=0; /初始编码置零 if(x1XR) c1=c1|2; /在右方，第三位置1 if(y1YT) c1=c1|8; / 在上方，第一位置1 if(x2XR) c2=c2|2; /类似 if(y2YT) c2=c2|8; if(c1&c2)!=0) done=1; /线段在窗口之外，舍弃 else if(c1=0 & c2=0) done=1; accept=1; /均在窗口内 else if(c1=0) /在窗口内 xchange=x1; x1=x2; x2=xchange; /交换点坐标及编码 ychange=y1; y1=y2; y2=ychange; c=c1; c1=c2; c2=c; if(c1&4)=4) /求交点，点在窗口之下 x=x1-(y1-YB)*(x1-x2)/(y1-y2); y=YB; else if (c1&8)=8) /点在窗口之上 x=x1-(y1-YT)*(x1-x2)/(y1-y2); y=YT; else if( (c1&1)=1) /点在窗口之左 x=XL; y=y1-(x1-XL)*(y1-y2)/(x1-x2); else if(c1&2)=2) /点在窗口之右 x=XR; y=y1-(x1-XR)*(y1-y2)/(x1-x2); x1=x;y1=y; /else /while三、 算法流程图开始 初始化done=0,accept=0 求编码，编码 （逻辑与）=0 否 丢弃done=1 是且， 是 接受done=1，accept=1 否 ？ 否是在窗口内 与交换 求交 在窗口之 上 下 左 右 Y1=YT，X1= Y1=YB，X1= X1=XL,Y1= X1=XR,Y1=否 done=1 ? 是 accept=1 ? 否 是 显示- 退出四、 实验结果 两端点坐标分别为（5，2），（260，200）的直线裁减前后的图形如下：两端点坐标分别为（30，50），（160，250）的直线裁减前后的图形如下：五、 总结 通过对这次计算机图形学的实验，我不仅深刻的掌握了编码裁减法的基本原理和算法，还学习了c+builder中多种组件的使用，例如Image组件、TCanvas组件、Edit、Label等的使用，使我对该软件有了更深的认识。附录： int x,y,x1,y1,x2,y2,xchange,ychange; bool done=0,accept=0; char c,c1,c2; int XL=20,XR=150,YB=20,YT=180; / 定义窗口区大小 Image1-Canvas-Rectangle(0,0,Image1-Width,Image1-Height); Image1-Canvas-Rectangle(XL,YB,XR,YT); Image2-Canvas-Rectangle(XL,YB,XR,YT); x1=StrToInt(X1-Text); y1=StrToInt(Y1-Text); x2=StrToInt(X2-Text); y2=StrToInt(Y2-Text); Image1-Canvas-MoveTo(x1,y1); Image1-Canvas-LineTo(x2,y2); while(done!=1) c1=0,c2=0; if(x1XR) c1=c1|2; if(y1YT) c1=c1|8; if(x2XR) c2=c2|2; if(y2YT) c2=c2|8; if(c1&c2)!=0) done=1; else if(c1=0 & c2=0) done=1; accept=1; /p1,p2均在窗口内 else if(c1=0) xchange=x1; x1=x2; x2=xchange; /交换p1,p2点 ychange=y1; y1=y2; y2=ychange; c=c1; c1=c2; c2=c; if(c1&4)=4) x=x1-(y1-YB)*(x1-x2)/(y1-y2); y=YB; else if (c1&8)=8) x=x1-(y1-YT)*(x1-x2)/(y1-y2); y=YT; else if( (c1&1)=1) x=XL; y=y1-(x1-XL)*(y1-y2)/(x1-x2); e