扫描线填色算法

1、扫描线填色算法1、基本原理见幻灯2、多边形区域填充步骤（1）输入欲填充多边形的顶点数及其顶点坐标。这里，顶点数为实际顶点 数加1，最后一个顶点坐标与第一个顶点坐标相同。（2）计算所有多边形顶点坐标中y的最大值和最小值，以此作为扫描线的 处理范围。（3）对处理范围内的每条扫描线建立有序边表。（4）对处理范围内的每条扫描线重复下列步骤：用有序边表建立当前扫描线的活化边表；从活化边表中依次取出一对交点，对该两个交点内的像素进行填充；为下一条扫描线更新活化边表，即增加交点的x值和删除不再相交的 边。重排活化边表。3、数据结构活化边表结点数据结构可以定义为：typedef struct tEdgeflo

2、at x ;/*当前扫描线与边的交点的x值*/float dx ;/*从当前扫描线到下一条扫描线之间的x增量*/int ymax ; /*边所交的最高扫描线号*/Edge;4、有序边表填充算法的C语言描述#includegraphics.h”#define WINDOW_HEIGHT 480#define NULL 0typedef struct tEdge /*设置有序边表和活化边表数据结构*/int ymax;float x, dx;struct tEdge *next;Edge;typedef struct point int x,y;POINT;/*按交点X的升序对边进行插入排序*/v

3、oid InsertEdge(Edge * list,Edge * edge) /*list 为有序边表，edge 为待插入的 边*/Edge * p,*q=list;p=q-next;while(p!=NULL) if(edge-xx)p=NULL; /*停止循环，edge应插入到链表的头*/else /* 遍历 list */ q=p;p=p-next;edge-next=q-next; /*q指向edge应插入位置的前一个结点，edge插入到 q之后*/q-next=edge;/*计算下一条非水平线的y值*/int yNext(int k,int cnt,POINT * pts)int

4、j;if(k+1)(cnt-1)j=0;elsej=k+1;while(ptsk.y=ptsj.y)if(j+1)(cnt-1)j=0;elsej+;return(ptsj.y);/*生成有序边表的一条边*/void MakeEdgeRec(POINT lower,POINT upper,int yComp,Edge * edge,Edge * edges) edge-dx=(float)(upper.x-lower.x)/(upper.y-lower.y);edge-x=lower.x;if(upper.yymax=upper.y-1;elseedge-ymax=upper.y;Insert

5、Edge(edgeslower.y,edge);/*建立有序边表，每次从顶点数组中取出两个点，调用MakeEdgeRec来生 成一条边，并调用InsertEdge把建好的边插入到有序边表中*/void BuildEdgeList(int cnt,POINT * pts, Edge * edges)Edge *edge;POINT v1,v2;int i,yPrev=ptscnt-2.y;v1.x=ptscnt-1.x;v1.y=ptscnt-1.y;for(i=0;icnt;i+) v2=ptsi;if(v1.y!=v2.y)/* nonhorizontal line */edge=(Edge

6、 *)malloc(sizeof(Edge);if(v1.ynext;while(p) q=p-next;InsertEdge(active,p);p=q;void FillScan(int scan,Edge * active,int color) /* 对当前扫描线填充*/Edge *p1, *p2;int i;p1=active-next;while(p1)p2=p1-next;for(i=p1-x;ix;i+)putpixel(int)i,scan,color);p1=p2-next;void DeleteAfter(Edge *q) /* 删除不再相交的边*/Edge *p=q-ne

7、xt;q-next=p-next;free(p);/*Delete completed edges. Update xIntersect field for others */void UpdateActiveList(int scan,Edge * active) /* 为下一条扫描线进行更新*/Edge *q=active,*p=active-next;while(p)if(scan=p-ymax) /*如果当前扫描线scan的值大于p所指向的边的 ymax，则删除该边*/ p=p-next;DeleteAfter(q);else /*否则p所指向的边的x值加一个dx */ p-x=p-x

8、+p-dx;q=p;p=p-next;void ResortActiveList(Edge * active) /*重排活化边表*/Edge *q,*p=active-next;active-next=NULL;while(p) q=p-next;InsertEdge(active,p);p=q;void ScanFill(int cnt,POINT *pts,int color) /* cnt 为多边形的顶点数，pts 为顶点坐标数组*/Edge * edgesWINDOW_HEIGHT,*active;int i, scan, scanmax = 0, scanmin = WINDOW_HEIGHT;for (i = 0; i cnt-1; i+) /*求填充区域的扫描线最大值scanmax和最小 值 scanmin*/ if (scanmax pts i.y ) scanmin = pts i.y;for(scan=scanmin;scannext=NULL;BuildEdgeList(cnt,pts,edges); /*用顶点坐标pts建立有序边表，放在 edges 中*/active=(Edge *)malloc(sizeof(Edge); /* 初始化活化边表*/ active-next=NULL;for(scan=sca