当前位置：文档之家› 扫描线填充算法讲解

扫描线填充算法讲解

扫描线算法（Scan-Line F illing）

扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需

要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD

软件的渲染等等。

对矢量多边形区域填充，算法核心还是求交。《计算几何与图形学有关的几种常用算法》一文给出了判断点与多边形关系的算法――扫描交点的奇偶数判断算法，利用此

算法可以判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的

填充算法都是只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法

效率问题之外，还存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非

常靠近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后，

这个点在光栅图形设备上看就有可能是在多边形外边（矢量点没有大小概念，光栅图

形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。扫描线算法的基本思想

扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首

尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些

交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色

画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归

纳为以下4个步骤：

（1）求交，计算扫描线与多边形的交点

（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；

（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色

填充；

（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第

1步继续处理；

整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端

点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。

对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而

且效率底下，如图（6）所示：

图（6）多边形与扫描线示意图

观察多边形与扫描线的交点情况，可以得到以下两个特点：

（1）每次只有相关的几条边可能与扫描线有交点，不必对所有的边进行求交计算；

（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所在直线

的斜率有关；

第一个特点是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动边”

组成的表，称为“活动边表（AET）”。例如扫描线4的“活动边表”由P1P2和P3P4两条边组成，而扫描线7的“活动边表”由P1P2、P6P1、P5P6和P4P5四条边组成。

第二个特点可以进一步证明，假设当前扫描线与多边形的某一条边的交点已经通过直

线段求交算法计算出来，得到交点的坐标为（x, y），则下一条扫描线与这条边的交

点不需要再求交计算，通过步进关系可以直接得到新交点坐标为（x + △x, y + 1）。前面提到过，步进关系△x是个常量，与直线的斜率有关，下面就来推导这个△x。

假设多边形某条边所在的直线方程是：ax + by + c = 0，扫描线y

和下一条扫描线

y i+1与该边的两个交点分别是（x

，y

）和（x

i+1

，y

i+1

），则可得到以下两个等式：

i + by

+ c = 0 (等式 1)

i+1 + by

i+1

+ c = 0 (等式 2)

由等式1可以得到等式3：

x i = -(by

+ c) / a (等式 3)

同样，由等式2可以得到等式4：

x i+1 = -(by

i+1

+ c) / a (等式 4)

由等式 4 –等式3可得到

x i+1– x

= -b (y

i+1

- y

) / a

由于扫描线存在y

i+1 = y

+ 1的关系，将代入上式即可得到：

x i+1– x

= -b / a

即△x = -b / a，是个常量（直线斜率的倒数）。

“活动边表”是扫描线填充算法的核心，整个算法都是围绕者这张表进行处理的。要完整的定义“活动边表”，需要先定义边的数据结构。每条边都和扫描线有个交点，扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时，根据△x直接计算出新扫描线与边的交点x坐标，可以避免复杂的求交计算。一条边不会一直待在“活动边表”中，当扫描线与之没有交点时，要将其从“活动边表”中删除，判断是否有交点的依据就是看扫描线y是否大于这条边两个端点的y坐标值，为此，需要记录边的y坐标的最大值。根据以上分析，边的数据结构可以定义如下：

65typedef struct tagEDGE

66{

67double xi;

68double dx;

69int ymax;

74}EDGE;

根据EDGE的定义，扫描线4和扫描线7的“活动边表”就分别如图（7）和图(8)所示：

图（7）扫描线4的活动边表

图（8）扫描线7的活动边表

前面提到过，扫描线算法的核心就是围绕“活动边表（AET）”展开的，为了方便活性边表的建立与更新，我们为每一条扫描线建立一个“新边表（NET）”，存放该扫描线第一次出现的边。当算法处理到某条扫描线时，就将这条扫描线的“新边表”中的所有边逐一插入到“活动边表”中。“新边表”通常在算法开始时建立，建立“新边表”的规则就是：如果某条边的较低端点（y坐标较小的那个点）的y坐标与扫描线y相等，则该边就是扫描线y的新边，应该加入扫描线y的“新边表”。上例中各扫描线的“新边表”如下图所示：

图（9）各扫描线的新边表

讨论完“活动边表（AET）”和“新边表（NET）”，就可以开始算法的具体实现了，但是在进一步详细介绍实现算法之前，还有以下几个关键的细节问题需要明确：

（1）多边形顶点处理

在对多边形的边进行求交的过程中，在两条边相连的顶点处会出现一些特殊情况，因

当出现这种情况的时候，会对填充产生影响，因为填充的过程是成对选择交点的过程，错误的计算交点个数，会造成填充异常。

