区域填充的扫描线算法

计算机图形学

——区域填充的扫描线算法

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)所在的区段*/

i = x;

while(getpixel(i,y) == oldColor)/*向右填充*/ {

putpixel(i,y,newColor); i++; }

span.xRight = i - 1; /*确定区段右边界*/ i = x - 1;

while(getpixel(i,y) == oldColor)/*向左填充*/ {

putpixel(i,y,newColor); i--; }

span.xLeft = i + 1; /*确定区段左边界*/ /*初始化*/

SetStackEmpty(s); span.y = y;

PushStack(s,&span);/*将前面生成的区段压入堆栈*/ while( ! IsStackEmpty(s) )/*终止判断*/ {

/*出栈*/

PopStack(s, &span); /*处理上面扫描线*/ y = span.y + 1;

xRight = span.xRight; i = span.xLeft - 1;

isLeftEndSet = FALSE;

while(getpixel(i,y) == oldColor)/*向左填充*/ {

putpixel(i, y, newColor); i--; }

if( i != span.xLeft - 1)/*确定区段左边界*/ {

isLeftEndSet = TRUE; xLeft = i + 1; }

i = span.xLeft; while( i < xRight) {

spanNeedFill = FALSE;

while(getpixel(i,y) == oldColor) /*向右填充*/ {

if( ! spanNeedFill)

{

spanNeedFill = TRUE; if( ! isLeftEndSet) {

isLeftEndSet = TRUE; xLeft = i; } }

putpixel(i,y,newColor); i++; }

if( spanNeedFill ) {

span.y = y;

span.xLeft = xLeft; span.xRight = i - 1;

PushStack(s, &span); /*将区段压入堆栈*/ isLeftEndSet = FALSE; spanNeedFill = FALSE; }

/* while(getpixel(i,y) != oldColor) */ i++;

}/*end of while( i < xRight) */

/*处理下面一条扫描线,与处理上面一条扫描线完全类似*/ y = y - 2;

xRight = span.xRight; i = span.xLeft - 1;

isLeftEndSet = FALSE;

while(getpixel(i,y) == oldColor)/*向左填充*/ {

putpixel(i, y, newColor); i--; }

if( i != span.xLeft - 1)/*确定区段左边界*/ {

isLeftEndSet = TRUE; xLeft = i + 1; }

i = span.xLeft; while( i < xRight) {

spanNeedFill = FALSE;

while(getpixel(i,y) == oldColor) /*向右填充*/ {

if( ! spanNeedFill) {

spanNeedFill = TRUE; if( ! isLeftEndSet) {

isLeftEndSet = TRUE; xLeft = i; } }

putpixel(i,y,newColor); i++; }

if( spanNeedFill ) {

span.y = y;

span.xLeft = xLeft; span.xRight = i - 1;

PushStack(s, &span); /*将区段压入堆栈*/ isLeftEndSet = FALSE; spanNeedFill = FALSE; }

/* while(getpixel(i,y) != oldColor) */ i++;

}/*end of while( i < xRight) */ delay(2000); /*延时*/

}/*end of while( ! isStackEmpty() ) */

}/*end of ScanLineFill4() */

/*---------------------main()------------------------------------------*/ int main() {

initgr(); /* BGI初始化 */ setbkcolor(3); setcolor(1);

moveto(50, 50); /*绘制4连通区域*/ lineto(400, 50); lineto(400,300); lineto(150,300); lineto(150,400); lineto(50, 400); lineto(50, 50);

ScanLineFill4(150,150,0,14); /*相与后oldColor == 0*/ getch(); /* 暂停一下，看看前面绘图代码的运行结果 */ closegr(); /* 恢复TEXT屏幕模式 */ return 0;

}

七、实验结果

本文来源：https://www.bwwdw.com/article/kisg.html