计算机图形学-区域填充的扫描线算法
- 格式：doc
- 大小：91.00 KB
- 文档页数：13
计算机图形学——区域填充的扫描线算法
一．实验名称：
区域填充的扫描线算法
二．实验目的：
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
#include
#include
#include
#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; //空栈返回true
else
return false; //非空栈返回false
}
//种子点入栈；
int stackpush (SeqStack *&S,Seed point) {
if(S->top==Stack_Size-1)//栈已满，返回false
return false;
S->top++;//栈未满，栈顶元素加1
S->Point[S->top]= point;
return true;
}
//取栈顶元素；
int stackpop (SeqStack *&S,Seed &point)
{
if(S->top==-1)//栈为空，返回false
return false;
point=S->Point[S->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
{
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：
