计算机图形学 区域填充算法的实现

}
} /* polyfill */
桶结构
用于存放按照一定的规则（顺序）排列的若 干组数据或处理对象。
通常情况下，桶采用向量形式和链表形式构 造的一种数据结构。
6．边界标志算法
边界标志算法的基本思想是：在帧缓冲器中 对多边形的每条边进行直线扫描转换，亦即对多 边形边界所经过的象素打上标志。然后再采用和 扫描线算法类似的方法将位于多边形内的各个区 段着上所需颜色。对每条与多边形相交的扫描线 依从左到右的顺序，逐个访问该扫描线上的象素。 使用一个布尔量inside来指示当前点是否在多边形 内的状态。Inside的初值为假，每当当前访问的 象素为被打上边标志的点，就把inside取反。对未 打标志的象素，inside不变。若访问当前象素时， inside为真，说明该象素在多边形内，则把该象素 置为填充颜色。
扫描线6的活性边表 扫描线7的活性边表
为了方便活性边表的建立与更新，我们为 每一条扫描线建立一个新边表（NET）,存放 在该扫描线第一次出现的边。也就是说，若 某边的较低端点为ymin，则该边就放在扫描 线ymin的新边表中。
扫描线多边形填充算法的主要步骤
▪ 建立NET(NewEdgeList) ▪ 从最低扫描线开始到最高扫描线循环： ➢ 建立或调整AET(ActiveEdgeList)； ➢ 按照AET中的接点顺序填充；
准备工作： typedef struct { int x,y;} seed; typedef struct { seed s[6400];int top;} seedstack;
VC++程序实现
可以直接利用函数的递归调用来实现.
设（x,y）为内点表示的4连通区域内的一点， oldcolor为区域的原色，要将整个区域填充为新 的颜色newcolor。

CFill.cpp参考代码：
// Fill.cpp : implementation file
#include "stdafx.h"
#include "FloodFill.h"
#include "Fill.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
（1）种子填充算法原理
在多边形内部找到一个已知的象素点作为种子点，由此开始，利用区域的连通性找到多边形内部的 其它所有象素点进行填充。
（i）四向连通区域
①四向连通区域概念：从区域上任一点出发，在不超出区域边界的前提下，可通过4个方向：上、下、左、右的移动组合到达区域中的任意象素点，称此区域为四向连通区域。
{
//有需要填充的区域
if(spanNeedFill==FALSE)
{
spanNeedFill = TRUE;
}
x++;
}
if(spanNeedFill)
{
CPoint rightp(x-1,y);
stack.Push(x-1);
stack.Push(y);
spanNeedFill = FALSE;
virtual ~CStack();
};
#endif // !defined(AFX_STACK_H__D198F788_4ED1_4C09_98E5_433BAB24D864__INCLUDED_)
CStack.cpp参考代码：
// Stack.cpp: implementation of the CStack class.
#if !defined(AFX_STACK_H__D198F788_4ED1_4C09_98E5_433BAB24D864__INCLUDED_) #define AFX_STACK_H__D198F788_4ED1_4C09_98E5_433BAB24D864__INCLUDED_