假设多边形按照顶点P1、P2和P3的顺序产生两条相邻的边，P2就是所说的顶点。多边形的顶点一般有四种情况，如图（10）所展示的那样，分别被称为左顶点、右顶点、上顶点和下顶点：

图（10）多边形顶点的四种类型

左顶点――P1、P2和P3的y坐标满足条件：y1 < y2 < y3；

右顶点――P1、P2和P3的y坐标满足条件：y1 > y2 > y3；

上顶点――P1、P2和P3的y坐标满足条件：y2 > y1 && y2 > y3；

下顶点――P1、P2和P3的y坐标满足条件：y2 < y1 && y2 < y3；

对于左顶点和右顶点的情况，如果不做特殊处理会导致奇偶奇数错误，常采用的修正

方法是修改以顶点为终点的那条边的区间，将顶点排除在区间之外，也就是删除这条

边的终点，这样在计算交点时，就可以少计算一个交点，平衡和交点奇偶个数。结合

前文定义的“边”数据结构：EDGE，只要将该边的ymax修改为ymax – 1就可以了。

对于上顶点和下顶点，一种处理方法是将交点计算做0个，也就是修正两条边的区间，将交点从两条边中排除；另一种处理方法是不做特殊处理，就计算2个交点，这样也

能保证交点奇偶个数平衡。

（2）水平边的处理

水平边与扫描线重合，会产生很多交点，通常的做法是将水平边直接画出（填充），

然后在后面的处理中就忽略水平边，不对其进行求交计算。

（3）如何避免填充越过边界线

边界像素的取舍问题也需要特别注意。多边形的边界与扫描线会产生两个交点，填充

时如果对两个交点以及之间的区域都填充，容易造成填充范围扩大，影响最终光栅图

形化显示的填充效果。为此，人们提出了“左闭右开”的原则，简单解释就是，如果

扫描线交点是1和9，则实际填充的区间是[1,9），即不包括x坐标是9的那个点。

扫描线算法实现

扫描线算法的整个过程都是围绕“活动边表（AET）”展开的，为了正确初始化“活

动边表”，需要初始化每条扫描线的“新边表（NET）”，首先定义“新边表”的数

据结构。定义“新边表”为一个数组，数组的每个元素存放对应扫描线的所有“新边”。因此定义“新边表”如下：

510 std::vector< std::list> slNet(ymax - ymin +1);

ymax和ymin是多边形所有顶点中y坐标的最大值和最小值，用于界定扫描线的范围。slNet 中的第一个元素对应的是ymin所在的扫描线，以此类推，最后一个元素是

ymax所在的扫描线。在开始对每条扫描线处理之前，需要先计算出多边形的ymax和ymin并初始化“新边表”：

503void ScanLinePolygonFill(const Polygon& py,int color)

504{

505 assert());

506

507int ymin =0;

508int ymax =0;

509 GetPolygonMinMax(py, ymin, ymax);

510 std::vector< std::list> slNet(ymax - ymin +1);

511 InitScanLineNewEdgeTable(slNet, py, ymin, ymax);

512

ush_front(e);

344}

345else

346{

347=;

348if>=

349=-1;

350else

351=;

352 slNet[- ymin].push_front(e);

353}

354}

355}

356}

多边形的定义Polygon和本系列第一篇《计算几何与图形学有关的几种常用算法》一

文中的定义一致，此处就不再重复说明。算法通过遍历所有的顶点获得边的信息，然

后根据与此边有关的前后两个顶点的情况确定此边的ymax是否需要-1修正。ps和pe 分别是当前处理边的起点和终点，pss是起点的前一个相邻点，pee是终点的后一个

判断结果对此边的ymax进行-1修正，算法实现非常简单，注意与扫描线平行的边是不处理的，因为水平边直接在HorizonEdgeFill()函数中填充了。

ProcessScanLineFill()函数开始对每条扫描线进行处理，对每条扫描线的处理有四个操作，如下代码所示，四个操作分别被封装到四个函数中：

467void ProcessScanLineFill(std::vector< std::list>& slNet,

468int ymin,int ymax,int color)

469{

470 std::list aet;

471

472for(int y = ymin; y <= ymax; y++)

473{

474 InsertNetListToAet(slNet[y - ymin], aet);

475 FillAetScanLine(aet, y, color);

476//删除非活动边

477 RemoveNonActiveEdgeFromAet(aet, y);

478//更新活动边表中每项的xi值，并根据xi重新排序

479 UpdateAndResortAet(aet);

480}

481}

