扫描线填充算法讲解

1、扫描线算法 (Scan-Line Filling)扫描线算法适合对矢量图形进行区域填充，只需要直到多边形区域的几何位置，不需 要指定种子点，适合计算机自动进行图形处理的场合使用，比如电脑游戏和三维CAD 软件的渲染等等。对矢量多边形区域填充，算法核心还是求交。计算几何与图形学有关的几种常用算 法一文给出了判断点与多边形关系的算法一一扫描交点的奇偶数判断算法，利用此 算法可以判断一个点是否在多边形内，也就是是否需要填充，但是实际工程中使用的 填充算法都是只使用求交的思想，并不直接使用这种求交算法。究其原因，除了算法 效率问题之外，还存在一个光栅图形设备和矢量之间的转换问题。比如某个点位于非 常靠

2、近边界的临界位置，用矢量算法判断这个点应该是在多边形内，但是光栅化后， 这个点在光栅图形设备上看就有可能是在多边形外边（矢量点没有大小概念，光栅图 形设备的点有大小概念），因此，适用于矢量图形的填充算法必须适应光栅图形设备。扫描线算法的基本思想扫描线填充算法的基本思想是：用水平扫描线从上到下（或从下到上）扫描由多条首 尾相连的线段构成的多边形，每根扫描线与多边形的某些边产生一系列交点。将这些 交点按照x坐标排序，将排序后的点两两成对，作为线段的两个端点，以所填的颜色 画水平直线。多边形被扫描完毕后，颜色填充也就完成了。扫描线填充算法也可以归 纳为以下4个步骤：（1）求交，计算扫描线与多边形的交

3、点（2）交点排序，对第2步得到的交点按照x值从小到大进行排序；（3）颜色填充，对排序后的交点两两组成一个水平线段，以画线段的方式进行颜色 填充；（4）是否完成多边形扫描？如果是就结束算法，如果不是就改变扫描线，然后转第 1步继续处理；整个算法的关键是第1步，需要用尽量少的计算量求出交点，还要考虑交点是线段端 点的特殊情况，最后，交点的步进计算最好是整数，便于光栅设备输出显示。对于每一条扫描线，如果每次都按照正常的线段求交算法进行计算，则计算量大，而 且效率底下，如图（6）所示：图（6）多边形与扫描线示意图观察多边形与扫描线的交点情况，可以得到以下两个特点：（1）每次只有相关的几条边可能与扫描线

4、有交点，不必对所有的边进行求交计算；（2）相邻的扫描线与同一直线段的交点存在步进关系，这个关系与直线段所在直线 的斜率有关；第一个特点是显而易见的，为了减少计算量，扫描线算法需要维护一张由“活动边” 组成的表，称为“活动边表（AET）”。例如扫描线4的“活动边表”由P1P2和P3P4 两条边组成，而扫描线7的“活动边表”由P1P2、P6P1、P5P6和P4P5四条边组成。第二个特点可以进一步证明，假设当前扫描线与多边形的某一条边的交点已经通过直 线段求交算法计算出来，得到交点的坐标为（x, y），则下一条扫描线与这条边的交 点不需要再求交计算，通过步进关系可以直接得到新交点坐标为（x + Ax

5、, y + 1）。 前面提到过，步进关系Ax是个常量，与直线的斜率有关，下面就来推导这个Ax。假设多边形某条边所在的直线方程是：ax + by + c = 0,扫描线y和下一条扫描线 y与该边的两个交点分别是（x，y ）和仔，y ），则可得到以下两个等式：i+1i ii+1i+1ax. + by. + c = 0 （等式 1）ax+ by, 1 + c = 0 （等式 2）由等式1可以得到等式3：x. = -（byi + c） / a （等式 3）同样，由等式2可以得到等式4：x.+1 = -（byi+1 + c） / a （等式 4）由等式4 -等式3可得到xi+1 一 xi = -b （y