初始化每条扫面线的边链表 */
/*
建“桶” */
edges[scan]->next=NULL;
}
BuildEdgeList(cnt,pts,edges);
/*
建立有序边表 */
active=(Edge *)malloc(sizeof(Edge));
active->next=NULL;
for(scan=scanmin;scan<=scanmax;scan++) /* 扫描每条扫描线， 求活性表 */
当多边形新边表 ET构成后，按下列步骤进行： ① 对每一条扫描线 i ，初始化 ET表的表头指针 ET[i] ； ② 将 ymax = i 的边放入 ET[i] 中； ③ 使 y = 多边形最低的扫描线号； ④ 初始化活性边表 AET为空； ⑤ 循环，直到 AET和 ET 为空。
将新边表 ET 中对应 y 值的新边节点插入到 AET表。 遍历 AET表，将两两配对的交点之间填充给定颜色值。 遍历 AET表，将 ymax= y 的边节点从 AET表中删除，并将 ymax> y 的各边节点 的 x 值递增 Δx；并重新排序。 y 增加 1。
/* 建立扫描线 scan 的活性边表 , 把活性边结点放入扫描线 scan 的结点指针数组
edges[scan] 中*/
{
Edge *p,*q;
p=edges[scan]->next;
/*
查找当前扫描线对应的 y 桶*/
while(p)
/*y
桶不空 */
{q=p->next;
/*
找到最后一个边结点， 插入 */
*edges[])
/* 把边结点 edge, 放到 lower.y 扫描线所在的边结点指针数组 edges[] 中 */

实验四区域填充算法的实现班级 08信计2班学号 20080502088 姓名许延恒分数一、实验目的和要求：1、理解区域的表示和类型。

2、能正确区分四连通和八连通的区域3、了解区域填充的实验原理。

4、利用C++实现区域填充的递归算法。

二、实验内容：1假设在多边形内有一像素已知，由此出发利用连通性找到区域内所有像素。

2 取（x，y）为种子点将整个区域填充为新的颜色。

3 进行递归填充。

三、实验结果分析区域填充属性包括填充样式，填充颜色和填充图案的类型。

C语言中定义了某种图形后，即可调用-floodfill函数，对指定区域进行填充. 程序代码#include<graphics.h>#include<conio.h>#include<time.h>void floodfill4(int x,int y,int oldcolor,int newcolor){if(getpixel(x,y)==oldcolor){putpixel(x,y,newcolor);Sleep(1);floodfill4(x,y+1,oldcolor,newcolor);floodfill4(x,y-1,oldcolor,newcolor);floodfill4(x-1,y,oldcolor,newcolor);floodfill4(x+1,y,oldcolor,newcolor);}}main(){int a,b,c,d,i,j;int graphdriver=DETECT;int graphmode=0;initgraph(&graphdriver,&graphmode,"");cleardevice();setcolor(RED); rectangle(50,50,70,100); for(i=51;i<70;i++)for(j=51;j<100;j++) {putpixel(i,j,4);}a=57;b=70;c=4;d=RGB(0,255,0); floodfill4(a,b,c,d); getch();closegraph();}。

{
b++;
p[b]=(int)edge[j].xmax;
}
}
if((scan>edge[j].ymin)&&(scan<edge[j].ymax))
{
b++;
p[b]=(int)(edge[j].xmax+edge[j].dx*(scan-edge[j].ymax));
}
}
//pDC->LineTo(spt[edge[0].num].x,spt[edge[0].num].y);
4.用C/C++语言编写源程序并调试、执行（最好能用动画显示填充过程）；
5.分析实验结果
6.对程序设计过程中出现的问题进行分析与总结；
7.打印源程序或把源程序以文件的形式提交；
8.按格式要求完成实验报告。
五、实验结果及分析
种子填充算法的优点是非常简单，缺点是需要大量栈空间来存储相邻的点。扫描线填充算法就是它的改进的方法。它是通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。
if(spt[i].y > pmax)
pmax = spt[i].y;
if(spt[i+1].y < pmin)
pmin = spt[i+1].y;
}
}
for(int r=1;r<=6;r++)//排序edge(yUpper，xIntersect)，结果为从大到小
{
for(int q=0;q<=6-r;q++)

计算机图形学四连通区域种子填充算法实验————————————————————————————————作者: ————————————————————————————————日期:ﻩ《计算机图形学实验》报告任课教师:钱文华2０16年春季学期实验:四连通区域种子填充算法实验时间：201６年12月8日实验地点：信息学院22０4实验目的：掌握种子填充算法的原理，并会用种子填充算法和opｅｎｇl并结合使用ｃ+＋语言编写程序绘制多边形。

实验原理:种子填充算法又称为边界填充算法。

其基本思想是:从多边形区域的一个内点开始，由内向外用给定的颜色画点直到边界为止。

如果边界是以一种颜色指定的,则种子填充算法可逐个像素地处理直到遇到边界颜色为止。

内点的检测条件：ｉf(iｎｔerｉoｒCｏloｒ!=bo ｒｄerCoｌor&&interｉorColoｒ!＝ｆiｌlCｏlｏr）。

种子填充算法常用四连通域和八连通域技术进行填充操作。

从区域内任意一点出发，通过上、下、左、右四个方向到达区域内的任意像素。

用这种方法填充的区域就称为四连通域;这种填充方法称为四向连通算法。

从区域内任意一点出发,通过上、下、左、右、左上、左下、右上和右下八个方向到达区域内的任意像素。

用这种方法填充的区域就称为八连通域；这种填充方法称为八向连通算法。

一般来说，八向连通算法可以填充四向连通区域,而四向连通算法有时不能填充八向连通区域。

四向连通填充算法:a）种子像素压入栈中;b)如果栈为空,则转e）；否则转c）;c) 弹出一个像素,并将该像素置成填充色;并判断该像素相邻的四连通像素是否为边界色或已经置成多边形的填充色，若不是,则将该像素压入栈;d)转b）;ｅ）结束。

四连通填充算法利用到了递归的思想。