InsertNetListToAet()函数负责将扫描线对应的所有新边插入到aet中，插入操作到保证aet还是有序表，应用了插入排序的思想，实现简单，此处不多解释。FillAetScanLine()函数执行具体的填充动作，它将aet中的边交点成对取出组成填充区间，然后根据“左闭右开”的原则对每个区间填充，实现也很简单，此处不多解释。RemoveNonActiveEdgeFromAet()函数负责将对下一条扫描线来说已经不是“活动边”的边从aet中删除，删除的条件就是当前扫描线y与边的ymax相等，如果有多条边满足这个条件，则一并全部删除：

439bool IsEdgeOutOfActive(EDGE e,int y)

440{

441return== y);

442}

443

444void RemoveNonActiveEdgeFromAet(std::list& aet,int y)

445{

446(std::bind2nd(std::ptr_fun(IsEdgeOutOfActive), y));

447}

UpdateAndResortAet()函数更新边表中每项的xi值，就是根据扫描线的连贯性用dx 对其进行修正，并且根据xi从小到大的原则对更新后的aet表重新排序：

449void UpdateAetEdgeInfo(EDGE& e)

451+=;

452}

453

454bool EdgeXiComparator(EDGE& e1, EDGE& e2)

455{

456return<=;

457}

458

459void UpdateAndResortAet(std::list& aet)

460{

461//更新xi

462 for_each(),(), UpdateAetEdgeInfo);

463//根据xi从小到大重新排序

464(EdgeXiComparator);

465}

其实更新完xi后对aet表的重新排序是可以避免的，只要在维护aet时，除了保证

xi从小到大的排序外，在xi相同的情况下如果能保证修正量dx也是从小到大有序，就可以避免每次对aet进行重新排序。算法实现也很简单，只需要对InsertNetListToAet()函数稍作修改即可，有兴趣的朋友可以自行修改。

至此，扫描线算法就介绍完了，算法的思想看似复杂，实际上并不难，从具体算法的

实现就可以看出来，整个算法实现不足百行代码。

第二种讲解

下面这个程序能对任意多边形填充，用鼠标画一个封闭多边形，画回到起始点说明画

图完毕！然后点右键填充！我用的是扫描线算法，不过在对边界点的填充上有点问题，希望高手帮忙！！！

#include<>

#define FALSE 0

#define TRUE 1

#define NULL 0

union REGS regs; /* 鼠标的变量 */

int X_max,Y_max; /* 鼠标活动范围最大值 */

int x_Origin, y_Origin,x_Old,y_Old,x_New,y_New;/* 鼠标点击的初始点,前一点和当前点的坐标 */

int PointNum=0; /* 判断鼠标是否是第一次按下 */

int LineDrawFlag=FALSE; /* 随鼠标画线标志 */

int AddFlag=TRUE; /* 边是否加入边表标志 */

int y_Now; /* 扫描线y的当前值 */

int y_Start,y_Over; /* 扫描线的起点与终点 */

typedef struct Etable /* 边表数据结构 */

{

int Ymax; /* 一条边中Y值较大点的Y值 */

float x; /* 一条边中Y值较小点的X值 */

int y; /* 一条边中Y值较小点的Y值 */

float dx; /* 一条边的斜率的倒数 */

struct Etable *next; /* 指向下一条相临边的指针 */

}ETable;

typedef struct AEtable /* 活动边表数据结构 */

{

int Ymax;

float x;

float dx;

struct AEtable *next;

}AETable;

/* 交换结点数据时用的临时指针,这个指针我放在相应函数中定义编译时会有警告并 */

AETable *temp; /* 会在程序退出时报错,不清楚原因!! */

void Initgr() /* 初始化图形模式 */

{

int gdriver=DETECT,gmode;

registerbgidriver(EGAVGA_driver);

initgraph(&gdriver,&gmode,"");

Y_max=getmaxy(); /* 鼠标活动范围最大值 */

}

ETable *AddtoEtable(int x_Old,int y_Old,int x_New,int y_New,ETable *head) /* 将边加入边表 */

{ ETable *p,*q1;

p=head;

while(p->next!=NULL) /* 转到边表最后一个结点处 */

p=p->next;

q1=(ETable *)malloc(sizeof(ETable)); /* 临时建立一个结点来加入新边的信息 * /

if(y_New>y_Old) /* 如果当前点比前一点高,就把当前点的Y值赋予边的Ymax */ { q1->Ymax = y_New;

q1->x=x_Old;

q1->y=y_Old;

}

else /* 如果当然点比前一点低,就把前一点的Y值赋予边的Ymax */

{

q1->Ymax = y_Old;

q1->x=x_New;

q1->y=y_New;

}

q1->dx=(float)(x_New-x_Old)/(y_New-y_Old);

if(head->Ymax < q1->Ymax) /* 将边表中Ymax的最大值存入边表头结点,以确定扫描线的终点 */

head->Ymax=q1->Ymax;

if(head->y > q1->y) /* 将边表中 Y(它是一条边中X值较小的点的Y值) 的最大值存入边表头结点, */

head->y=q1->y; /* 以确定扫描线的起点 */

q1->next=p->next;

if(x_New==x_Origin && y_New==y_Origin) /* 如果画回到初始点,说明多边形绘制完成,停止加入边表的工作 */

AddFlag=FALSE; /* 将加入边表的标志置为假 */

return head; /* 返回边表的头指针 */

}