6、i+1 - yi）/ a由于扫描线存在yi+1 = yi + 1的关系，将代入上式即可得到：x. 1 - x. = -b / a即Ax = -b / a,是个常量（直线斜率的倒数）。“活动边表”是扫描线填充算法的核心，整个算法都是围绕者这张表进行处理的。要 完整的定义“活动边表”，需要先定义边的数据结构。每条边都和扫描线有个交点， 扫描线填充算法只关注交点的x坐标。每当处理下一条扫描线时，根据Ax直接计算 出新扫描线与边的交点x坐标，可以避免复杂的求交计算。一条边不会一直待在“活 动边表”中，当扫描线与之没有交点时，要将其从“活动边表”中删除，判断是否有 交点的依据就是看扫描线y是否大于这条边

7、两个端点的y坐标值，为此，需要记录边 的y坐标的最大值。根据以上分析，边的数据结构可以定义如下：typedef struct tagEDGEdouble xi;double dx;int ymax;74 EDGE;根据EDGE的定义，扫描线4和扫描线7的“活动边表”就分别如图（7）和图所 示：图（7）扫描线4的活动边表图（8）扫描线7的活动边表前面提到过，扫描线算法的核心就是围绕“活动边表（AET）”展开的，为了方便活 性边表的建立与更新，我们为每一条扫描线建立一个“新边表（NET） ”，存放该扫 描线第一次出现的边。当算法处理到某条扫描线时，就将这条扫描线的“新边表”中 的所有边逐一插入到“

8、活动边表”中。“新边表”通常在算法开始时建立，建立“新 边表”的规则就是：如果某条边的较低端点（y坐标较小的那个点）的y坐标与扫描 线y相等，则该边就是扫描线y的新边，应该加入扫描线y的“新边表”。上例中各 扫描线的“新边表”如下图所示：图（9）各扫描线的新边表讨论完“活动边表（AET） ”和“新边表（NET） ”，就可以开始算法的具体实现了， 但是在进一步详细介绍实现算法之前，还有以下几个关键的细节问题需要明确：（1）多边形顶点处理在对多边形的边进行求交的过程中，在两条边相连的顶点处会出现一些特殊情况，因 为此时两条边会和扫描线各求的一个交点，也就是说，在顶点位置会出现两个交点。当出现这种情

9、况的时候，会对填充产生影响，因为填充的过程是成对选择交点的过程， 错误的计算交点个数，会造成填充异常。假设多边形按照顶点P1、P2和P3的顺序产生两条相邻的边，P2就是所说的顶点。多 边形的顶点一般有四种情况，如图（10）所展示的那样，分别被称为左顶点、右顶点、 上顶点和下顶点：图（10）多边形顶点的四种类型左顶点P1、P2和P3的y坐标满足条件：y1 y2 y2 y3；上顶点P1、P2和P3的y坐标满足条件：y2 y1 & y2 y3；下顶点P1、P2和P3的y坐标满足条件：y2 y1 & y2 y3；对于左顶点和右顶点的情况，如果不做特殊处理会导致奇偶奇数错误，常采用的修正 方法是修改以顶

10、点为终点的那条边的区间，将顶点排除在区间之外，也就是删除这条 边的终点，这样在计算交点时，就可以少计算一个交点，平衡和交点奇偶个数。结合 前文定义的边”数据结构：EDGE，只要将该边的ymax修改为ymax - 1就可以了。对于上顶点和下顶点，一种处理方法是将交点计算做0个，也就是修正两条边的区间， 将交点从两条边中排除；另一种处理方法是不做特殊处理，就计算2个交点，这样也 能保证交点奇偶个数平衡。（2）水平边的处理水平边与扫描线重合，会产生很多交点，通常的做法是将水平边直接画出（填充）， 然后在后面的处理中就忽略水平边，不对其进行求交计算。（3）如何避免填充越过边界线边界像素的取舍问题也需要