本实验只包括四连通填充算法程序代码:#ｉncludｅ<ｇlut.h>＃ｉｎｃlｕde<ｓtdｌib．h>＃ｉncｌudｅ<math．h>#include<ｗindowｓ.h＞voidｉniｔ（vｏid）{ glCｌearColor(１．０，１.0,1．0,0.０）；glMatrixMoｄｅ（ＧL_PROJＥCTION）;gｌｕOrtho２D（０．0，30０．0，０.0,30０.0);}voｉd setPixel(inｔx，ｉnｔy,lｏｎｇｆillCoｌor）{ ｇlColor3f（fｉllCoｌoｒ<<16,filｌCoｌor<<８,fillCｏloｒ)；ｇlＢｅgin（ＧL_ＰＯINTＳ);ｇlＶｅｒteｘ2i（x,y）;ｇlEnｄ();}ｖｏｉｄboundaryFill４(iｎt x,ｉnｔy,lｏng fillＣolor,lｏng bordeｒColor）{ unｓｉgneｄchａr paｒams[3];loｎg interioｒCoｌoｒ;glRｅaｄPixels(ｘ，y,1,1,GL_RGB,GＬ＿UNSIＧNＥD_BYＴE,par ａms）;interiorCoｌoｒ=RGB(paraｍs[0],ｐarａms[１］,paｒaｍs[2])；ｉf(inteｒiorＣolor!=boｒderCｏloｒ＆＆inteｒiｏrCoｌｏr!=filｌColor){ setＰixeｌ(x，ｙ,fｉｌlCoｌｏr);ｂoundaryFill4（x＋1,y,filｌＣoｌｏr,ｂordeｒCｏlor);ｂｏunｄaｒyＦｉｌl4(ｘ-1，y，fiｌlＣolor,borderColor); boundaryFilｌ４(x,ｙ+1,ｆｉlｌColｏr,borｄeｒCoｌor)；ｂounｄarｙFill4(x，y-1，ｆｉllColｏr，ｂorｄerＣolor);} }voiｄlineＳegment(voｉd) {long bｏrｄerCｏｌoｒ=RGB（255，0,０);lｏngｆiｌlColoｒ=RGB（０，0，255）;glClｅar（ＧL_COＬOR＿BUFFER_BIT); glCｏloｒ３ｆ(２55，0,0); ｇlＢegｉn（GL_ＬINE＿ＬＯＯP);glVeｒtex2ｉ(0,４0);glVｅｒteｘ2i(2０,0);glＶertex２i(６0,0）；glＶeｒtｅx2ｉ(80，4０）;ｇlVｅｒtex2i(６0,80);gｌVertex２i(20,80);gｌＥnd();boundaryＦill4(６０,60，ｆｉllＣolor,ｂorderColｏr)；gｌFlush()；}voｉｄmain(ｉｎt argc,chａr＊*aｒgv）｛ｇlutIｎｉｔ(&ａr ｇc,aｒｇv);glｕtInitDｉsｐｌaｙMode(GLUＴ＿ＳＩNGLE｜GLUT_ＲGB); glutInitＷindowPｏsiｔion（1５0,10０）;gluｔIｎitWinｄoｗSizｅ(300,３0０）;glutＣreateＷｉｎdow（"种子填充"）；init();glutDisｐlayFｕｎｃ(lｉneＳegｍeｎt);gｌｕtMａinＬｏoｐ(）;}上实验课时机房的实验结果:后来的实验结果:glVｅrteｘ2i（0,40);gｌＶerteｘ２i（20，0);glVerｔex2i（60,０);glVerteｘ2i（８0，４０);gｌＶertｅx2ｉ(60，80);ｇlＶerteｘ2i(２0,80)；ｇlEnｄ();ｂｏｕndaryFｉlｌ4(60,60，ｆｉlｌCｏlor,ｂorderＣoｌor）；以上这段程序改成如下glVerｔex2ｉ(９0，40);glVｅrtｅx２i（１2０, １00）;ｇlVertex2i(90,1６0);glVertｅｘ２i(60, 160);ｇlVertex2i(60, ４０);glEnd()；bouｎｄaryFilｌ4(７0,6０,fiｌｌCｏｌoｒ,bｏｒderCoｌor); 改变参数后：再把ｇlVeｒｔｅx2i（9０，40);glVertｅｘ２i(120, 100）；glＶｅrｔex2i(90,160）;glＶerｔex2i(60, １6０）;glVｅrtex２i（６0, 40）;gｌＥnd（);bｏundaryFill4（70,6０,fiｌlCｏloｒ,boｒdｅrCｏlor）；改成glVeｒtex2i(100, １０0)；glVｅrteｘ2i(２00, 100);gｌVｅｒteｘ2ｉ(1５0,150);/／glVｅrteｘ2ｉ(60, 1６0);／/glVertｅx2i(6０, 40)；glＥnd();ｂoundaryFill4(150，1２0,fiｌlCｏlor，borｄerCoｌoｒ);后的结果如下图:实验总结:通过多组数据的测试，知道了上面算法的正确,普适性。

40
种子填充算法

