计算机图形学-区域填充的扫描线算法.doc
Four short words sum up what has lifted most successful individuals above the crowd: a little bit more.-author-date计算机图形学-区域填充的扫描线算法计算机图形学-区域填充的扫描线算法计算机图形学区域填充的扫描线算法一 实验名称： 区域填充的扫描线算法二 实验目的： 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 PointStack_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; /空栈返回true else return false; /非空栈返回false/种子点入栈；int stackpush (SeqStack *&S,Seed point) if(S->top=Stack_Size-1)/栈已满，返回false return false; S->top+;/栈未满，栈顶元素加1 S->PointS->top= point; return true;/取栈顶元素；int stackpop (SeqStack *&S,Seed &point) if(S->top=-1)/栈为空，返回false return false; point=S->PointS->top; S->top -;/栈未空，top减1 return 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; elsed+=(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.此扫描线填充算法能够对多种图案进行填充，展现了算法的实用性。-
