计算机图形学-区域填充的扫描线算法重点.doc

计算机图形学——区域填充的扫描线算法 实验名称： 区域填充的扫描线算法 实验目的： 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; //空栈返回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