11、特别注意。多边形的边界与扫描线会产生两个交点，填充 时如果对两个交点以及之间的区域都填充，容易造成填充范围扩大，影响最终光栅图 形化显示的填充效果。为此，人们提出了 “左闭右开”的原则，简单解释就是，如果 扫描线交点是1和9,则实际填充的区间是1,9），即不包括x坐标是9的那个点。扫描线算法实现 扫描线算法的整个过程都是围绕“活动边表（AET） ”展开的，为了正确初始化“活 动边表”，需要初始化每条扫描线的“新边表（NET）”，首先定义“新边表”的数 据结构。定义“新边表”为一个数组，数组的每个元素存放对应扫描线的所有“新 边”。因此定义“新边表”如下：510 std:vector std:l

12、ist slNet（ymax - ymin + ）;ymax和ymin是多边形所有顶点中y坐标的最大值和最小值，用于界定扫描线的范围。 slNet中的第一个元素对应的是ymin所在的扫描线，以此类推，最后一个元素是 ymax所在的扫描线。在开始对每条扫描线处理之前，需要先计算出多边形的ymax和 ymin并初始化新边表”：void ScanLinePolygonFill(const Polygon& py, int color)assert ();506int ymin = 0;int ymax = 0;GetPolygonMinMax(py, ymin, ymax);std:vector s

13、td:list slNet(ymax - ymin + 1);InitScanLineNewEdgeTable(slNet, py, ymin, ymax);512ush_front (e); TOC o 1-5 h z else=;if = - B;else=;slNet - ymin. push_front(e)多边形的定义Polygon和本系列第一篇计算几何与图形学有关的几种常用算法一 文中的定义一致，此处就不再重复说明。算法通过遍历所有的顶点获得边的信息，然 后根据与此边有关的前后两个顶点的情况确定此边的ymax是否需要-1修正。ps和pe 分别是当前处理边的起点和终点，pss是起点的

14、前一个相邻点，pee是终点的后一个 相邻点，pss和pee用于辅助判断ps和pe两个点是否是左顶点或右顶点，然后根据 判断结果对此边的ymax进行-1修正，算法实现非常简单，注意与扫描线平行的边是 不处理的，因为水平边直接在HorizonEdgeFill()函数中填充了。ProcessScanLineFill()函数开始对每条扫描线进行处理，对每条扫描线的处理有四 个操作，如下代码所示，四个操作分别被封装到四个函数中：void ProcessScanLineFill(std:vector std:list & slNet,int ymin, int ymax, int color)std:li

15、st aet;471for(int y = ymin; y = ymax; y+)InsertNetListToAet(slNety - ymin, aet);FillAetScanLine (aet, y, color);/删除非活动边RemoveNonActiveEdgeFromAet(aet, y);更新活动边表中每项的xi值，并根据xi重新排序UpdateAndResortAet(aet);InsertNetListToAet。函数负责将扫描线对应的所有新边插入到aet中，插入操作到 保证aet还是有序表，应用了插入排序的思想，实现简单，此处不多解释。FillAetScanLine()

16、函数执行具体的填充动作，它将aet中的边交点成对取出组成填 充区间，然后根据“左闭右开”的原则对每个区间填充，实现也很简单，此处不多解 释。RemoveNonActiveEdgeFromAet ()函数负责将对下一条扫描线来说已经不是活动 边”的边从aet中删除，删除的条件就是当前扫描线y与边的ymax相等，如果有多 条边满足这个条件，则一并全部删除：bool IsEdgeOutOfActive(EDGE e, int y) TOC o 1-5 h z return = y);443void RemoveNonActiveEdgeFromAet(std:list& aet, int y)(st

17、d:bind2nd(std:ptr_fun(lsEdgeOutOfActive), y);UpdateAndResortAet()函数更新边表中每项的xi值，就是根据扫描线的连贯性用dx 对其进行修正，并且根据xi从小到大的原则对更新后的aet表重新排序：void UpdateAetEdgeInfo(EDGE& e)+=;453bool EdgeXiComparator(EDGE& el, EDGE& e2)return =;458void UpdateAndResortAet(std:list& aet)/更新 xifor_each(), (), UpdateAetEdgeInfo);根据x

