多边形的区域填充.pdf
佛山科学技术学院实验报告课程名称计算机图形学实验实验项目多边形的区域填充专业班级姓 名学 号指导教师成 绩日 期一、实验目的一、实验目的1.通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理2.掌握多边形区域填充算法的基本过程3.掌握在 C/C+环境下用多边形填充算法编程实现指定多边形的填充。二、实验内容二、实验内容用种子填充算法和扫描线填充算法等任意两种算法实现指定多边形的区域填充。三、实验原理三、实验原理扫描线算法原理：（1）求交：计算扫描线与多边形各边的交点。（2）排序：把所有交点按 x 值递增顺序排序。（3）配对：第一个与第二个，第三个与第四个等，每对交点代表扫描线与多边形的一个相交区间。（4）填色：把相交区间内的像素置成多边形颜色，把相交区间外的像素置成背景色。种子填充算法原理：1 初始化：确定种子点元素（x，y）。2 判断种子点（x，y）是否满足非边界、非填充色的条件，若满足条件，以 y 作为当前扫描线沿当前扫描线向左、右两个方向填充，直到边界。3 确定新的种子点：检查与当前扫描线 y 上、下相邻的两条扫描线上的像素。若存在非边界、未填充的像素，则返回 步骤 2 进行扫描填充。直至区域所有元素均为填充色，程序结束。四、实验步骤四、实验步骤1.复习有关算法，明确实验目的和要求；2.依据算法思想，绘制程序流程图（指定填充多边形）；3.设计程序界面，要求操作方便；4.用 C/C+语言编写源程序并调试、执行（最好能用动画显示填充过程）；5.分析实验结果6.对程序设计过程中出现的问题进行分析与总结；五、实验结果及分析五、实验结果及分析X-扫描线算法，在处理每条扫描线是，需要与多边形的所有变交，这样处理效率很低，而改进后的有效边表算法，利用区间的连贯性，用一条指令填充区间上若干连续像素，提高了算法效率。用 4 邻接点边界填充算法在没有改进前，因为要大量元素的进栈，会是栈溢出，在改进后，利用扫描线算法，进行两点区间的填充，只需把每个连续像素段的最左像素取作种子像素进栈就行了，大大降低溢出的发生。六、实验主要代码六、实验主要代码扫描线构造边表，对边表进行排序，构造活性边表对每条扫描线对应的活性边表求交点判断交点类型，并两两配对对符合条件的交点之间用画线方式填充下一条扫描线，是否结束void CDuobianxingView:OnScan()结束/TODO:Add your command handler code hereCDC*pDC=GetDC();CPen newpen(PS_SOLID,1,RGB(0,255,0);CPen*old=pDC-SelectObject(&newpen);int j,k,s=0;int p6;/每根扫描线交点int pmin=spt0.y,pmax=spt0.y,CPoint;for(int i=1;i7;i+)if(pmaxspti.y)pmin=spti.y;for(i=0;i7;i+)/建立 7 条边表edgei.dx=(float)(spti+1.x-spti.x)/(spti+1.y-spti.y);/斜率倒数 1/kif(spti.y=spti+1.y)/一条边的 Y 最大值edgei.num=i;/第 i 条扫描线edgei.ymin=spti.y;edgei.ymax=spti+1.y;edgei.xmin=(float)spti.x;edgei.xmax=(float)spti+1.x;elseedgei.num=i;edgei.ymin=spti+1.y;edgei.ymax=spti.y;edgei.xmax=(float)spti.x;edgei.xmin=(float)spti+1.x;for(int r=1;r7;r+)/排序 edge(yUpper，xIntersect)7 条边表冒泡for(int q=0;q7-r;q+)if(edgeq.yminpmin+1;scan-)/纵向 Y 的每一条边从 Y 最大值到最小值，不扫描最高和最低int b=0;k=s;for(j=k;jedgej.ymin)&(scan=edgej.ymax)/判断与线段相交扫描先与线段相交if(scan=edgej.ymax)if(sptedgej.num+1.yedgej.ymax)b+;pb=(int)edgej.xmax;if(sptedgej.num-1.yedgej.ymin)&(scanedgej.ymax)b+;pb=(int)(edgej.xmax+edgej.dx*(scan-edgej.ymax);if(scan1)for(int u=1;uMoveTo(pu+3,scan);u+;pDC-LineTo(pu,scan);pDC-SelectObject(old);种子填充算法：确定种子节点（，）定义最大边界的,Ymax 和最小边界 Yminno（，）是否在满足填充条件no以当作当前扫描线向左右填充到边界y，y=Ymaxyy-1y=Ymin结束void CDuobianxingView:OnSeed()/TODO:Add your command handler code hereCClientDC dc(this);int fill=RGB(0,255,0);int boundary=RGB(255,0,0);int current;CPoint pt=s_point;int x,y,pmin,pmax;CPoint p0;/求多边形的最大最小值 pmax=spt0.y;pmin=spt0.y;for(int i=1;i7;i+)if(pmaxspti.y)pmin=spti.y;x=s_point.x;/种子节点y=s_point.y;dc.TextOut(s_point.x,s_point.y,xiaopinhai);for(;ypmin-1;y-)/向下扫描 current=dc.GetPixel(x,y);while(current!=boundary)&(current!=fill)/向右扫描dc.SetPixel(x,y,fill);x+;current=dc.GetPixel(x,y);x=s_point.x;x-;current=dc.GetPixel(x,y);while(current!=boundary)&(current!=fill)/向左扫描dc.SetPixel(x,y,fill);x-;current=dc.GetPixel(x,y);x=s_point.x;
