实验三-图形裁剪算法实现.doc

实验三 图形裁剪算法实现
实验学时：2学时
实验类型：验证型
实验要求：必修
在使用计算机处理图形信息时，计算机内部存储的图形往往比较大，而屏幕显示的只是图的一部分。因此需要确定图形中哪些部分落在显示区之内，哪些落在显示区之外，以便只显示落在显示区内的那部分图形。这个选择过程称为裁剪。最简单的裁剪方法是把各种图形扫描转换为点之后，再判断各点是否在窗内。但那样太费时，一般不可取。这是因为有些图形组成部分全部在窗口外，可以完全排除，不必进行扫描转换。所以一般采用先裁剪再扫描转换的方法，多边形裁剪示意图，如图1-1所示。

（a）裁剪前 （b）裁剪后
图1-1 多边形裁剪示意图
直线裁剪
1．直线和窗口的关系
直线和窗口的关系如图1-2所示，可以分为如下3类：

图1-2 直线与窗口的关系

（1）整条直线在窗口内。此时，不需剪裁，显示整条直线。
（2）整条直线在窗口外，此时，不需剪裁，不显示整条直线。
（3）部分直线在窗口内，部分直线在窗口外。此时，需要求出直线与窗框的交点，并将窗口外的直线部分剪裁掉，显示窗口内的直线部分。
直线剪裁算法有两个主要步骤。首先将不需剪裁的直线挑出，即删去在窗外的直线。然后，对其余直线，逐条与窗框求交点，并将窗口外的部分删去。
2．Cohen-Sutherland直线剪裁算法
以区域编码为基础，将窗口及其周围的8个方向以4 bit的二进制数进行编码。如图1-3所示的编码方法将窗口及其邻域分为5个区域。
（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所示，是上述多边形裁剪的原理示意图。

图1-6 多边形裁剪原理示意图2
图形裁剪编程
1．程序设计功能说明
如图1-7所示为图形裁剪的实用程序运行时的主界面，首先根据界面提示，在用户区双击，出现所需要裁剪的各种线段，再单击菜单中“图形裁剪”，可选择其下拉菜单的各图形裁剪选项完成各种图形裁剪（在窗口中红矩形框外的线段或多边形被裁减掉）。

图1-7 “图形裁剪”程序主界面
2．程序设计步骤
程序“图形裁剪”的设计步骤如下：
（1）创建工程名称为“图形裁剪”单文档应用程序框架（参看上面单文档应用程序框架的建立）。
（2）编辑菜单资源。

图1-8 图形裁剪切界面

设计如图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_CLIPLINE
CONMMAN
OnIDTRANSLATION
ID_CLIPPOLYGON
CONMMAN
OnIDROTATION
（4）添加代码，在图形裁剪应用程序的相应文件中添加如下黑体字部分代码。
① 在“图形裁剪View.h”文档中的适当位置添加定义存储线段端点的数组。

class CMyView : public CView
{
protected: // create from serialization only
M
public:
CPoint ptset[N];
M
};

② 在“图形裁剪View.cpp”文档中的适当位置手工添加以下黑体部分代码。

#include "stdafx.h"
#include "图形裁剪.h"
M
#endif
#define LEFT 1
#define RIGHT 2
#define BOTTOM 4
#define TOP 8
#define XL 100
#define XR 300
#define YT 100
#define YB 250
//////////////////////////////////////////////////////////////////
void CMyView::OnDraw(CDC* pDC)//功能为程序开始呈现下面的界面
{
CMyDoc* pDoc = GetDocument();
ASSERT_VALID(pDoc);
// TODO: add draw code for native data here
CPen newpen(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);
}
//////////////////////////////////////////////////////////////////
//处理双击左键消息函数，得到要进行裁剪的直线段
void CMyView::OnLButtonDblClk(UINT nFlags, CPoint point)
{
CDC* pDC=GetDC();
CPen newpen(PS_SOLID,1,RGB(255,0,0));
CPen *old=pDC->SelectObject(&newpen);
flag=1;
for(int i=0;i<N;i++)
{
pDC->MoveTo(ptset[i]);
pDC->LineTo(ptset[i+1]);
i++;
}
CView::OnLButtonDblClk(nFlags, point);
}

