}
p2=p1->next;
for(i=p1->x;i
putpixel((int)i,scan,color); /*画出图形内部的点*/ p1=p2->next; /*活性表的下一条边表 */ }
void DeleteAfter(Edge *q)
/*删除链表中结点,删除边结点q的后续结点p*/ {
Edge *p=q->next;
q->next=p->next; /*删除结点*/ free(p); }
/* 删除 y=ymax 的边 */
/*填充完后，更新活动边表的主体函数*/
void UpdateActiveList(int scan,Edge *active)
/*删除扫描线scan完成交点计算的活性边,同时更新交点x域*/ {
Edge *q=active,*p=active->next; while(p)
if(scan>=p->ymax) /*扫描线超过边的最大y值，此条边的节点应该删掉*/ {
p=p->next;
deleteAfter(q); }
else /*扫描线未超过边的最大y值，相应的x值增加*/ {
p->x=p->x+p->dx;
q=p;p=p->next; } }
/*对活性边表结点重新排序的主体函数*/
void ResortActiveList(Edge *active)
/*活性边表active中的结点按x域从小到大重新排序*/
5
{ }
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)
/*填充函数,输入:多边形顶点个数+1=cnt, 指向多边形顶点的指针数组pts*/ {
Edge *edges[WINDOW_HEIGHT],*active;
int i,scan,scanmax=0,scanmin=WINDOW_HEIGHT;
for(i=0;i
for(scan=scanmin;scan<=scanmax;scan++) /*初始化每条扫面线的边链表*/ {edges[scan]=(Edge *)malloc(sizeof(Edge)); /*建“桶”*/
edges[scan]->next=NULL;
}
BuildEdgeList(cnt,pts,edges); /*建立有序边表*/ active=(Edge *)malloc(sizeof(Edge)); active->next=NULL;
for(scan=scanmin;scan<=scanmax;scan++) /*扫描每条扫描线，求活性表*/ {
BuildActiveList(scan,active,edges); /*建立活性边表*/
if(active->next) /*活性边表不为空*/ { FillScan(scan,active,color); /*填充当前扫描线*/ UpdateActiveList(scan,active); /*更新活化边表*/
ResortActiveList(active); /*重排活化边表*/ } } }
6
/*开始菜单*/
void main() {
POINT pts[7]; /*保存数组*/ int gdrive=DETECT,gmode;
pts[0].x=100;pts[0].y=40; /*多边形顶点x、y坐标*/ pts[1].x=220;pts[1].y=140; pts[2].x=280;pts[2].y=80; pts[3].x=350;pts[3].y=300; pts[4].x=200;pts[4].y=380; pts[5].x=50;pts[5].y=280;
pts[6].x=100;pts[6].y=40; /*合并桶中的新边，按次序插入到 AET 中*/ initgraph(&gdrive,&gmode,\设置graphic模式*/ ScanFill(7,pts,2); getch(); }
四、 实验结果
图1 用有序边表算法生成的多边形
五、 总结与体会
实验步骤
7
1) 分析多边形区域扫描线填充算法的原理，确定算法流程
① 初始化：构造边表，AET表置空
② 将第一个不空的ET表中的边插入AET表
③ 由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色 ④ y=yi+1时，根据x=xi+1/k修改AET表所有结点中交点的x坐标。同时如果相 应的ET表不空，则将其中的结点插入AET表，形成新的AET表 ⑤ AET表不空，则转（3），否则结束。 2) 编程实现
① 首先确定多边形顶点和ET/AET表中结点的结构
② 编写链表相关操作（如链表结点插入、删除和排序等）
③ 根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能
④ 编写主函数，测试该算法
通过运用C语言环境下的图像显示设置，本次实验我学会了多边形区域扫描线填充的有序边表算法，设计相关的数据结构（如链表结构、结点结构等），并将实现的算法应用于任意多边形的填充，为深一步的学习做好了铺垫。
六、 参考文献
[1]张家广 等编著.计算机图形学（第3版）.北京：清华大学出版社,1998年9月. [2]陈传波，陆枫主编，《计算机图形学基础》，电子工业出版社，2002年3月.
8