栈实现的种子填充算法(四向算法)
void BoundaryFill4(int x, int y, int boundColor, int newColor) { int px = x, py = y; stackPush(px, py); while(!stackEmpty()) { stackPop(&px, &py); SetPixel(x, y, newColor);

扫描转换算法
区域填充算法
34
种子填充算法

区域：点阵表示的图形，像素集合 表示方法


内点表示 区域内的所有像素具有同一颜色，而区域外的所有像素具有另 一种颜色 边界表示 区域边界上的所有像素具有特定的颜色（可以是填充色），在 区域内的所有像素均不能具有这一特定颜色，而且边界外的像 素也不能具有与边界相同的颜色

若低端点y值为ymin，则该边就放在ymin所对应的桶中

桶中的各边：
按下端点的x坐标值排序
27
12 10（2，9） l3 8 6 4 2 l2 l4
（13，11） l5 （13，5） l6
（7，7）
（2，3） （7，1） l1 2 4
9 11 9 3 ∧ ∧
6
8 10 12 14
7 3/2 11
扫描线算法

取整问题

扫描线与多边形边界交点坐标值不为整数 当扫描线与多边形边界交点坐标为小数值时，如果多 边形在此边界右侧，则将该小数值进1作为边界点，否 则舍去小数部分并进行填充，这样可使多边形不扩大
解决方法

16
扫描线算法

水平边问题

计算机图形学——区域填充的扫描线算法一．实验名称：区域填充的扫描线算法二．实验目的：1、理解区域填充扫描线算法的原理；2、实现区域填充的扫描线算法并测试；三．算法原理：算法基本思想: 首先填充种子点所在扫描线上位于区域内的区段，然后确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。

随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。

借助于栈结构，区域填充的扫描线算法之步骤如下：Step 1. 初始化种子点栈：置种子点栈为空栈，并将给定的种子点入栈；Step 2. 出栈：若种子点栈为空，算法结束；否则，取栈顶元素(x，y)为种子点；Step 3. 区段填充：从种子点(x, y) 开始沿纵坐标为y 的当前扫描线向左右两个方向逐像素点进行填色，其颜色值置为newcolor 直至到达区域边界。

分别以xl 和xr 表示该填充区段两端点的横坐标；Step 4. 新种子点入栈: 分别确定当前扫描线上、下相邻的两条扫描线上位于区段[xl, xr] 内的区域内的区段。

若这些区段内的像素点颜色值为newolor ,则转至Step 2；否则以区段的右端点为种子点入种子点栈，再转至Step 2。

四．原程序代码：/*****************************************//*4-ScanLineFill 区域填充的扫描线算法实现*//*****************************************/#include <stdio.h>#include <conio.h>#include <graphics.h>#include <malloc.h>#define Stack_Size 100 //栈的大小常量//定义结构体,记录种子点typedef struct{int x;int y;}Seed;//定义顺序栈(种子点)typedef struct{Seed Point[Stack_Size];int top;}SeqStack;//初始化栈操作void InitStack(SeqStack *&S){S=(SeqStack *)malloc(sizeof(SeqStack));S->top=-1;}//种子点栈置空；void setstackempty (SeqStack *S){S->top==-1;}//种子点栈状态检测函数int isstackempty (SeqStack *S){if(S->top==-1)return true; //空栈返回trueelsereturn false; //非空栈返回false}//种子点入栈；int stackpush (SeqStack *&S,Seed point){if(S->top==Stack_Size-1)//栈已满，返回false return false;S->top++;//栈未满，栈顶元素加1S->Point[S->top]= point;return true;}//取栈顶元素；int stackpop (SeqStack *&S,Seed &point){if(S->top==-1)//栈为空，返回falsereturn false;point=S->Point[S->top];S->top --;//栈未空，top减1return true;}//画圆void CirclePoints (int xc, int yc, int x, int y, int Color) {putpixel (xc + x, yc + y, Color);putpixel (xc + x, yc - y, Color);putpixel (xc - x, yc + y, Color);putpixel (xc - x, yc - y, Color);putpixel (xc + y, yc + x, Color);putpixel (xc + y, yc - x, Color);putpixel (xc - y, yc + x, Color);putpixel (xc - y, yc - x, Color); }//中点画圆算法void MidpointCircle(int radius, int Color) {int x, y;float d;x=0;y=radius;d=5.0/4-radius;CirclePoints(250,250,x,y,Color);while(x<y){if (d<0){d+=x*2.0+3;}else{d+=(x-y)*2.0+5;y--;}x++;CirclePoints(250,250,x,y,Color);}}//四连通扫描线算法void ScanLineFill4(int x, int y, int oldcolor, int newcolor) {int xl, xr, i;bool SpanNeedFill;Seed pt;//种子点SeqStack *S;//定义顺序栈InitStack(S);//定义了栈之后必须把栈先初始化setstackempty(S);//种子点栈置空；pt.x = x;pt.y = y;stackpush (S,pt); // 种子点(x, y)入栈while (!isstackempty(S)){stackpop (S,pt);//取种子点y = pt.y;x = pt.x;while (getpixel (x,y)==oldcolor) {// 从种子点开始向右填充putpixel (x, y, newcolor);x++;}xr = x -1;x = pt.x -1;while (getpixel (x,y)==oldcolor) { // 从种子点开始向左填充putpixel (x, y, newcolor);x--;}xl = x + 1;x = xl;y = y +1; // 处理上面一条扫描线while (x < xr){SpanNeedFill = false;while (getpixel (x, y)==oldcolor){SpanNeedFill = true;x++ ;} // 待填充区段搜索完毕if (SpanNeedFill){// 将右端点作为种子点入栈pt.x = x - 1;pt.y = y;stackpush (S,pt);SpanNeedFill = false;} //继续向右检查以防遗漏while ((getpixel (x, y)!=oldcolor) && (x< xr)) x++;} //上一条扫描线上检查完毕x = xl;y=y-2; // 处理下面一条扫描线while (x < xr){SpanNeedFill = false;while (getpixel (x, y)==oldcolor){SpanNeedFill=true;x++ ;}if (SpanNeedFill){pt.x= x - 1;pt.y = y;stackpush (S,pt);SpanNeedFill=false;}while ((getpixel (x, y)!=oldcolor) && (x < xr))x++;}}}//主函数检测void main(){int radius,color;int x,y;//种子点int oldcolor,newcolor;//原色与填充色//输入参数值printf("input radius and color:\n");//画圆参数scanf("%d,%d",&radius,&color);printf("input x and y:\n"); //读入内点scanf("%d,%d", &x, &y);printf("input oldcolor and newcolor:\n"); //读入原色与填充色scanf("%d,%d", &oldcolor, &newcolor);int gdriver = DETECT,gmode;initgraph(&gdriver, &gmode, "c:\\tc");// 用背景色清空屏幕cleardevice();// 设置绘图色为红色setcolor(RED);MidpointCircle(radius,color);//用中点画圆算法画圆rectangle(150, 150, 350, 350);//再画一个矩形区域ScanLineFill4 (x,y,oldcolor,newcolor);//扫描线区域填充getch();closegraph();}五．运行结果与讨论：测试结果1：测试结果2：六．实验分析与讨论：1.通过借助栈这一数据结构，完成了区域填充的扫描线算法的实现，并利用以前所学的画圆等算法，进行综合运用，在此基础上进行扩充，设计多种图案，进行扫描线填充算法的检测，都得到了理想的结果，体现了算法的有效性；2.栈的数据结构给种子点的操作带来了极大的方便，为算法的实现提供了便利，同时还提高了算法的复用性和可靠性；3.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。

计算机图形学——区域填充算法（基本光栅图形算法）⼀、区域填充概念区域：指已经表⽰成点阵形式的填充图形，是象素的集合。

区域填充：将区域内的⼀点（常称【种⼦点】）赋予给定颜⾊，然后将这种颜⾊扩展到整个区域内的过程。

区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种⼦点的颜⾊扩展到区域内的其它点。

1、区域有两种表⽰形式1）内点表⽰：枚举出区域内部的所有象素，内部所有象素着同⼀个颜⾊，边界像素着与内部象素不同的颜⾊。

2）边界表⽰：枚举出区域外部的所有象素，边界上的所有象素着同⼀个颜⾊，内部像素着与边界象素不同的颜⾊。

21）四向连通区域：从区域上⼀点出发可通过【上、下、左、右】四个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

2）⼋向连通区域：从区域上⼀点出发可通过【上、下、左、右、左上、右上、左下、右下】⼋个⽅向移动的组合，在不越出区域的前提下，到达区域内的任意象素。

⼆、简单种⼦填充算法给定区域G⼀种⼦点（x, y）,⾸先判断该点是否是区域内的⼀点，如果是，则将该点填充为新的颜⾊，然后将该点周围的四个点（四连通）或⼋个点（⼋连通）作为新的种⼦点进⾏同样的处理，通过这种扩散完成对整个区域的填充。

这⾥给出⼀个四连通的种⼦填充算法（区域填充递归算法），使⽤【栈结构】来实现原理算法原理如下：种⼦像素⼊栈，当【栈⾮空】时重复如下三步：这⾥给出⼋连通的种⼦填充算法的代码：void flood_fill_8(int[] pixels, int x, int y, int old_color, int new_color){if(x<w&&x>0&&y<h&&y>0){if (pixels[y*w+x]==old_color){pixels[y*w+x]== new_color);flood_fill_8(pixels, x,y+1,old_color,new_color);flood_fill_8(pixels, x,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y,old_color,new_color);flood_fill_8(pixels, x+1,y,old_color,new_color);flood_fill_8(pixels, x+1,y+1,old_color,new_color);flood_fill_8(pixels, x+1,y-1,old_color,new_color);flood_fill_8(pixels, x-1,y+1,old_color,new_color);flood_fill_8(pixels, x-1,y-1,old_color,new_color);}}}简单种⼦填充算法的不⾜a)有些像素会多次⼊栈，降低算法效率，栈结构占空间b)递归执⾏，算法简单，但效率不⾼，区域内每⼀像素都要进/出栈，费时费内存c)改进算法，减少递归次数，提⾼效率三、扫描线种⼦填充算法基本思想从给定的种⼦点开始，填充当前扫描线上种⼦点所在的⼀区段，然后确定与这⼀段相邻的上下两条扫描线上位于区域内的区段（需要填充的区间），从这些区间上各取⼀个种⼦点依次把它们存起来，作为下次填充的种⼦点。