void CMyView::OnClipline() //线段裁剪消息处理函数
{

图1-10 警告图示窗

CDC* pDC=GetDC();
CPen newpen(PS_SOLID,1,RGB(0,255,0));
CPen *old=pDC->SelectObject(&newpen);
if(flag!=1)
{MessageBox("请先双击","警告！");}（如图1-10所示）
else
{
float x,y,x1,x2,y1,y2;
int i;
int code1,code2;
RedrawWindow();
// 求两端点所在区号code
for(i=0;i<N;i++,i++)
{
int c=0;

图1-11 线段剪切结果

if(ptset[i].x<XL) c=c|LEFT;
else if (ptset[i].x>XR)c=c|RIGHT;
if(ptset[i].y>YB) c=c|BOTTOM;
else if(ptset[i].y<YT) c=c|TOP;
code1=c;
c=0;
if(ptset[i+1].x<XL) c=c|LEFT;
else if(ptset[i+1].x>XR) c=c|RIGHT;
if(ptset[i+1].y>YB) c=c|BOTTOM;
else if(ptset[i+1].y<YT) c=c|TOP;
code2=c;
//线段与区域的相交情况（见图1-11）
if(code1!=0&&code2!=0&&(code1&code2)==0)
{
if((LEFT&code1)!=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);
}
else if((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);
}
else if((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);
}
else if((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);
}
else if((RIGHT&code2)!=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);
}
else if((BOTTOM&code2)!=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);
}
else if((TOP&code2)!=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+1].x=x;
ptset[i+1].y=y;
pDC->MoveTo(ptset[i].x,ptset[i].y);
pDC->LineTo(ptset[i+1].x,ptset[i+1].y);
}
if(code1==0&&code2==0)
{pDC->MoveTo(ptset[i].x,ptset[i].y);
pDC->LineTo(ptset[i+1].x,ptset[i+1].y);
}
if(code1==0&&code2!=0)
{
pDC->MoveTo(ptset[0].x,ptset[0].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);
}
else if((RIGHT&code2)!=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);
}
else if((BOTTOM&code2)!=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);
}
else if((TOP&code2)!=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+1].x=x;
ptset[i+1].y=y;
pDC->LineTo(ptset[i+1].x,ptset[i+1].y);
}
if(code1!=0&&code2==0)
{
pDC->MoveTo(ptset[i+1].x,ptset[i+1].y);
if((LEFT&code1)!=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);
}
else if((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);
}
else if((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);
}
else if((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;
pDC->LineTo(ptset[i].x,ptset[i].y);
}
}
}

图1-12 多边形剪切

}
//处理双击右键出现要裁剪的多边形（见图1-12）
void CMyView::OnRButtonDblClk(UINT nFlags, CPoint point)
{
CDC* pDC=GetDC();
CPen newpen(PS_SOLID,1,RGB(255,0,0));
CPen *old=pDC->SelectObject(&newpen);
flag=2;
pDC->MoveTo(ptset1[0]);
for(int i=1;i<5;i++)
{
pDC->LineTo(ptset1[i]);
}
CView::OnRButtonDblClk(nFlags, point);
}
void CMyView::OnClippolygon() 多边形裁剪（见图1-13）

