实验报告5 多边形裁剪与填充要点Word格式.docx
《实验报告5 多边形裁剪与填充要点Word格式.docx》由会员分享，可在线阅读，更多相关《实验报告5 多边形裁剪与填充要点Word格式.docx（28页珍藏版）》请在冰点文库上搜索。
（2）多边形的表示：
1）顶点表示是用多边形的顶点的序列来描述多边形，该表示几何意义强、占内存少，但它不能直观地说明哪些像素在多边形内。
2）点阵表示是用位于多边形内的象素的集合来刻划多边形，该方法虽然没有多边形的几何信息，是面着色所需要的图像表示形式。
算法设计：
1多边形的裁剪：
Sutherland-Cohen算法:
基本思想：
对于每条线段P1P2分为三种情况处理。
（1）若P1P2完全在窗口内，则显示该线段P1P2简称“取”之。
（2）若P1P2明显在窗口外，则丢弃该线段，简称“弃”之。
（3）若线段既不满足“取”的条件，也不满足“弃”的条件，则在交点处把线段分为两段。
其中一段完全在窗口外，可弃之。
然后对另一段重复上述处理。
具体操作：
分为两步
第一步是判定：
1）完全在窗口内的直线段，称为完全可见的线段；
2）完全在窗口外的线段，称为完全不可见线段。
第二步处理不能断定为完全可见或完全不可见的线段。
这时需要计算出直线段和窗口边界的一个交点，这个交点把直线分成两段，其中一条为完全不可见的线段,被抛弃。
对余下部分再作第一步的判断，重复上述过程，直到直线段余下的部分可用第一步的判断得出肯定的结论为止。
（1）多边形填充的扫描线算法
a.令y=c为一个常数，扫描整个多边形的边，记录横坐标为xi记为序列1.
b.设d为一整数，d=c–1，且yi0≥y≥yin；
设位于扫描线y=d上的交点序列为，记为序列2。
c.奇点的处理:
多边形P的顶点可分为两类：
极值点和非极值点。
如果
，
称顶点Pi为极值点（P1,P2,P3,P5,P6,P8）；
否则称Pi为非极值点（P0,P4,P7）。
若扫描线与多边形相交于多边形的顶点，则该交点（顶点）称为奇点。
为了使交点个数保持为偶数，规定当奇点是P的极值点时，该点按两个交点计算；
否则按一个交点计算。
（2）边缘填充算法:
对多边形P的每一非水平边上的各像素做向右求反运算即可。
步骤：
a.以值为boundary-color的特殊颜色勾画多边形P的边界。
设多边形顶点为Pi=（xi,yi）,0≤i≤n，xi,yi均为整数；
置Pn+1=P0。
每一条扫描线上着上这种特殊颜色的点的个数必定是偶数（包括零）。
b.设interior_point是一布尔变量。
对每一条扫描线从左到右进行搜索，如果当前是像素位于多边形P内，则interior_point=true，需要填上值为polygon_color的颜色；
否则该像素在多边形P外，需要填上值为background_color的颜色。
（3）区域填充:
a.区域是指已经表示成点阵形式的像素集合。
在光栅图形中，区域可采用内点表示和边界表示两种形式进行描述。
内点表示法：
把位于给定区域内的所有像素一一列举出来的方法称为内点表示法。
边界表示法：
把位于给定区域边界上的像素一一列举出来的方法称为边界表示法。
b.区域的连通性:
1）连通的区域:
取区域内任意两点，在该区域内若从其中一点出发通过上、下、左\右四种运动可到达另一点。
2）连通的区域:
取区域内任意两点，若从其中任一点出发，在该区域内通过沿水平方向、垂直方向和对角线方向的八种运动可到达另一点。
（4）扫描线种子填充算法:
从给定的种子点开始，填充当前扫描线上种子点所在的一区段，然后确定与这一段相邻的上下两条扫描线上位于区域内的区段（需要填充的区间），从这些区间上各取一个种子点依次把它们存起来，作为下次填充的种子点。
反复进行这过程，直到所保存的各区段都填充完毕。
a.（初始化）将算法设置的堆栈置为空。
将给定的种子点（x,y）压入堆栈
b.（出栈）如果堆栈为空，算法结束；
否则取栈顶元素（x,y）作为种子点
c.（区段填充）从种子点（x,y）开始，沿纵坐标为y的当前扫描线向左右两个方向逐个像素
用新的颜色值进行填充，直到边界为止即象素颜色等于边界色。
设区间两边界的横坐标分别
为xleft和xright。
d.在与当前扫描线相邻的上下两条扫描线上，以区间[xleft,xright]为搜索范围，求出需要填
充的各小区间，把各小区间中最右边的点并作为种子点压入堆栈，转到步骤2。
代码：
publicintcode（floatx,floaty）
{
intc=0;
if（x<
xL）c=c|1;
elseif（x>
xR）c=c|2;
if（y<
yB）c=c|4;
elseif（y>
yT）c=c|8;
returnc;
//二进制分别为01101001000
}
//Sutherland_Cohen裁减算法
publicvoidSutherland_Cohen（Graphicsg,floatx0,floaty0,floatx2,floaty2）
intc1,c2,c;
floatx,y,wx,wy;
booleanaccept=false,done=false;
c1=code（x0,y0）;
c2=code（x2,y2）;
do{
if（（c1|c2）==0）//两个编码都为0，表明在窗口内
accept=true;
done=true;
elseif（（c1&
c2）!
=0）done=true;
//两个编码的某一位为1，则必然在外侧显然在窗口外
else
c=c1;
if（c==0）c=c2;
wx=x2-x0;
wy=y2-y0;
if（（c&
8）==8）//求交点
{
x=x0+wx*（yT-y0）/wy;
y=yT;
}
elseif（（c&
4）==4）
x=x0+wx*（yB-y0）/wy;
y=yB;
1）==1）
y=y0+wy*（xL-x0）/wx;
x=xL;
}else//即（c&
2）==2
y=y0+wy*（xR-x0）/wx;
x=xR;
if（c==c1）//表明c1!
=0,起始点不在窗口内，将交点作为新的起点重复判断步骤；
x0=x;
y0=y;
c1=code（x0,y0）;
}else//终点不在窗口内，交点作为新的终点
x2=x;
y2=y;
c2=code（x2,y2）;
}//else
}while（done==false）;
if（accept）g.drawLine（（int）x0,（int）y0,（int）x2,（int）y2）;
2多边形的填充：
classactiveEdgeList{
activeEdgeListEntryheader=null;
activeEdgeListEntrytailer=null;
publicactiveEdgeList（activeEdgeListEntryelement）{
header=tailer=element;
//指向第一个边结点
//把新结点插入有序排列的多边形单链表
publicvoidinsert（activeEdgeListEntryelement）{
activeEdgeListEntrysentinel;
if（element==null||this.header==null）//新结点异常或者链表空
thrownewNullPointerException（）;
//出错，抛出异常
sentinel=this.header;
//当前指针指向表头结点
intxt=element.topx;
//新结点的topx
intxtold=sentinel.topx;
doubleoldDelta=sentinel.delta;
//当前结点的delta
doublenewDelta=element.delta;
/*排序第一关键字结点的topx，第二关键字结点的delta*/
/*两个关键字由小到大*/
if（（xtold<
xt）||（（xtold==xt）&
&
（oldDelta<
newDelta）））{
while（true）{//在链表头指针之后寻找新结点element的位置
if（sentinel.next==null）{
sentinel.next=element;
//追加到表尾
this.tailer=element;
break;
//结束while循环
}
activeEdgeListEntrymp=sentinel.next;
//下一结点
intxmt=mp.topx;
doublemidDelta=mp.delta;
if（（xmt<
xt）||（（xmt==xt）&
（midDelta<
sentinel=mp;
//新结点仍然大于下一结点，当前结点指针后移，继续循环
else{//否则，新结点就应该插入当前位置
element.next=mp;
//结束while循环，尾指针不动
}
}
else{//新结点作为单链表头结点
sentinel=this.header;
this.header=element;
element.next=sentinel;
}//插入新结点结束
//把新结点作为多边形链表的头结点或者尾结点
publicvoidappend（activeEdgeListEntryelement）{
if（element==null）thrownewNullPointerException（）;
if（tailer==null）{//如果单链表是空
tailer=element;
header=element;
else{//否则把新结点作为单链表尾结点
tailer.next=element;
tailer=element;
//两个多边形单链表的合并：
自身单链表与list单链表的合并
publicactiveEdgeListmerge（activeEdgeListlist,inty）{
if（list==null）returnthis;
activeEdgeListEntrya=this.header;
//自身单链表的头指针
activeEdgeListEntryb=list.header;
//单链表list的头指针
activeEdgeListEntrysave=null;
//指向链表结点的工作指针
activeEdgeListEntryanext,bnext;
activeEdgeListresult=null;
//合并结果链表
while（true）{
if（a==null&
b==null）returnresult;
//两个空表
elseif（a==null）{//自身为空表
if（save!
=null）{
save.next=b;
result.tailer=list.tailer;
returnresult;
}
}
elseif（b==null）{//list为空表
if（save!
=null）{
save.next=a;
result.tailer=this.tailer;
returnresult;
}
/*两个表都不空*/
intxa=（int）（a.topx+（a.topy-y）*a.delta）;
//自身链表
intxb=b.topx;
//list链表头结点的topx
if（xa<
=xb）{//决定合并后两个表的先后
anext=a.next;
a.next=null;
if（result==null）{//结果链表为空，则a表在前
result=newactiveEdgeList（a）;
save=result.tailer;
elseresult.append（a）;
//结果链表不空，则a表在后
save=a;
a=anext;
}
else{
bnext=b.next;
b.next=null;
if（result==null）{//结果链表为空，则b表在前
result=newactiveEdgeList（b）;
elseresult.append（b）;
//结果链表不空，则b表在后
save=b;
b=bnext;
}//结束while
}//单链表合并结束
//删除多边形单链表的结点
publicvoidremove（activeEdgeListEntryelement）{
activeEdgeListEntryp,q;
if（header==element）{//要删除的是头结点
header=element.next;
if（tailer==element）tailer=header;
return;
p=q=header;
while（p!
=element）{
q=p;
p=p.next;
if（p==null）thrownewNullPointerException（）;
//查无此结点
if（element==tailer）tailer=q;
//要删除的是尾结点
q.next=p.next;
//要删除的是非头尾结点
//多边形单链表的相邻结点
publicvoidtraverse（）{
activeEdgeListEntryp,q,r,tmp;
p=r=header;
=null）{
q=p.next;
if（q==null）break;
//到达末尾
if（q.x<
p.x）{//多边形单链表相邻结点的x坐标要由小到大
tmp=q.next;
//交换两个结点
if（p==header）header=q;
elser.next=q;
q.next=p;
p.next=tmp;
r=p;
//指向尾结点
p=p.next;
//下一个结点
tailer=r;
//多边形单链表新的尾指针
}//结束多边形单链表类
//*****定义直线类
classLine{
publicdoublex1,y1;
publicdoublex2,y2;
publicLine（doublex1,doubley1,doublex2,doubley2）{
this.x1=x1;
this.y1=y1;
this.x2=x2;
this.y2=y2;
}//结束直线类
//***********定义多边形的填充类*******//
publicclassfillPolygonextendsApplet//继承鼠标事件监听接口
implementsMouseListener,MouseMotionListener{
protectedMyCanvasm;
//定义MyCanvas的对象
//扫描行处理用数据
protectedactiveEdgeListEntry[]edgeData=null;
//边结点数组
protectedactiveEdgeList[]bucket=null;
//多边形单链表数组
protectedactiveEdgeListactiveHeader=null;
//当前边单链表的头指针
protectedintnumEdge=0;
//多边形的边数
//鼠标相关数据
protectedbooleanisFirstClicked=true;
//鼠标最初点击
protectedbooleanisDoubleClicked=false;
//双击标志
protectedbooleanisSingleClicked=false;
//单击标志
//绘图区域
protectedintwidth,height;
//Applet绘图区的大小
protectedImageimage=null;
//图像区域
protectedMemoryImageSourcemis=null;
//内存图像
protectedint[]pixel=null;
//内存图像配色数组
protectedintpixelWidth;
//图像宽度
protectedintpixelHeight;
//图像高度
protectedintxoffset;
//pixel数据的窗口内显示偏移量
protectedintyoffset;
protecteddoubleleftTopx;
//pixel数据的起始点
protecteddoubleleftTopy;
//多边形的绘图数据
protecteddoublex0,y0;
//边的起点
protecteddoublelastx,lasty;
//边的终点位置
protecteddoublemovingx,movingy;
//用户坐标系下一个点的坐标
protectedintnumPoints=0;
//顶点计数器
protectedbooleanisPolygonMode=true;
//标志
protectedVectorlines=newVector（256,256）;
//Java的向量类
//APPLET程序的初始化
publicvoidinit（）{
m=newMyCanvas（this）;
//本APPLET容器的MyCanvas对象
addMouseListener（this）;
//定义鼠标按钮监听器
addMouseMotionListener（this）;
Dimensiond=getSize（）;
//本APPLET容器的大小
width=d.width;
height=d.height;
//成员变量初始化
publicvoidinitData（）{
isFirstClicked=true;
isPolygonMode=true;
//标志描绘多边形
numPoints=0;
//多边形顶点计数器
bucket=newactiveEdgeList[height+1];
//边的单链表数组
for（inti=0;
i<
height+1;
i++）bucket[i]=null;
if（lines.size（）>
0）lines.removeAllElements（）;
//向量类的对象
//APPLET程序的绘图
publicvoidpaint（Graphicsg）{
if（isFirstClicked）{//初始状态
initData（）;
Fontf=m.MyFont（m.getFont（）.getName（）,Font.BOLD+Font.ITALIC,1.5）;
m.setFont（f）;
m.drawString（"
单击画多边形"
-0.5,0.2）;
双击填充多边形"
-0.9,-0.15）;
m.setBackground（newColor（220,220,220））;
//背景色
m.setColor（Color.black）;
//前景色
lines.size（）;
i++）{
Linel=（Line）lines.elementAt（i）;
//转换第i个向量
m.drawLine（l.x1,l.y1,l.x2,l.y2）;
if（isP
升级会员 