西安工程大学实验报告课程实验名称区第 1 页共 6 页系别组别_____________ 实验报告日期年月日姓名学号报告退发 ( 订正、重做 )E_mail:_________________________________ 教师审批评分___________________区域填充算法一、实验目的和任务1. 学习多边形填充的基于扫描线的区域填充算法2. 编程实现区域填充算法二、实验环境和设备windows系统下 vs2012 c++三、实验步骤和过程在MFC框架中通过菜单与对话框实现多边形顶点参量的输入，选择各种填充算法中的两种进行展示，其中栅栏填充和边填充算法不能同时选择，多边形的表示根据所选择的算法，以内点表示或边界表示均可四、实验故障与排除五、总结附录#include <glut.h>#include<Windows.h>const int POINTNUM = 7; //多边形点数./******定义结构体用于活性边表AET和新边表NET***********************************/ typedef struct XET{float x;float dx, ymax;XET* next;}AET, NET;/******定义点结构体point******************************************************/struct point{float x;float y;}polypoint[POINTNUM] = { 250, 50, 550, 150, 550, 400, 250, 250, 100, 350, 100, 100, 120, 30 };//多边形顶点void PolyScan(){/******计算最高点的y坐标(扫描到此结束)****************************************/int MaxY = 0;int i;for (i = 0; i<POINTNUM; i++)if (polypoint[i].y>MaxY)MaxY = polypoint[i].y;/*******初始化AET表***********************************************************/ AET *pAET = new AET;pAET->next = NULL;/******初始化NET表************************************************************/ NET *pNET[1024];for (i = 0; i <= MaxY; i++){pNET[i] = new NET;pNET[i]->next = NULL;}glClear(GL_COLOR_BUFFER_BIT); //赋值的窗体显示.glColor3f(0.0, 0.0, 0.0); //设置直线的颜色红色glBegin(GL_POINTS);/******扫描并建立NET表*********************************************************/ for (i = 0; i <= MaxY; i++){for (int j = 0; j<POINTNUM; j++)if (polypoint[j].y == i){ //一个点跟前面的一个点形成一条线段。

