计算机图形学
——区域填充的扫描线算法
NORTHWESTUNIVERSITY
一、实验目的
1. 通过实验，进一步理解和掌握几种常用多边形填充算法的基本原理
2. 掌握多边形区域填充算法的基本过程
3. 掌握在C/C++环境下用多边形填充算法编程实现指定多边形的填充。 4. 利用TC2.0编写区域填充的扫描线算法。 二、实验内容
算法基本思想：首先填充种子点所在扫描线上位于区域内的区段，然后
确定与该区段相邻的上下两条扫描线上位于区域内的区段，并依次将各区段的起始位置保存, 这些区段分别被用区域边界色显示的像素点所包围。随后,逐步取出一开始点并重复上述过程，直到所保存各区段都填充完毕为止。 算法描述：扫描线填充算法一般包括四个步骤：求交、排序、交点配对、区域填充。正确求得扫描线与区域填内外轮廓线的交点是算法成败的关键问题。另一方面，采用合适的数据结构又可以简化操作、提高算法的效率。本论文由于采用链表结构记录轮廓线和交点，无需焦点排序的过程，因而提高了算法效率。扫描线来源于光栅显示器的显示原理：对于屏幕上所有待显示像素的信息，将这些信息按从上到下、自左至右的方式显示。
扫描线多边形区域填充算法是按扫描线顺序，计算扫描线与多边形的相交区间，再用要求的颜色显示这些区间的象素，即完成填充工作。区间的端点可以通过计算扫描线与多边形边界线的交点获得。对于一条扫描线，多边形的填充过程可以分为四个步骤：
（1）求交：计算扫描线与多边形各边的交点； （2）排序：把所有交点按x值递增顺序排序；
（3）配对：第一个与第二个，第三个与第四个等等；每对交点代表扫描线与多边形的一个相交区间;
（4）填色：把相交区间内的象素置成多边形颜色;
三、实验原理
扫描线填充算法的基本过程如下：当给定种子点(x,y)时，首先填充种子点所在扫描线上的位于给定区域的一个区段，然后确定与这一区段相连通的上、下两条扫描线上位于给定区域内的区段，并依次保存下来。反复这个过程，直到填充结束。
区域填充的扫描线算法可由下列四个步骤实现： (1)初始化：堆栈置空。将种子点(x,y)入栈。
(2)出栈：若栈空则结束。否则取栈顶元素(x,y)，以y作为当前扫描线。
(3)填充并确定种子点所在区段：从种子点(x,y)出发，沿当前扫描线向左、右两个方向填充，直到边界。分别标记区段的左、右端点坐标为xl和xr。
(4)并确定新的种子点：在区间[xl，xr]中检查与当前扫描线y上、下相邻的两条
扫描线上的象素。若存在非边界、未填充的象素，则把每一区间的最右象素作为种子点压入堆栈，返回第（2）步。
四、实验步骤
1. 复习有关算法，明确实验目的和要求；
2. 依据算法思想，绘制程序流程图（指定填充多边形）； 3. 设计程序界面，要求操作方便；
4. 用C/C++语言编写源程序并调试、执行分析实验结果
5. 对程序设计过程中出现的问题进行分析与总结；具体做法如下：
1） 打印源程序或把源程序以文件的形式提交；分析多边形区域扫描线填充算法的原理，确定算法流程
① ② ③ ④
初始化：构造边表ET，置AET表为空； 将第一个不空的ET表中的边插入AET表；
由AET表取出交点进行配对（奇偶）获得填充区间，依次对这y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。
些填充区间着色；
同时如果相应的ET表不空，则将其中的结点插入AET表，形成新的AET表； ⑤
AET表不空，则转（3），否则结束。
2）编程实现：
⑥ ⑦ ⑧ ⑨
首先确定多边形顶点和ET/AET表中结点的结构； 编写链表相关操作（如链表结点插入、删除和排序等）； 根据1）中的算法结合上述已有的链表操作函数实现多边形区域编写主函数，测试该算法。
扫描线填充的主体功能；
3）算法描述：
void polyfill (多边形 polygon, 颜色 color)
{ for (各条扫描线i )
{ 初始化新边表头指针NET [i]；
把ymin = i 的边放进边表NET [i]; }
y = 最低扫描线号；
初始化活性边表AET为空； for (各条扫描线i )
{ 把新边表NET[i]中的边结点用插入排序法插入AET表，使之按x坐标递增顺序排列；
遍历AET表，把y max= i 的结点从AET表中删除，并把y max > i结点的x值递增D x；
若允许多边形的边自相交，则用冒泡排序法对AET表重新排序； 遍历AET表，把配对交点区间(左闭右开)上的象素(x, y)，用drawpixel (x, y, color) 改写象素颜色值；
}
} /* polyfill */ 6.
五、实验结果及分析
扫描线填充算法是通过沿扫描线填充水平像素段，来处理四连通或八连通相邻点，这样就仅仅只需要将每个水平像素段的起始位置压入栈，而不需要将当前位置周围尚未处理的相邻像素都压入栈，从而可以节省大量的栈空间。
六、程序代码
#include \
#include \ #include \ #define closegr closegraph
void initgr(void) /* BGI初始化 */ {
int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同样效果 */
registerbgidriver(EGAVGA_driver);/* 注册BGI驱动后可以不需要.BGI文件的支持运行 */
initgraph(&gd, &gm, \}
enum BOOL{FALSE = 0, TRUE = 1}; typedef struct{ int y; int xLeft; int xRight; }Span;/*区段*/
typedef struct stacknode {
Span span;
struct stacknode *next; }stacknode; typedef struct {
stacknode *top; }linkstack;
/*-----------------进栈操作----------------------------------------*/ void PushStack(linkstack *s, Span *span) {
stacknode *p=(stacknode*)malloc(sizeof(stacknode)); p->span.y = span->y;
p->span.xLeft = span->xLeft; p->span.xRight = span->xRight; p->next=s->top; s->top=p; }
/*-----------------出栈操作------------------------------------------*/ void PopStack(linkstack *s,Span *span) { int x;
stacknode *p=s->top; span->y = p->span.y;
span->xLeft = p->span.xLeft; span->xRight = p->span.xRight; s->top=p->next; free(p); }
/*-----------------将栈清空------------------------------------------*/ void SetStackEmpty(linkstack *s) {
stacknode *p=s->top; while( s->top != NULL) {
free(p);
s->top=p->next; } }
/*--------------判断栈是否为空----------------------------------------*/ int IsStackEmpty(linkstack *s) {
if(s->top == NULL) return 1; else return 0; }
/*----------------核心程序开始----------------------------------------*/ void ScanLineFill4(int x,int y,int oldColor,int newColor) {
int xLeft,xRight; int i;
enum BOOL isLeftEndSet, spanNeedFill; Span span;
linkstack *s=(linkstack*)malloc(sizeof(linkstack)); s->top = NULL;
/*填充并确定种子点(x,y)所在的区段*/
百度搜索“70edu”或“70教育网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，70教育网，提供经典综合文库区域填充的扫描线算法在线全文阅读。
相关推荐：