18、i从小到大重新排序(EdgeXiComparator);其实更新完xi后对aet表的重新排序是可以避免的，只要在维护aet时，除了保证 xi从小到大的排序外，在xi相同的情况下如果能保证修正量dx也是从小到大有序， 就可以避免每次对aet进行重新排序。算法实现也很简单，只需要对 InsertNetListToAet()函数稍作修改即可，有兴趣的朋友可以自行修改。至此，扫描线算法就介绍完了，算法的思想看似复杂，实际上并不难，从具体算法的 实现就可以看出来，整个算法实现不足百行代码。第二种讲解下面这个程序能对任意多边形填充，用鼠标画一个封闭多边形，画回到起始点说明画 图完毕！然后点右键填充！我用的

19、是扫描线算法，不过在对边界点的填充上有点问题， 希望高手帮忙！#include#include#include#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; /* 随鼠标

20、画线标志 */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 /*活动

21、边表数据结构*/ (int Ymax;float x;float dx;struct AEtable *next;AETable;/*交换结点数据时用的临时指针，这个指针我放在相应函数中定义编译时会有警告并*/AETable *temp; /*会在程序退出时报错，不清楚原因！ */ void Initgr() /*初始化图形模式*/ (int gdriver=DETECT,gmode;registerbgidriver(EGAVGA_driver);initgraph(&gdriver,&gmode,)； X_max=getmaxx();Y_max=getmaxy(); /*鼠标活动范围最大值

22、*/ 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_Newy_Old) /*如果当前点比前一点高,就把当前点的Y值赋予边的Ymax */ ( q1-Ymax = y_New;q1-x=x_Old;q1-y=y_Old

23、;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 Ymax) /*将边表中Ymax的最大值存入边表头结点，以确定扫 描线的终点*/head-Ymax=q1-Ymax;if(head-y q1-y) /*将边表中Y(它是一条边中X值较小的点的Y值)的最大值 存入边表头结点, */head-y=q1-y; /*以确定扫描线的起点*/q1-next=p-next;p-next=q1;if(x

24、_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-

25、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-;p=p-next;q=q-next;p=head-next;q=p-next;return head; /*返回边表头指针*/AETable SortAEtable (AETable *head) /*对活动边表中的边按x从小到大排序*/ AETable *p, *q;p=head-next;q=p-nex

26、t;while (q!=NULL) /*对活动边表中的边按X从小到大排序*/if ( p-x q-x)(t emp-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=t emp-Ymax;p-x=temp-x;p-dx=temp-dx;temp=NULL;q=q-next:p=p-next:return head; /*返回活动边表的头指针*/void AET_Fill(AETable *head,int color) /*填充活动边表中的奇数边到偶数边间 的像素*/ (AETable *p,*

27、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!=NUL

28、L)(if(q-Ymax=Ymax) /*删除活动边表中边的Ymax值与当前扫描线Y值相等的所有边 */(p-next=q-next;free(q);q=head-next;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; /*从边表的头结点获取扫描线的终结值*/he

29、ad1=SortEtable(head1); /*对边表按Y值从小到大排序*/ for( y_Now=y_Start; y_Nownext;while(q1!=NULL) /*如果边表不为空*/(2楼2007-04-26 15:11Iif(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

30、-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 = (f

31、loat)(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(0 x33,?s,?s);if(retcode=0) return 0;int86(0 x33,?s,?s);int86(0 x33,?s,?s);return retcode;int MouseState(int *m_x,int *m_y,int

32、 *mstate) /* 获取鼠标状态和位置 */ (static int x0=10,y0=10,state=0;int xnew,ynew,ch;do(if(kbhit()(ch=getch();if(ch=13)( *mstate=1;return -1;else return ch;int86(0 x33,?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) /*在鼠标当前位置

33、画鼠标指针 和 跟随鼠标移动的 直线*/( int color;char str50;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);outtextxy(10,20,str)

34、;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); /* 开辟活动边表的一个头结点，以便 加入符合条件的新边*/ head