对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右；
‐如果两端点的编码均为0000，表示直线在窗口内。
‐如果两端点的编码相与不为0000，表示直线在窗口外。
‐如果两端点的编码不全为0000，但相与为0000，则该直线部分可见，需计算直线与窗口的交点，确定哪一部分可见。
裁剪一条线段时，先求出P1P2所在的区号code1,code2。
若code1=0,且code2=0，则线段P1P2在窗口内，应取之。
若按位与运算code1&code2≠0，则说明两个端点同在窗口的上方、下方、左方或右方。
可判断线段完全在窗口外，可弃之。
否则，按第三种情况处理。
求出线段与窗口某边的交点，在交点处把线段一分为二，其中必有一段在窗口外，可弃之。
在对另一段重复上述处理。
在实现本算法时，不必把线段与每条窗口边界依次求交，只要按顺序检测到端点的编码不为0，才把线段与对应的窗口边界求交。
算法分析：
本算法的优点在于简单，易于实现。
用编码方法可快速判断线段的完全可见和显然不可见，他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。
在这个算法中求交点是很重要的，他决定了算法的速度。
本算法对于其他形状的窗口是否同样有效就值得讨论了，这也证明了在图形算法中，没有几个是对大多数情况有效的。
特别适用二种情形：
大窗口场合（线段大多数为完全可见）；窗口特别小场合（线段大多数为完全不可见。
光标拾取图形，光标看作小的裁剪窗口）。
多边形裁剪算法：
Sutherland-Hodgema算法
算法原理：
通过对单一边或面的裁剪来实现多边形的裁剪
分割处理策略：
将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。
一次用窗口的一条边裁剪多边形。
流水线过程（左上右下）：
前边的结果是后边的输入。
亦称逐边裁剪算法。
算法的每一次输出（包括中间结果）都是一个多边形的顶点表，且所有顶点均位于相应窗口裁剪边或面的可见一侧。
由于多边形的每一条边需要与裁剪边或面分别进行比较，因此只需要讨论单条边和单个裁剪边或面之间可能的位置关系。
假设S，P为多边形的两个相邻顶点，且S为该边的起点，P为该边的终点，则变SP与裁剪边或面之间只有4种可能的关系。
如下图：
由上可见，每一次将多边形的边与裁剪边或面比较后，输出一个或两个顶点，也可能无输出点。
如果SP边完全可见，则输出P点，不必输出起点S，因为顶点是按顺序处理的，S是作为前一边的终点输出的。
如果SP边完全不可见，则无输出。
如果SP边部分可见，则SP边可能进入或离开裁剪边或面的可见一侧。
如果SP边离开裁剪边或面的可见一侧，则输出SP与裁剪边或面交点。
如果SP边进入裁剪边或面的可见一侧，则输出两点，一个为SP与裁剪边或面的交点，一个是P点。
对于多边形的第一个顶点，只需判断其可见性。
如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。
对于最后一条边PnP1，其处理方法是：
标志第一顶点为F，这样最后一条边则为PnF，可与其他边作相同的处理。
实现方法：
设置二个表：
输入顶点表：
用于存放被裁剪多边形的顶点p1-pm。
输出顶点表：
用于存放裁剪过程中及结果的顶点q1-qn。
输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。
相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪
算法分析：
对凸多边形应用本算法可以得到正确的结果，但是对凹多边形的裁剪将显示出一条多余的直线。
这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。
因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。
解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。
二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。
实验环境
硬件平台：
PC机
软件：
Windows7平台，eclipse集成开发环境，java编程语言。
实验步骤
1.掌握算法原理；
2.依据算法，编写源程序并进行调试；
3.对运行结果进行保存与分析；
4.把源程序以文件的形式提交；
5.按格式书写实验报告。
实验内容
一、直线段裁剪算法的核心代码为：
计算（x,y）点的编码的方法：
privateintencode（doublex,doubley）{//求（x,y）点的编码
intcode=0;
if（xcode|=LEFT;//并上左边的编码0001
}elseif（x>XR）{//点位于矩形的右边
code|=RIGHT;//并上右边的编码0010
}elseif（ycode|=BOTTOM;//并上下边的编码0100
}elseif（y>YT）{//点位于矩形的上边
code|=TOP;//并上上边的编码1000
}
returncode;
}
直线段裁剪的方法：
privatevoidlineCut（doublex1,doubley1,doublex2,doubley2）{//直线的起点（x1,y1）和终点（x2,y2）
doublex=0,y=0;
intcode1,code2,code;
code1=this.encode（x1,y1）;//起点的编码
code2=this.encode（x2,y2）;//终点的编码
while（code1!
=0||code2!
=0）{
if（（code1&code2）!
=0）{//两端点的编码相与不为0，表示直线在窗口外
return;
}
if（code1!
=0）{
code=code1;
}else{
code=code2;
}
if（（LEFT&code）!
=0）{//直线的端点与矩形窗口的左边编码相与！
=0
x=XL;
y=y1+（y2-y1）*（XL-x1）/（x2-x1）;//求直线与矩形窗口的左边界的交点
}elseif（（RIGHT&code）!
=0）{//直线的端点与矩形窗口的右边编码相与！
=0
x=XR;
y=y1+（y2-y1）*（XR-x1）/（x2-x1）;//求直线与矩形窗口的右边界的交点
}elseif（（BOTTOM&code）!
=0）{//直线的端点与矩形窗口的下边编码相与！
=0
y=YB;
x=x1+（x2-x1）*（YB-y1）/（y2-y1）;//求直线与矩形窗口的下边界的交点
}elseif（（TOP&code）!
=0）{//直线的端点与矩形窗口的上边编码相与！
=0
y=YT;
x=x1+（x2-x1）*（YT-y1）/（y2-y1）;//直线的端点与矩形窗口的上
//边编码相与！
=0
}
if（code==code1）{
x1=x;
y1=y;
code1=encode（x,y）;
}else{
x2=x;
y2=y;
code2=encode（x,y）;
}
}
g.drawLine（（int）（x1+0.5）,（int）（y1+0.5）,（int）（x2+0.5）,（int）（y2+0.5））;
}
二、多边形裁剪的核心代码为：
通过点集画直线或者多边形：
privatevoiddraw（）{//通过点集画直线或者多边形
for（inti=1;iPointp1=newPoint（）;
p1=points.get（i）;
intx1=（int）p1.getX（）;
inty1=（int）p1.getY（）;
Pointp2=newPoint（）;
p2=points.get（i-1）;
intx2=（int）p2.getX（）;
inty2=（int）p2.getY（）;
g.drawLine（x1,y1,x2,y2）;
}
}
多边形的裁剪函数：
privatePoint[]cutPicture（Point[]point,Point[]edge）{//剪裁函数，参数为（点集，边）
Point[]intersectPoint=newPoint[20];//存放交点的集合
for（intj=0;j<20;j++）{
intersectPoint[j]=newPoint（）;
}
Points=newPoint（）;
Pointp=newPoint（）;
Pointt=newPoint（）;
inti=0;
intlength=point.length;
s=point[length-1];
for（intj=0;jp=point[j];
if（inside（p,edge））{//sp在窗口内，情况1
if（inside（s,edge））{
intersectPoint[i]=p;
i+=1;
}else{//s在窗口外，情况4
t=intersect（s,p,edge）;
intersectPoint[i]=t;
i+=1;
intersectPoint[i]=p;
i+=1;
}
}elseif（inside（s,edge））{
//s在窗口内，p在窗口外，情况3
t=intersect（s,p,edge）;
intersectPoint[i]=t;
i+=1;
}//情况2没有输出
s=p;
}
ListtempList=newArrayList（）;
for（intk=0;kif（intersectPoint[k]!
=null）{
Pointpt=intersectPoint[k];
tempList.add（pt）;
}
}
Point[]temp=newPoint[tempList.size（）];
for（intj=0;jtemp[j]=newPoint（）;
temp[j]=tempList.get（j）;
}
intersectPoint=temp;
returnintersectPoint;
}
判断点是否在裁剪边的可见侧：
privatebooleaninside（Pointpoint,Point[]edge）{//判断点是否在裁剪边的可见侧
//裁剪边为窗口下边
if（（edge[0].y==edge[1].y）&&（edge[0].xif（point.y>=edge[0].y）{
returntrue;
}
}
//裁剪边为窗口上边
if（（edge[0].y==edge[1].y）&&（edge[0].x>edge[1].x））{
if（point.y<=edge[0].y）{
returntrue;
}
}
//裁剪边为窗口右边
if（（edge[0].x==edge[1].x）&&（edge[0].yif（point.x<=edge[0].x）{
returntrue;
}
}
//裁剪边为窗口左边
if（（edge[0].x==edge[1].x）&&（edge[0].y>edge[1].y））{
if（point.x>=edge[0].x）{
returntrue;
}
}
returnfalse;
}
直线段与窗口边界求交：
privatePointintersect（Points,Pointp,Point[]edge）{//直线段与窗口边界求交，并返回交点
Pointt=newPoint（）;
if（edge[0].y==edge[1].y）{//水平裁剪边
t.y=edge[0].y;
t.x=s.x+（edge[0].y-s.y）*（p.x-s.x）/（p.y-s.y）;
}elseif（edge[0].x==edge[1].x）{//垂直裁剪边
t.x=edge[0].x;
t.y=s.y+（edge[0].x-s.x）*（p.y-s.y）/（p.x-s.x）;
}
returnt;
}
鼠标的监听类（内部类）：
classMouseMonitorextendsMouseAdapter{//通过鼠标的单击获取点，并画出直线或者多边形
publicvoidmouseClicked（MouseEvente）{
points.add（e.getPoint（））;
if（points.size（）>1）{
draw（）;
}
}
}
键盘的监听类（内部类）：
classKeyMonitorextendsKeyAdapter{//键盘控制
publicvoidkeyPressed（KeyEvente）{
switch（e.getKeyCode（））{
caseKeyEvent.VK_R:
//清空画布和点集
panel.repaint（）;
points.removeAll（points）;
break;
caseKeyEvent.VK_W:
//对裁剪窗口的处理
g.setColor（Color.RED）;
g.drawRect（XL,YB,XR-XL,YT-YB）;
//存放裁剪窗口的边
top=newPoint[2];//存放裁剪窗口的上边
top[0]=newPoint（XL,YB）;
top[1]=newPoint（XR,YB）;
right=newPoint[2];//存放裁剪窗口的右边
right[0]=newPoint（XR,YB）;
right[1]=newPoint（XR,YT）;
bottom=newPoint[2];//存放裁剪窗口的下边
bottom[0]=newPoint（XR,YT）;
bottom[1]=newPoint（XL,YT）;
left=newPoint[2];//存放裁剪窗口的左边
left[0]=newPoint（XL,YT）;
left[1]=newPoint（XL,YB）;
break;
caseKeyEvent.VK_A:
//对直线段进行裁剪
g.setColor（Color.GREEN）;
Pointp1=points.get（0）;
Pointp2=points.get
（1）;
lineCut（p1.getX（）,p1.getY（）,p2.getX（）,p2.getY（））;
break;
caseKeyEvent.VK_B:
//对多边形进行裁剪
source=newPoint[points.size（）];//得到多边形的点
for（inti=0;isource[i]=points.get（i）;
}
g.setColor（Color.GREEN）;
wT=cutPicture（source,top）;//得到多边形与裁剪窗口上边的交点
wR=cutPicture（wT,right）;//得到多边形与裁剪窗口右边的交点
wB=cutPicture（wR,bottom）;//得到多边形与裁剪窗口下边的交点
wL=cutPicture（wB,left）;//得到多边形与裁剪窗口左边的交点
intlength=wL.length;//得到剪裁后的顶点集合,并画出图形
for（intj=0;jintx1=wL[j].x;
inty1=wL[j].y;
intx2=wL[j+1].x;
inty2=wL[j+1].y;
g.drawLine（x1,y1,x2,y2）;
}
intx1=wL[0].x;
inty1=wL[0].y;
intx2=wL[length-1].x;
inty2=wL[length-1].y;
g.drawLine（x1,y1,x2,y2）;
break;
default:
;
}
}
}
实验数据
一、直线段裁剪算法的结果显示：
（1）运行程序，点击“W”键，显示出裁剪窗口，用鼠标在画布上点击两点作为直线段的起点和终点，点击“A”键，进行直线段的裁剪，进行下一次的线段裁剪时，点击“R”键进行画布的清除，再重复上述过程进行实验：
第一种情况：
线段在裁剪窗口的外部，线段完全不可见。
第二种情况：
线段在裁剪窗口的内部，线段完全可见。
裁剪后：
第三种情况：
线段部分在裁剪窗口的内部，部分在裁剪窗口的外部，线段部分可见。
裁剪后：
二、多边形裁剪的结果显示：
与直线裁剪操作方式不同的是：
在裁剪时点击“B”键进行裁剪。
裁剪后：
实验总结
通过本次实验，让我理解并掌握了直线裁剪和多边形裁剪的算法，并成功编写了测试程序进行实验。
在本次实验中，有如下两点说明：
（1）通过编写鼠标监听类简化了对输入点的处理，我们可以通过在画布上点击要画的直线或者多边形的顶点来进行程序的输入，而不需要在窗口中输入点的坐标值，简化了操作，而且直接在画布上点击也比较直观，不必去想要输入那几个点才能构成多边形，输入的点构成的直线和多边形是否符合实验的需求（即与裁剪窗口的位置关系）。
（2）本次实验的不足在于没有能实现裁剪窗口的任意化，实验的裁剪窗口只局限于矩形窗口，算法缺少普适性。
指导教师意见
签名：
年月日
升级会员 