实验(No. 4)题目：区域填充实验目的及要求：一、实验目的：掌握基本光栅图形的生成原理和算法。

使用Visual C＋＋实现区域填充。

二、实验要求：1 在OnDraw函数里绘制一个欲填充的多边形区域；－－用CPen类；2 在C**View类里添加一个实现函数FloodFill4；－p443 在OnDraw函数里确定种子点，调用该实现函数；4 每人单独完成实验，多边形的边的数目和座标不能和例子相同。

5 不要取中文类名；工程（project）以自己名字全拼和/或学号来命名；6 思考能否像实验五那样，做出一个菜单来实现填充算法？三、实验设备：微机，Visual C++6.0四、实验内容及步骤：1 打开VC，打开原来建立的工程CG。

文件名为cg.dsw。

2 在CGView.cpp文件中（类CCGView中），添加函数void FloodFill4(int x, int y, COLORREFoldColor, COLORREF newColor)。

方法如下：在VC界面的ClassView中，右键单击CCGView 类，出现图1所示的界面，点击“Add Member Function…”菜单，出现图2的对话框，在其中分别完成对函数FloodFill的定义和声明。

图1图23 在函数体void FloodFill4(int x, int y, COLORREF oldColor, COLORREF newColor)中，实现这个内点表示的4连通区域的递归填充算法。

具体代码参考教材P44。

需要注意的是，FloodFill4函数中调用GetPixel和SetPixel函数之前需要得到设备上下文，即在函数体前部加入如下代码：CDC *pDC = this->GetDC();调用方式为：COLORREF color = pDC->GetPixel(x,y)；同理，调用SetPixel函数的方式为：pDC->SetPixel(x,y,newColor);并在FloodFill4函数结尾前加上代码：this->ReleaseDC(pDC);以释放DC，避免对资源的过多占用。

活化边表
把与当前扫描线 相交的边称为活 化边，并把它们 按与扫描线交点 X坐标递增的顺 序存放在一个链 表中，形成活化 边表。
表结构
算法中采用较灵活的数据结构。它由边的分有序边 表ET（Edge Table）和边的活化边表AEL（Active Edge Table ）两部分组成。 表结构ET和AET中的基本元素为多边形的边。边 的结构由以下四个域组成： ymax 边的上端点的y坐标； x 在ET中表示边的下端点的x坐标，在 AET中则表示边与扫描线的交点的坐标； Δx 边的斜率的倒数； next 指向下一条边的指针。
四个方向运动 八个方向运动
四连通区域
八连通区域
算法原理：
填充区域边界 以一种颜色指 定，从区域的 一个内部点开 始，由内至外 绘制直到填充算法
设(x,y)为内点表示的4连通区域内的一点，oldcolor为区域的 原色，要将整个区域填充为新的颜色newcolor。内点表示的 4连通区域的递归填充算法: void FloodFill4(int x,int y,int oldcolor,int newcolor) { if(GetPixel(x,y)==oldcolor) { SetPixel(x,y,newcolor); FloodFill4(x,y+1,oldcolor,newcolor); FloodFill4(x,y-1,oldcolor,newcolor); FloodFill4(x-1,y,oldcolor,newcolor); FloodFill4(x+1,y,oldcolor,newcolor); } }
i1
a
i1
i
a
其中 x
b 为常数， a
交点数的处理

实验四区域填充算法的实现班级 08信计学号 67姓名张洪伟分数一、实验目的和要求：1. 理解区域的表示和类型；2．实现区域填充的扫描线算法；3．WIN-TC 图形编程模板实现编程结果并保存。

二、实验内容：在任意不间断区间中只取一个种子像素（不间断区间指在一条扫描线上一组相邻元素），填充当前扫描线上的该段区间；然后确定与这一区段相邻的上下两条扫描线上位于区域内的区段，并依次把它们保存起来，反复进行这个过程，直到所保存的每个区段都填充完毕。

1. 确定种子区段：从种子点出发，沿当前扫描线向左右两个方向填充直到边界。

用三元组(y,xLeft,xRight)记录此区段。

2．初始化：将堆栈设为空，将种子区段压入堆栈。

3．出栈：若堆栈为空，算法结束;否则取栈顶元素，以纵坐标为y的扫描线为当前扫描线，[xLeft,xRight]为搜索区间。

4．进栈：分别确定与当前扫描线相邻的上下两条扫描线与区段(y,xLeft,xRight)连通的位于给定区域内的区段。

如果有这样的区段，填充并将它们的信息压入堆栈，返回步骤3。

三、实验结果分析1该实验先用fillellipse(100,100,60,40) 画出实心椭圆，然后用如上算法填充，代码如下：setcolor(5);fillellipse(300,250,60,40);ScanLineFill(300,250,15,5);此算法还能填充带边框的多边形，如下代码填充一个矩形区域，oldColor 为背景色0：rectangle(100,20,200,50);ScanLineFill(125,30,0,5);如下代码填充带孔的四连通区域：bar(100,80,150,180);bar(150,80,200,90);bar(200,80,250,180);bar(150,130,200,180);ScanLineFill(110,150,15,2);对于每一个待填充的区段，只需压栈一次，因此扫描线算法的效率提高了很多。

