计算机图形学-有效边表算法源代码

#includestdio.h#includemalloc.h#includegl/glut.h#includeWindows.h#defineEPSILON0.000001//最小浮点数//点结构体structPoint{intx;//x坐标inty;//y坐标};//线结构体structLine{Pointhigh_point;//高端点Pointlow_point;//低端点intis_active;//是否为有效边，水平边（0），非水平边（1）doubleinverse_k;//斜率k的倒数};//边结点structEdgeNode{doublex;//扫描线与边交点的x坐标（边的低端点的x坐标）inty_max;//边的高端点的y坐标ymaxdoubleinverse_k;//斜率k的倒数EdgeNode*next;//下一个边结点的指针};//有效边表structActiveEdgeTable{inty;//扫描线yEdgeNode*head;//边链表的头指针};//桶结点typedefstructBucket{inty;//扫描线yEdgeNode*head;//边链表的头指针Bucket*next;//下一个桶的指针}EdgeTable;intcompare(Pointp1,Pointp2);Line*create_lines(Pointpoints[],intn);Pointget_lowest_point(Linelines[],intn);Pointget_highest_point(Linelines[],intn);voidswap(Line&l1,Line&l2);voidsort(Linelines[],intn);EdgeTable*create_edge_table(Linelines[],intn);ActiveEdgeTable*init_active_table(EdgeTable*edge_table);voiddelete_edge(ActiveEdgeTable*active_table,inty_max);voidadd_edge(ActiveEdgeTable*active_table,EdgeNodeedge);ActiveEdgeTable*update_active_table(ActiveEdgeTable*active_table,EdgeTable*edge_table);voidDrawPolygon(Pointpoints,intn);voidDrawGrid(intx,inty);voidFill(Pointpoints[],intn);voidInitial();voidDisplay();intmain(intargc,char*argv[]){glutInit(&argc,argv);glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);glutInitWindowSize(400,300);glutInitWindowPosition(100,120);glutCreateWindow(PolygonFilling);glutDisplayFunc(Display);Initial();glutMainLoop();return0;}//比较2个点的高度intcompare(Pointp1,Pointp2){if(p1.yp2.y)return1;elseif(p1.y==p2.y)return0;return-1;}//由点数组生成线段数组Line*create_lines(Pointpoints[],intn){Line*lines=(Line*)malloc(n*sizeof(Line));for(inti=0;in;++i){Pointp1=points[i];Pointp2=points[(i+1)%n];intresult=compare(p1,p2);if(result==0)lines[i].is_active=0;elselines[i].is_active=1;lines[i].high_point=result0?p1:p2;lines[i].low_point=result0?p1:p2;lines[i].inverse_k=(double)(p2.x-p1.x)/(double)(p2.y-p1.y);}returnlines;}//获取线数组中最低的端点Pointget_lowest_point(Linelines[],intn){Pointlowest_point=lines[0].low_point;for(inti=1;in;++i){Pointlow_point=lines[i].low_point;if(compare(lowest_point,low_point)0)lowest_point=low_point;}returnlowest_point;}//获取线数组中最高的端点Pointget_highest_point(Linelines[],intn){Pointhighest_point=lines[0].high_point;for(inti=1;in;++i){Pointhigh_point=lines[i].high_point;if(compare(highest_point,high_point)0)highest_point=high_point;}returnhighest_point;}//交换2个Line对象voidswap(Line&l1,Line&l2){Linetemp=l1;l1=l2;l2=temp;}//对线数组进行排序voidsort(Linelines[],intn){//先按低端点的y坐标进行升序排序for(inti=0;in;++i){intmin_index=i;for(intj=i+1;jn;++j){if(lines[j].low_point.ylines[min_index].low_point.y)min_index=j;}swap(lines[i],lines[min_index]);}//再将有序数组按低端点的x坐标升序排列，若x坐标相等，按inverse_k升序for(i=0;in;++i){intmin_index=i;for(intj=i+1;lines[j].low_point.y==lines[i].low_point.y;++j){if(lines[j].low_point.xlines[min_index].low_point.x)min_index=j;}swap(lines[i],lines[min_index]);if(i0&&lines[i].low_point.x==lines[i-1].low_point.x){if(lines[i].is_active==1&&lines[i-1].is_active==1){if(lines[i].inverse_klines[i-1].inverse_k)swap(lines[i],lines[i-1]);}}}}//创建一个边表EdgeTable*create_edge_table(Linelines[],intn){EdgeTable*edge_table=(EdgeTable*)malloc(sizeof(EdgeTable));edge_table-head=NULL;edge_table-next=NULL;sort(lines,n);Pointlowest_point=get_lowest_point(lines,n);Pointhighest_point=get_highest_point(lines,n);EdgeTable*s=edge_table;for(inti=lowest_point.y;i=highest_point.y;++i){Bucket*bucket=(Bucket*)malloc(sizeof(Bucket));bucket-y=i;bucket-next=NULL;bucket-head=(EdgeNode*)malloc(sizeof(EdgeNode));bucket-head-next=NULL;EdgeNode*p=bucket-head;for(intj=0;jn;++j){if(lines[j].is_active==0)continue;if(lines[j].low_point.y==i){EdgeNode*q=(EdgeNode*)malloc(sizeof(EdgeNode));q-x=lines[j].low_point.x;q-y_max=lines[j].high_point.y;q-inverse_k=lines[j].inverse_k;q-next=NULL;p-next=q;p=q;}}s-next=bucket;s=bucket;}returnedge_table;}//从边表中取出第一个不为空的桶初始化有效边表ActiveEdgeTable*init_active_table(EdgeTable*edge_table){ActiveEdgeTable*active_table=(ActiveEdgeTable*)malloc(sizeof(ActiveEdgeTable));active_table-y=edge_table-next-y;active_table-head=(EdgeNode*)malloc(sizeof(EdgeNode));active_table-head-next=NULL;EdgeNode*p=edge_table-next-head;EdgeNode*q=active_table-head;while(p-next!=NULL){EdgeNode*s=(EdgeNode*)malloc(sizeof(EdgeNode));s-x=p-next-x;s-y_max=p-next-y_max;s-inverse_k=p-next-inverse_k;s-next=NULL;q-next=s;q=s;p=p-next;}returnactive_table;}//从有效边表中删除指定y_max的边结点voiddelete_edge(ActiveEdgeTable*active_table,inty_max){EdgeNode*p=active_table-head;while(p-next!=NULL){EdgeNode*q=p-next;if(q-y_max==y_max){p-next=q-next;free(q);}elsep=p-next;}}//将一个边结点按次序添加到有效边表中voidadd_edge(ActiveEdgeTable*active_table,EdgeNodeedge){EdgeNode*t=(EdgeNode*)malloc(sizeof(EdgeNode));t-x=edge.x;t-y_max=edge.y_max;t-inverse_k=edge.inverse_k;t-next=NULL;EdgeNode*p=active_table-head;while(p-next!=NULL){EdgeNode*q=p-next;if((edge.xq-x)||(edge.x==q-x&&edge.inverse_kq-inverse_k)){p-next=t;t-next=q;return;}p=p-next;}p-next=t;}//更新有效边表，并与边表中对应的桶合并ActiveEdgeTable*update_active_table(Ac