实验2：多边形区域扫描线填充或种子填充实验类型：验证、设计所需时间：3学时主要实验内容及要求：实现多边形区域扫描线填充的有序边表算法，并将实现的算法应用于任意多边形的填充，要求多边形的顶点由键盘输入或鼠标拾取，填充要准确，不能多填也不能少填。
要求掌握边形区域扫描线填充的有序边表算法的基本原理和算法设计，画出算法实现的程序流程图，使用C或者VC++实现算法，并演示。
参考试验步骤：1）分析多边形区域扫描线填充算法的原理，确定算法流程①初始化：构造边表，AET表置空②将第一个不空的ET表中的边插入AET表③由AET表取出交点进行配对（奇偶）获得填充区间，依次对这些填充区间着色④y=y i+1时，根据x=x i+1/k修改AET表所有结点中交点的x坐标。
同时如果相应的ET表不空，则将其中的结点插入AET表，形成新的AET表⑤AET表不空，则转（3），否则结束。
2）编程实现①首先确定多边形顶点和ET/AET表中结点的结构②编写链表相关操作（如链表结点插入、删除和排序等）③根据1）中的算法结合上述已有的链表操作函数实现多边形区域扫描线填充的主体功能④编写主函数，测试该算法源代码：#include<gl/glut.h>#include<iostream>using namespace std;typedef struct dePt{int x;int y;}dePt;void fill(GLint x1,GLint y1,GLint z1){glBegin(GL_POINTS);glVertex3f(x1,y1,0.0f);glEnd();}typedef struct Edge{int yUpper;float xIntersect, dxPerScan;struct Edge *next;}Edge;void insertEdge(Edge *list, Edge *edge){Edge *p,*q=list;p=q->next;while(p!=NULL){if(edge->xIntersect<p->xIntersect)p=NULL;else{q=p;p=p->next;}}edge->next=q->next;q->next=edge;}int yNext(int k, int cnt, dePt*pts){int j;if((k+1)>(cnt-1))j=0;elsej=k+1;while(pts[k].y==pts[j].y)if((j+1)>(cnt-1))j=0;else j++;return (pts[j].y);}void makeEdgeRec(dePt lower, dePt upper,int yComp,Edge *edge,Edge *edges[]) {edge->dxPerScan=(float)(upper.x-lower.x)/(upper.y-lower.y);edge->xIntersect=lower.x;if(upper.y<yComp)edge->yUpper=upper.y-1;elseedge->yUpper=upper.y;insertEdge(edges[lower.y],edge);}void buildEdgeList(int cnt,dePt *pts,Edge *edges[]){Edge *edge;dePt v1,v2;int i,yPrev=pts[cnt-2].y;v1.x=pts[cnt-1].x;v1.y=pts[cnt-1].y;for(i=0;i<cnt;i++){v2=pts[i];if(v1.y!=v2.y){edge=(Edge *)malloc(sizeof(Edge));if(v1.y<v2.y)makeEdgeRec(v1,v2,yNext(i,cnt,pts),edge,edges);elsemakeEdgeRec(v2,v1,yPrev,edge,edges);}yPrev=v1.y;v1=v2;}}void buildActiveList(int scan,Edge *active,Edge *edges[]) {Edge *p,*q;p=edges[scan]->next;while(p){q=p->next;insertEdge(active,p);p=q;}}void fillScan(int scan,Edge *active){Edge *p1,*p2;int i;p1=active->next;while(p1){p2=p1->next;for(i=p1->xIntersect;i<p2->xIntersect;i++)fill((int)i,scan,3);p1=p2->next;}}void deleteAfter(Edge *q){Edge *p=q->next;q->next=p->next;free(p);}void updateActiveList(int scan,Edge *active) {Edge *q=active, *p=active->next;while(p)if(scan>=p->yUpper){p=p->next;deleteAfter(q);}else{p->xIntersect=p->xIntersect+p->dxPerScan; 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,dePt *pts){Edge *edges[1024],*active;int i,scan;for(i=0;i<1024;i++){edges[i]=(Edge *)malloc(sizeof(Edge)); edges[i]->next=NULL;}buildEdgeList(cnt,pts,edges);active=(Edge *)malloc(sizeof(Edge)); active->next=NULL;for(scan=0;scan<1024;scan++)buildActiveList(scan,active,edges);if(active->next){fillScan(scan,active);updateActiveList(scan,active);resortActiveList(active);}}}void ChangeSize(GLsizei w,GLsizei h){GLfloat nRange=400.0f;if(h==0) h=1;glViewport(0,0,w,h);glMatrixMode(GL_PROJECTION);glLoadIdentity();if(w<=h)glOrtho(-nRange,nRange,-nRange*h/w,nRange*h/w,-nRange,nRange);elseglOrtho(-nRange*h/w,nRange*h/w,-nRange,nRange,-nRange,nRange); glMatrixMode(GL_MODELVIEW);glLoadIdentity();}void Display(void){glClear(GL_COLOR_BUFFER_BIT);glLineWidth(5.0);int n,x,y,i;cout<<"请输入多边形顶点数："<<endl;cin>>n;dePt *t=new dePt[n];for(i=0;i<n;i++){cout<<"请输入第"<<i+1<<"个顶点坐标"<<endl;cin>>x>>y;t[i].x=x;t[i].y=y;glVertex2i(t[i].x,t[i].y);} glEnd();glFlush();scanFill(n,t);glFlush();}void SetupRC()glClearColor(1.0f,1.0f,1.0f,1.0f); glColor3f(1.0f,0.0f,0.0f);}实验结果：。