实验2：多边形区域扫描线填充或种子填充实验类型：验证、设计所需时间：3学时主要实验内容及要求：实现多边形区域扫描线填充的有序边表算法，并将实现的算法应用于任意多边形的填充，要求多边形的顶点由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。

要求掌握边形区域扫描线填充的有序边表算法的基本原理和算法设计，画出算法实现的程序流程图，使用C或者VC++实现算法，并演示。

参考试验步骤：1）分析多边形区域扫描线填充算法的原理，确定算法流程①初始化：构造边表，AET表置空②将第一个不空的ET表中的边插入AET表③由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色④y=y i+1时，根据x=x i+1/k修改AET表所有结点中交点的x坐标。

同时如果相应的ET表不空，则将其中的结点插入AET表，形成新的AET表⑤AET表不空，则转（3），否则结束。

2）编程实现①首先确定多边形顶点和ET/AET表中结点的结构②编写链表相关操作（如链表结点插入、删除和排序等）③根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能④编写主函数，测试该算法源代码：#include<gl/glut.h>#include<iostream>using namespace std;typedef struct dePt{int x;int y;}dePt;void fill(GLint x1,GLint y1,GLint z1){glBegin(GL_POINTS);glVertex3f(x1,y1,0.0f);glEnd();}typedef struct Edge{int yUpper;float xIntersect, dxPerScan;struct Edge *next;}Edge;void insertEdge(Edge *list, Edge *edge){Edge *p,*q=list;p=q->next;while(p!=NULL){if(edge->xIntersect<p->xIntersect)p=NULL;else{q=p;p=p->next;}}edge->next=q->next;q->next=edge;}int yNext(int k, int cnt, dePt*pts){int j;if((k+1)>(cnt-1))j=0;elsej=k+1;while(pts[k].y==pts[j].y)if((j+1)>(cnt-1))j=0;else j++;return (pts[j].y);}void makeEdgeRec(dePt lower, dePt upper,int yComp,Edge *edge,Edge *edges[]) {edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);edge->xIntersect=lower.x;if(upper.y<yComp)edge->yUpper=upper.y-1;elseedge->yUpper=upper.y;insertEdge(edges[lower.y],edge);}void buildEdgeList(int cnt,dePt *pts,Edge *edges[]){Edge *edge;dePt v1,v2;int i,yPrev=pts[cnt-2].y;v1.x=pts[cnt-1].x;v1.y=pts[cnt-1].y;for(i=0;i<cnt;i++){v2=pts[i];if(v1.y!=v2.y){edge=(Edge *)malloc(sizeof(Edge));if(v1.y<v2.y)makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);elsemakeEdgeRec(v2,v1,yPrev,edge,edges);}yPrev=v1.y;v1=v2;}}void buildActiveList(int scan,Edge *active,Edge *edges[]) {Edge *p,*q;p=edges[scan]->next;while(p){q=p->next;insertEdge(active,p);p=q;}}void fillScan(int scan,Edge *active){Edge *p1,*p2;int i;p1=active->next;while(p1){p2=p1->next;for(i=p1->xIntersect;i<p2->xIntersect;i++)fill((int)i,scan,3);p1=p2->next;}}void deleteAfter(Edge *q){Edge *p=q->next;q->next=p->next;free(p);}void updateActiveList(int scan,Edge *active) {Edge *q=active, *p=active->next;while(p)if(scan>=p->yUpper){p=p->next;deleteAfter(q);}else{p->xIntersect=p->xIntersect+p->dxPerScan; q=p;p=p->next;}}void resortActiveList(Edge *active){Edge *q,*p=active->next;active->next=NULL;while(p){q=p->next;insertEdge(active,p);p=q;}}void scanFill(int cnt,dePt *pts){Edge *edges[1024],*active;int i,scan;for(i=0;i<1024;i++){edges[i]=(Edge *)malloc(sizeof(Edge)); edges[i]->next=NULL;}buildEdgeList(cnt,pts,edges);active=(Edge *)malloc(sizeof(Edge)); active->next=NULL;for(scan=0;scan<1024;scan++)buildActiveList(scan,active,edges);if(active->next){fillScan(scan,active);updateActiveList(scan,active);resortActiveList(active);}}}void ChangeSize(GLsizei w,GLsizei h){GLfloat nRange=400.0f;if(h==0) h=1;glViewport(0,0,w,h);glMatrixMode(GL_PROJECTION);glLoadIdentity();if(w<=h)glOrtho(-nRange,nRange,-nRange*h/w,nRange*h/w,-nRange,nRange);elseglOrtho(-nRange*h/w,nRange*h/w,-nRange,nRange,-nRange,nRange); glMatrixMode(GL_MODELVIEW);glLoadIdentity();}void Display(void){glClear(GL_COLOR_BUFFER_BIT);glLineWidth(5.0);int n,x,y,i;cout<<"请输入多边形顶点数："<<endl;cin>>n;dePt *t=new dePt[n];for(i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个顶点坐标"<<endl;cin>>x>>y;t[i].x=x;t[i].y=y;glVertex2i(t[i].x,t[i].y);} glEnd();glFlush();scanFill(n,t);glFlush();}void SetupRC()glClearColor(1.0f,1.0f,1.0f,1.0f); glColor3f(1.0f,0.0f,0.0f);}实验结果：。

