实验二填充算法

《实验二填充算法》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验二填充算法—、实验目的和要求通过编写源程序、运行程序以及调试程序，深入理解扫描线填色算法原理，并且能够对给定任意多边形进行填充。二、实验环境1)计算机一人一台;.2)安装有Window98以上的操作系统，且安装有TurboC三、实验内容•扫描线填色算法1、基本原理见幻灯2、多边形区域填充步骤(1)输入欲填充多边形的顶点数及其顶点坐标。这里，顶点数为实际顶点数加1,最后一个顶点坐标与第一个顶点坐标相同。(2)计算所有多边形顶点坐标中y的最大值和最小值，以此作为扫描线的处理范围。(3)对处理范围内的每条扫描线建立有序边表。(4)对处

2、理范围内的每条扫描线重复下列步骤：A.用有序边表建立当前扫描线的活化边表；B.从活化边表中依次取出一对交点，对该两个交点内的像素进行填充；C.为下一条扫描线更新活化边表，即增加交点的x值和删除不再相交的边。D.重排活化边表。3、数据结构活化边表结点数据结构可以定义为：typedefstructtEdge{floatx;/*当前扫描线与边的交点的x值*/floatdx;/*从当前扫描线到下一条扫描线之间的x增量引intymax;/*边所交的最高扫描线号引}Edge;4、有序边表填充算法的C语言描述#include,'graphics.

3、h"#defineWINDOW_HEIGHT480#defineNULL0typedefstruct(Edge/*设置有序边表和活化边表数据结构*/intymax;floatx，dx;structtEdge*next;}Edge;typedefstructpoint{intx,y;}POINT;/*按交点x的升序对边进行插入排序引voidInsertEdge(Edge*list,Edge*edge)/*list为有序边表，edge为待插入的边*/{Edge*p,*q=list;p=q->next;while(p!=NULL){if(

4、edge->xx)p=NULL;/*停止循环，edge应插入到链表的头勺else/*遍历list*/{q=p;p=p->next;}}edge->next=q->next;/*q指向edge应插入位置的前一个结点，edge插入到q21后*/q->next=edge;}/*计算下一条非水平线的y值*/intyNext(intk,intent,POINT*pts){intj;if((k+l)>(cnt-l))j=0；elsej=k+l；while(pts[k].y==pts[j].y)if(G+l)>(cnt-l))j=0;el

5、sej++;return(pts[j].y);}/*生成有序边表的一条边*/voidMakeEdgeRec(POINTlower,POINTupper,intyComp,Edge*edge,Edge*edges[]){edge->dx=(float)(uppe匚x-lowe匚x)/(uppe匚y-lower.y);edge->x=lower.x;if(uppe匚yvyComp)edge->ymax=uppe匚y-1;elseedge->ymax=uppe匚y;InsertEdge(edges[lowe匚y]，edgc);}/*建立有

6、序边表，每次从顶点数组中取出两个点，调用MakeEdgeRec生成一条边,并调用InsertEdge把建好的边插入到有序边表中*/voidBuildEdgeList(intent,POINT*pts,Edge*edges[]){Edge*edge;POINTvl,v2;inti,yPrev=pts[cnt-2].y;vl.x=pts[cnt-l].x;vl.y=pts[cnt-l].y;for(i=0;i

7、*)malloc(sizeof(Edge));if(vl.ynext

8、;while(p){q=p->next;InsertEdge(active,p);p=q;voidFillScan(intscan,Edge*active,intcolor)/*对当前扫描线填充*/{Edge*pl,*p2;inti;