图1-15 警告提示窗
{
CDC* pDC=GetDC();
CPen newpen(PS_SOLID,1,RGB(0,255,0));
CPen *old=pDC->SelectObject(&newpen);
if(flag!=1)
{MessageBox("请先双击鼠标右键","警告！");}（见图1-14）
else
{
int i,k;
int code1,code2;
int M=5;

图1-13 多边形剪切结果

RedrawWindow();
// 求两端点所在区号code
k=0;
for(i=0;i<M;i++)
{
int c=0;
if(ptset1[i].x<XL) c=1;
else if (ptset1[i].x>XL)c=0;
code1=c;
c=0;
if(ptset1[i+1].x<XL) c=1;
else if(ptset1[i+1].x>XL) c=0;
code2=c;
if(code1!=0&&code2==0)
{
pt[k].x=XL;
pt[k].y=ptset1[i].y+(ptset1[i+1].y-ptset1[i].y)*(XL-
ptset1[i].x)/(ptset1[i+1].x-ptset1[i].x);
pt[k+1].x=ptset1[i+1].x;
pt[k+1].y=ptset1[i+1].y;
k=k+2;
}
if(code1==0&&code2==0)
{
if(k==0)
{
pt[k].x=ptset1[i].x;
pt[k].y=ptset1[i].y;
pt[k+1].x=ptset1[i+1].x;
pt[k+1].y=ptset1[i+1].y;
k=k+2;
}
if(k!=0)
{
pt[k].x=ptset1[i+1].x;
pt[k].y=ptset1[i+1].y;
k=k+1;
}
}
if(code1==0&&code2!=0)
{
pt[k].x=XL;
pt[k].y=ptset1[i].y+(ptset1[i+1].y-ptset1[i].y)*(XL-
ptset1[i].x)/(ptset1[i+1].x-ptset1[i].x);
k++;
}
}
pt[k].x=pt[0].x;
pt[k].y=pt[0].y;
M=k+1;
k=0;
for(i=0;i<M;i++)
{
int c=0;
if(pt[i].x<XR) c=0;
else if(pt[i].x>XR) c=2;
code1=c;
c=0;
if(pt[i+1].x<XR) c=0;
else if(pt[i+1].x>XR) c=2;
code2=c;
if(code1==0&&code2==0)
{
if(k==0)
{
pts[k].x=pt[i].x;
pts[k].y=pt[i].y;
pts[k+1].x=pt[i+1].x;
pts[k+1].y=pt[i+1].y;
k=k+2;
}
if(k!=0)
{
pts[k].x=pt[i+1].x;
pts[k].y=pt[i+1].y;
k++;
}
}
if(code1!=0&&code2==0)
{
pts[k].x=XR;
pts[k].y=pt[i].y+(pt[i+1].y-pt[i].y)*(XR-pt[i].x)/(pt[i+
1].x-pt[i].x);
pts[k+1].x=pt[i+1].x;
pts[k+1].y=pt[i+1].y;
k=k+2;
}
if(code1==0&&code2!=0)
{
pts[k].x=XR;
pts[k].y=pt[i].y+(pt[i+1].y-pt[i].y)*(XR-pt[i].x)/(pt[i+
1].x-pt[i].x);
k=k+1;
}
}
//处理最后一条边
pts[k]=pts[0]; M=k+1; k=0;
for(i=0;i<M;i++)
{
int c=0;
if(pts[i].y>YB) c=4;
else if(pts[i].y<YB) c=0;
code1=c;
c=0;
if(pts[i+1].y>YB) c=4;
else if(pts[i+1].y<YB) c=0;
code2=c;

if(code1==0&&code2==0)
{
if(k==0)
{
ptse[k].x=pts[i].x;
ptse[k].y=pts[i].y;
ptse[k+1].x=pts[i+1].x;
ptse[k+1].y=pts[i+1].y;
k=k+2;
}
if(k!=0)
{
ptse[k].x=pts[i+1].x;
ptse[k].y=pts[i+1].y;
k=k+1;
}
}
if(code1!=0&&code2==0)
{
ptse[k].y=YB;
ptse[k].x=pts[i].x+(pts[i+1].x-pts[i].x)*(YB-pts[i].y)/
(pts[i+1].y-pts[i+1].y);
ptse[k+1].x=pts[i+1].x;
ptse[k+1].y=pts[i+1].y;
k=k+2;
}
}
if(code1==0&&code2!=0)
{
ptse[k].y=YB;
ptse[k].x=pts[i].x+(pts[i+1].x-pts[i].x)*(YB-pts[i].y)/
(pts[i+1].y-pts[i+1].y);
k=k+1;
}
ptse[k]=ptse[0];
M=k+1;
k=0;
for(i=0;i<M;i++)
{
int c=0;
if(ptse[i].y>YT) c=0;
else if(ptse[i].y<YT) c=1;
code1=c;
c=0;
if(ptse[i+1].y>YT) c=0;
else if(ptse[i+1].y<YT) c=1;
code2=c;
if(code1!=0&&code2==0)
{
p[k].y=YT;
p[k].x=ptse[i].x+(ptse[i+1].x-ptse[i].x)*(YT-ptse[i].y)/
(ptse[i+1].y-ptse[i].y);
p[k+1].x=ptse[i+1].x;
p[k+1].y=ptse[i+1].y;
k=k+2;
}
if(code1==0&&code2==0)
{
if(k==0)
{
p[k].x=ptse[i].x;
p[k].y=ptse[i].y;
p[k+1].x=ptse[i+1].x;
p[k+1].y=ptse[i+1].y;
k=k+2;
}
if(k!=0)
{
p[k].x=ptse[i+1].x;
p[k].y=ptse[i+1].y;
k=k+1;
}
}
if(code1==0&&code2!=0)
{
p[k].y=YT;
p[k].x=ptse[i].x+(ptse[i+1].x-ptse[i].x)*(YT-ptse[i].y)/
(ptse[i+1].y-ptse[i].y);
k++;
}
}
p[k]=p[0];
M=k+1;
pDC->MoveTo(p[0]);
for(int j=1;j<=M;j++)
{
pDC->LineTo(p[j]);
}
}
}