《C++程序例题-多边形扫描转换算法.docx》由会员分享,可在线阅读,更多相关《C++程序例题-多边形扫描转换算法.docx(6页珍藏版)》请在金锄头文库上搜索。
1、 C+程序例题:多边形扫描转换算法CPolyFillDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/ TODO: add draw code for native data hereconst int POINTNUM=6; /多边形点数./*定义构造体用于活性边表AET和新边表NET*/typedef struct XETfloat x;float dx,ymax;XET* next;AET,NET;/*定义点构造体point*/struct pointfloat x;float y;polypointPOINTNUM=250,50,550,150
2、,550,400,250,250,100,350,100,100;/多边形顶点/mypointPOINTNUM=100,100,200,100,200,200,100,200;/正方形/*计算点的y坐标(扫描到此完毕)*/int MaxY=0;int i;for(i=0;i MaxY)MaxY=polypointi.y;/*初始化AET表*/AET *pAET=new AET;pAET-next=NULL;/*初始化NET表*/NET *pNET1024;for(i=0;inext=NULL;/*扫描并建立NET表*/for(i=0;ix=polypointj.x;p-ymax=polypoi
3、nt(j-1+POINTNUM)%POINTNUM.y;p-dx=(polypoint(j-1+POINTNUM)%POINTNUM.x-polypointj.x)/(polypoint(j-1+POINTNUM)%POINTNUM.y-polypointj.y);p-next=pNETi-next;pNETi-next=p;if(polypoint(j+1+POINTNUM)%POINTNUM.ypolypointj.y)NET *p=new NET;p-x=polypointj.x;p-ymax=polypoint(j+1+POINTNUM)%POINTNUM.y;p-dx=(polypo
4、int(j+1+POINTNUM)%POINTNUM.x-polypointj.x)/(polypoint(j+1+POINTNUM)%POINTNUM.y-polypointj.y);p-next=pNETi-next;pNETi-next=p;/*建立并更新活性边表AET*/for(i=0;inext;while(p)p-x=p-x + p-dx;p=p-next;/更新后新AET先排序*/断表排序,不再开拓空间AET *tq=pAET;p=pAET-next;tq-next=NULL;while(p)while(tq-nextNET *s=p-next;p-next=tq-next;tq
5、-next=p;p=s;tq=pAET;/(改良算法)先从AET表中删除ymax=i的结点*/AET *q=pAET;p=q-next;while(p)if(p-ymax=i)q-next=p-next;delete p;p=q-next;elseq=q-next;p=q-next;/将NET中的新点参加AET,并用插入法按X值递增排序*/p=pNETi-next;q=pAET;while(p)while(q-nextNET *s=p-next;p-next=q-next;q-next=p;p=s;q=pAET;/*配对填充颜色*/p=pAET-next;while(p jnext-x;j+)pDC-SetPixel(static_cast(j),i,RGB(255,0,0);p=p-next-next;/考虑端点状况