计算机图形学-区域填充的扫描线算法
- 格式:docx
- 大小:61.64 KB
- 文档页数:15
计算机图形学——区域填充的扫描线算法
一.实验名称:
区域填充的扫描线算法
二.实验目的:
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 + y,
yc + x, Color);
putpixel (xc + y, yc - x, 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);
}
//中点画圆算法
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;//定义顺序栈 In itStack(S);//定义了栈之后必须把栈先初始 化 setstackempty(S);/种子点栈置空; pt.x = x; pt.y = y; stackpush (S,pt); // 种子点(x, y)入栈while