3.区域采样技术
改变边或直线的外观，模糊淡化阶梯 相当于图像的前置滤波
直线有宽度
点
有限
1/23/2022
1/23/2022
当前您浏览到是第三十三页，共三十四页。
区域
33
33
图形反走样技术（antialiasing）
根据相交的面积值决定像素显示的亮度级别
8级灰度
1/23/2022
1/23/2022 当前您浏览到是第三十四页，共三十四页。
22
当前您浏览到是第二十二页，共三十四页。
区域连通方式对填充结果的影响
4连通区域边界填充
算法的填充结果
当前您浏览到是第二十三页，共三十四页。
8连通区域边界填充 算法的填充结果
简单的种子填充算法
（4连通边界）
种子像素入栈 当栈非空时，重复以下步骤：
栈顶像素出栈 将出栈象素置成填充色 按左、上、右、下顺序检查与出栈象素相邻的
T x A x P x B x P
z z B A z z P P (x A x P )z B ( z P ) (x B x P )z A ( z P )
z
z
A
B
B P
x
A P
x
当T<0时，AP斜率>BP斜率，为顺时针角 当T>0时，AP斜率<BP斜率，为逆时针角
当前您浏览到是第六页，共三十四页。
内部一个点出发
当前您浏览到是第九页，共三十四页。
扫描线填充算法
利用图形的空间连贯性和 扫描线的连贯性
y 8 7 P5
6 5
I1 4 3
I2 P4
P3 I3 I4
2
1 P1
P2
求交：I4, I3, I2, I1

表5
4∧
3
2
1 0∧
P4P5
528 .
P5P6
5 -1.5 7 ∧
11 0 8 ∧ P3P4
2 0 7 ∧ P6P1
5 -3 2 . 5 3 3 ∧
P1P2
P2P3
P4P5
P3P4
y=7
9 2 8 . 11 0 8 ∧
更新边表，删除P6P1和P5P6，填充交点之间的区域
更新边表，删除P4P5和P3P4，有效边表为空，没有新边，填充算法结束
扫描线与多边形相交的边分处扫描线的两侧，则计 一个交点。设yi是扫描线，yi-1，yi+1分别是共享该顶 点的另外两个顶点，即 yi>yi-1，yi<yi+1，则计1个交 点，如P1。
扫描线与多边形相交的边分处扫描线同侧，且 yi<yi-1，yi<yi+1，则计2个交点(填色)，如P2。
扫描线与多边形相交的边分处扫描线同侧，且 yi>yi-1，yi>yi+1，则计0个交点(不填色)，如P6。
八向连通算法种子填充算法八向连通区域连通方式对填充结果的影响4连通区域填充算法的填充结果8连通区域填充算法的填充结果简单的种子填充算法4连通边界按右上左下顺序检查与出栈象素相邻的四象素若其中某象素不在边界上且未被置成填充色则将其入栈填充算法演示简单的种子像素入栈有些象素会入栈多次这样一方面降低了算法的效率另一方面还要求很大的存储空间以实现栈的结构解决这个问题的一个办法是在任意一个扫描线与多边形的相交区间含有若干个连续象素中只取一个种象素入栈相应的算法称为扫描线填充算法
扫描线填充算法规则
规则1： 边界上象素的取舍问题，避免填充扩大化。 解决方法： 边界象素：规定落在右上边界的象素不予填充。 具体实现时，只要对扫描线与多边形的相交区间左闭 右开，下闭上开。

2011-5-11
第6部分 区域填充
第5页
（1）求交（2）排序（3）配对（4）填色
8 7 6 5 4 3 2 P4(11,8) F G A B P5(5,5) P3(11,3) P1(2,2) P2(5,1) 0 1 2 3 4 5 6 7 8 9 10 11 E C D
P6(2,7)
1
2011-5-11
第6部分 区域填充
第6页
顶点问题
– 只需检查顶点的两条边的另外两个端点的y值。按 这两个y值中大于交点y值的个数是0,1,2来决定。
P1 1 P2 P3 P4 2 3
2011-5-11
第6部分 区域填充
第7页
活性边表算法
活性边表(AET)
–把与当前扫描线相交的边称为活性边，并把它们按 与扫描线交点x坐标递增的顺序存放在一个链表中
2011-5-11
第6部分 区域填充
第4页
扫描线填充算法
基本思想
– 用水平扫描线从上到下扫描由点线段构成的多段构 成的多边形。 – 每根扫描线与多边形各边产生一系列交点。将这些 交点按照x坐标进行分类，将分类后的交点成对取 出，作为两个端点，以所填的色彩画水平直线。 – 多边形被扫描完毕后，填色也就完成。
5 -3 P1P2
2011-5-11
第6部分 区域填充
第9页
算法程序
void polyfill (polygon, color) int color; 多边形 polygon; { for (各条扫描线i ) { 初始化新边表头指针NET [i]； 把y min = i 的边放进边表NET [i]; } y = 最低扫描线号； 初始化活性边表AET为空；
2011-5-11