ETable *SortEtable(ETable *head) /* 把边表中的奇异点消除 */

()

1楼

2007-04-26 15:11

{

ETable *p,*q;

p=head->next;

q=p->next;

while(q!=NULL) /* 如果一条边的Ymax (y)与下一条边的 y (Ymax)相等,Ymax减一,以达到消除奇异点的目的 */

{

if(p->y==q->Ymax)

q->Ymax--;

if(p->Ymax==q->y)

p->Ymax--;

if(q->next==NULL)

{

if(q->y==head->next->Ymax) /* 处理最后一条边与加入的第一条边的情况 */ head->next->Ymax--;

if(q->Ymax==head->next->y)

q->Ymax--;

}

q=q->next;

}

p=head->next;

q=p->next;

return head; /* 返回边表头指针 */

}

AETable *SortAEtable(AETable *head) /* 对活动边表中的边按x从小到大排序 */ { AETable *p,*q;

p=head->next;

q=p->next;

while(q!=NULL) /* 对活动边表中的边按X从小到大排序 */

{

if( p->x > q->x)

{

temp->Ymax=q->Ymax;

temp->x=q->x;

temp->dx=q->dx;

q->Ymax=p->Ymax;

q->x=p->x;

q->dx=p->dx;

p->Ymax=temp->Ymax;

p->x=temp->x;

p->dx=temp->dx;

temp=NULL;

}

q=q->next;

p=p->next;

}

void AET_Fill(AETable *head,int color) /* 填充活动边表中的奇数边到偶数边间的像素 */

{

AETable *p,*q;

p=head->next;

q=p->next;

setcolor(color);

while(q!=NULL) /* 如果活动边表中有边要填充 */

{

line(p->x,y_Now+1,q->x,y_Now+1);

delay(1000);

q=q->next;

p=p->next;

if(q!=NULL) /* 如果活动边表仍不为空 */

{q=q->next;

p=p->next;

}

AETable *DeleteAETable(int Ymax,AETable *head) /* 删除活动边表中Ymax大于扫描线y的边 */

{

AETable *p,*q,*m;

p=head;

q=head->next;

while(q!=NULL)

{

if(q->Ymax==Ymax) /* 删除活动边表中边的Ymax值与当前扫描线Y值相等的所有边 */

{

p->next=q->next;

free(q);

p=head;

}

else

{

q=q->next;

p=p->next;

}

return head;

}

void PolygonFill(ETable *head1,AETable *head2) /* 填充多边形 */

{ ETable *p1,*q1;

AETable *p2,*q2;

y_Over=head1->Ymax; /* 从边表的头结点获取扫描线的起始值 */

y_Start=head1->y; /* 从边表的头结点获取扫描线的终结值 */

head1=SortEtable(head1); /* 对边表按Y值从小到大排序 */

for( y_Now=y_Start; y_Now

{

p1=head1;

q1=p1->next;

while(q1!=NULL) /* 如果边表不为空 */

{

2楼

2007-04-26 15:11

if(y_Now==q1->y) /* 如果边表中有与扫描线Y值相等的Y值,则将这些边加入活动边表 */

{

p2=head2;

while(p2->next!=NULL)

p2=p2->next;

q2=(AETable *)malloc(sizeof(AETable));

q2->Ymax = q1->Ymax;

q2->x = q1->x;

q2->dx = q1->dx;

q2->next=p2->next;

p2->next=q2;

p1->next=q1->next;

free(q1); /* 将边表中已经加入活动边表的边删除 */

p1=head1;

q1=p1->next;

}

else { q1=q1->next;p1=p1->next; }

}

head2=SortAEtable(head2); /* 对活动边表中的边按X从小到大排序 */

AET_Fill(head2,RED); /* 填充活动边表中从奇数边到偶数边间的像素点 */

head2=DeleteAETable(y_Now,head2); /* 删除活动边表中已经填充完毕了的边 */ p2=head2->next;

while(p2!=NULL)

{

p2->x = (float)(p2->x + p2->dx); /* 将活动边表中的边的X值增加dx,即:x = x + dx; */

p2=p2->next;

}

int MouseInit(int Xp0,int Xp1,int Yp0,int Yp1) /* 初始化鼠标 */

{ /* 这里的参数是鼠标活动范围的左上角坐标和右下角坐标 */

int retcode;

int86(0x33,?s,?s);

if(retcode==0) return 0;

int86(0x33,?s,?s);

return retcode;

}

int MouseState(int *m_x,int *m_y,int *mstate) /* 获取鼠标状态和位置 */ {

static int x0=10,y0=10,state=0;

int xnew,ynew,ch;

{

if(kbhit())

{

ch=getch();

if(ch==13)

return -1;

}

else return ch;

}

int86(0x33,?s,?s);

}while(xnew==x0&&ynew==y0&&*mstate==state);

state=*mstate;

x0=xnew;

y0=ynew;

*m_x=xnew;

*m_y=ynew;

return -1;

}

void DrawCursor(int x,int y) /* 在鼠标当前位置画鼠标指针和跟随鼠标移动的直线 */

{ int color;

char str[50];

line(x-6,y,x-2,y);

line(x,y-6,x,y-3);

line(x+2,y,x+6,y);

line(x,y+3,x,y+6);

if(LineDrawFlag==TRUE)

{

line(x_New,y_New,x,y);

}

color=getcolor();

setcolor(getbkcolor());

outtextxy(10,20,str);

sprintf(str,"(%d,%d)",x,y); /* 显示鼠标当前的坐标值 */

setcolor(WHITE);

setcolor(color);

}

main()

{

int X,Y,m_state,y,a,b,i,j;

AETable *head2;

ETable *head1;

head1=(ETable *)malloc(sizeof(ETable)); /* 开辟边表的一个头结点来保存扫描线的起始和终结值 */

head1->Ymax=0; /* 初始化Ymax为零,以便比较得到最大的Ymax */

head1->y=10000; /* 初始化Y为10000,以便比较得到最小的Y */

head1->next=NULL;

head2=(AETable *)malloc(sizeof(AETable)); /* 开辟活动边表的一个头结点,以便加入符合条件的新边 */

head2->next=NULL;

3楼

2007-04-26 15:11

Initgr(); /* BGI初始化 */

setcolor(WHITE);

setwritemode(XOR_PUT); /* 设定输入模式为异或模式 */

MouseInit(0,X_max,0,Y_max); /* 初始化鼠标 */

a=X_max;b=Y_max;

m_state=0; /* 初始化鼠标状态为移动状态 */

DrawCursor(a,b);

while(m_state!=2) /* 如果没有点击右键 */

{

MouseState(&X,&Y,&m_state); /* 获取鼠标当前状态与坐标值 */

DrawCursor(a,b); /* 通过异或输入模式删除之前的鼠标指针 */

if(m_state==1) /* 如果鼠标左键点击 */

{

LineDrawFlag=TRUE; /* 将跟随鼠标画线标志置为真 */

if(0==PointNum) /* 如果是第一次点击左键 */

{

x_Origin=a;y_Origin=b;

x_Old=a;y_Old=b;

x_New=a;y_New=b;

}

else /* 如果不是第一次点击鼠标左键 */

{

x_Old=x_New;

y_Old=y_New;

x_New=a;

y_New=b;

}

PointNum++; /* 记录鼠标左键点击次数,以便确定是否要跟随鼠标画线 */

if((x_Origin-x_New) > -10 && (x_Origin-x_New) < 10 && (y_Origin-y_New) > -10

&& (y_Origin-y_New) < 10 && ((x_Origin-x_New)!=0 || (y_Origin-y_New)!=0)) { /* 如果线画到离初始点足够近的地方 */

LineDrawFlag=FALSE; /* 将跟随鼠标画线标志置为假 */

PointNum=0; /* 鼠标点击次数清零 */

x_New=x_Origin; y_New=y_Origin; /* 将初始点的坐标值赋给当前点 */

}

line(x_Old,y_Old,x_New,y_New); /* 从前一点到当前点画线 */

if( y_New!=y_Old && AddFlag==TRUE) /* 如果当前点与前一点不是同一个点并且加入边表标志为真 */

head1=AddtoEtable(x_Old,y_Old,x_New,y_New,head1); /* 执行加入边表动作 */ }

DrawCursor(X,Y); /* 在当前位置画鼠标指针 */

a=X;

b=Y;

}

PolygonFill(head1,head2); /* 如果右键点击,刚对所画多边形进行填充,退出图形模式!!! */

DrawCursor(X,Y);

getch();

closegraph();

}