計(jì)算機(jī)圖形學(xué)實(shí)驗(yàn)報(bào)告

計(jì)算機(jī)圖形學(xué)試驗(yàn)匯報(bào)第一次目錄TOC\o"1-3"\h\u243921.試驗(yàn)?zāi)康?3107192.試驗(yàn)內(nèi)容 3160552.1.Bresenham畫(huà)直線(xiàn)算法 3314362.2.Bresenham畫(huà)圓算法 334272.3.Bresenham畫(huà)橢圓算法 474342.4.多邊形陰影線(xiàn)填充算法 510222.5.多邊形掃描轉(zhuǎn)換算法 522663.試驗(yàn)環(huán)節(jié) 668623.1.程序設(shè)計(jì) 6231103.1.1.畫(huà)線(xiàn)段 7304793.1.2.畫(huà)圓 875703.1.3.畫(huà)橢圓 10184653.1.4.多邊形陰影線(xiàn)填充 11287003.1.5.多邊形區(qū)域掃描填充 15152023.2.程序運(yùn)行成果 2485443.2.1.畫(huà)直線(xiàn) 2491263.2.2.畫(huà)圓 2574213.2.3.畫(huà)橢圓 2565753.2.4.多邊形陰影線(xiàn)填充 26281333.2.5.多邊形區(qū)域掃描填充 27176784.試驗(yàn)總結(jié) 281.試驗(yàn)?zāi)康膬H調(diào)用畫(huà)點(diǎn)函數(shù)，設(shè)計(jì)實(shí)現(xiàn)一種圖形函數(shù)庫(kù)，具有如下功能：畫(huà)線(xiàn)段。畫(huà)圓弧。畫(huà)橢圓。畫(huà)多邊形。多邊形區(qū)域的陰影線(xiàn)填充。多邊形掃描轉(zhuǎn)換算法：顏色填充。試驗(yàn)環(huán)境：DevC++試驗(yàn)語(yǔ)言：C語(yǔ)言2.試驗(yàn)內(nèi)容本次試驗(yàn)?zāi)康牟捎昧巳缦滤惴▽?shí)現(xiàn)。2.1.Bresenham畫(huà)直線(xiàn)算法根據(jù)直線(xiàn)的斜率確定選擇X或者Y方向作為計(jì)長(zhǎng)方向,在此方向上每次遞增一種單位步長(zhǎng)(或者一種像素單位),另一種方向上與否同步產(chǎn)生一種單位增量由一種計(jì)算量很小的鑒別式來(lái)判斷。(以斜率在0~1之間的直線(xiàn)段為例)這種狀況下,選擇X方向?yàn)橛?jì)長(zhǎng)方向，即增量dx=1。如下圖所示,設(shè)Pi(xi,yi)是已選定的離直線(xiàn)近來(lái)的像素,目前要決定Pi+1是T還是S。若d<0.5,則S比較靠近直線(xiàn),應(yīng)選S；若d>=0.5,則應(yīng)選T。(m=△y/△x)令e=d-0.5(初值為m-0.5),即有：e<0時(shí)，選Pi+1(xi+1,yi),更新e=e+m；e>=0時(shí)，選Pi+1(xi+1,yi+1),更新e=e+m-1。2.2.Bresenham畫(huà)圓算法與Bresenham直線(xiàn)生成算法同樣,其基本措施是從一種起點(diǎn)出發(fā),運(yùn)用鑒別式選擇下一種顯示點(diǎn)。鑒別式的值通過(guò)簡(jiǎn)樸計(jì)算獲得,其符號(hào)用作判斷。（以位于第一象限的1/8圓弧為例）此算法在每一步都選擇一種離開(kāi)理想圓周近來(lái)的點(diǎn)Pi(xi,yi)，使其誤差項(xiàng)|D(Pi)|=|xi2+yi2-R2|在每一步都是極小值。設(shè)Pi-1(xi-1,yi-1)已被選定為最靠近圓弧的點(diǎn)，下一步x=xi-1+1時(shí),參見(jiàn)下圖：要決定T還是S更靠近理想的圓弧,令D(S)=(xi-1+1)2+yi-12-R2D(T)=(xi-1+1)2+(yi-1-1)2-R2顯然,|D(S)|>=|D(T)|時(shí)，應(yīng)當(dāng)取T點(diǎn)，反之則取S點(diǎn)。即若令di=|D(S)|-|D(T)|則di>=0，選擇T點(diǎn)，否則選用S點(diǎn)。結(jié)論：d1=3-2R；假如di<0,選Pi(xi,yi-1)，將yi=yi-1代入求di+1：di+1=di+4xi+2=di+4xi-1+6假如di>=0，選Pi(xi,yi-1-1)，將yi=yi-1-1代入求di+1：di+1=di+4xi-4yi-1+6=di+4(xi-1-yi-1)+102.3.Bresenham畫(huà)橢圓算法與Bresenham直線(xiàn)和圓生成算法原理同樣，不過(guò)橢圓的生成的過(guò)程中要分為上半部與下半部的狀況討論。在生成橢圓上部區(qū)域時(shí)，以x軸為步進(jìn)方向，如圖所示：x每步進(jìn)一種單位，就需要在判斷y保持不變還是也步進(jìn)減1，bresenham算法定義鑒別式為：

di=d1-d2假如di<0，則取P1為下一種點(diǎn)，否則，取P2為下一種點(diǎn)。采用鑒別式di，使得鑒別式規(guī)約為全整數(shù)運(yùn)算，算法效率得到了很大的提高。根據(jù)橢圓方程，可以計(jì)算出d1和d2分別是：d1=a2(yi2-y2)d2=a2(y2-yi+12)以(0,b)作為橢圓上部區(qū)域的起點(diǎn)，將其代入鑒別式di可以得到如下遞推關(guān)系：當(dāng)di<0時(shí)，di+1=di+2b2(2xi+3)當(dāng)di>=0時(shí)，di+1=di+2b2(2xi+3)-4a2(yi-1)d1=2b2–2a2b+a2在生成橢圓下部區(qū)域時(shí)，以y軸為步進(jìn)方向，如圖所示：y每步進(jìn)減一種單位，就需要在判斷x保持不變還是步進(jìn)加一種單位，對(duì)于下部區(qū)域，計(jì)算出d1和d2分別是：d1=b2(xi+12-x2)d2=b2(x2-xi2)以(xp,yp)作為橢圓下部區(qū)域的起點(diǎn)，將其代入鑒別式di可以得到如下遞推關(guān)系：

當(dāng)di<0時(shí)，di+1=di-4a2(yi-1)+2a2當(dāng)di>=0時(shí)，di+1=di+2b2(xi+1)-4a2(y-1)+2a2+b2d1=b2(xp+1)2+b2xp2-2a2b2+2a2(yp-1)22.4.多邊形陰影線(xiàn)填充算法算法環(huán)節(jié)如下：a.對(duì)于MN條棱邊,計(jì)算每一條棱邊Li的兩個(gè)端點(diǎn)分別按陰影線(xiàn)斜率k=tgα引線(xiàn)得到的截距,其中較小值放在B(1,i)中,較大值放在B(2,i)中。b.求出Bmin=minB(1,i)，Bmax=maxB(2,i)，i=1,2,...,MN。c.取第一條陰影線(xiàn)截距為b=Bmin+△b(△b=h/|cosα|)。d.初始化寄存陰影線(xiàn)與各棱邊交點(diǎn)的數(shù)組D(2,MN)；判斷目前陰影線(xiàn)與各棱邊與否有交點(diǎn),若存在則計(jì)算出交點(diǎn)坐標(biāo)并存入D數(shù)組；按X/Y坐標(biāo)排列D數(shù)組中的交點(diǎn)并生成陰影線(xiàn)段；取下一條陰影線(xiàn)b=b+△b,若b≠Bmax轉(zhuǎn)d繼續(xù)。2.5.多邊形掃描轉(zhuǎn)換算法算法環(huán)節(jié)如下：a.非極值奇點(diǎn)的預(yù)處理。（極值奇點(diǎn)算作2個(gè)交點(diǎn)；非極值奇點(diǎn)算作1個(gè)交點(diǎn)）b.建立邊的分類(lèi)表ET。c.取掃描線(xiàn)初始值y為ET表中所列的最小y坐標(biāo)值。d.邊的活化鏈表AEL初始化,使其為空。e.反復(fù)下列操作,直至ET表和AEL表都變成空：e1.把ET表中縱坐標(biāo)為y的鏈取下,與AEL表合并，并保持AEL表中元素按x域值升序排列，x相似時(shí)，按△x域。e2.對(duì)于目前掃描線(xiàn)y,從左到右,將AEL表中元素兩兩配對(duì),按每對(duì)兩個(gè)x域定義的區(qū)段填充所需要的像素值。e3.將AEL表中滿(mǎn)足ymax=y的元素刪除；e4.對(duì)于仍留在AEL表中的元素,求下一條掃描線(xiàn)與邊的交點(diǎn),即x域累加△x：x=x+△x。e5.取下一條掃描線(xiàn)作為目前掃描線(xiàn)：y=y+1。3.試驗(yàn)環(huán)節(jié)3.1.程序設(shè)計(jì)函數(shù)庫(kù)的申明部分如下：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<windows.h>#definePI3.1416#defineDEF-10000#defineMAX100structlist{ intymax; doublex; doubledx; structlist*next;};structhead{ intnum; structlist*start; structlist*end;};typedefstructlistL;typedefstructheadH;typedefL*LP;voidDrawLine(HDChdc,intx1,inty1,intx2,inty2,COLORREFcolor);voidDrawCircle(HDChdc,intxc,intyc,intr,COLORREFcolor);voidDrawEllipse(HDChdc,intxc,intyc,inta,intb,COLORREFcolor);voidDrawPolygon(HDChdc,intp[][MAX],intpoint_num,intin_num,COLORREFcolor);voidPolygonShadow(HDChdc,intp[][MAX],intpoint_num,intin_num,doublea,inth,COLORREFcolor);voidPolygonFill(HDChdc,intp[][MAX],intpoint_num,intin_num,COLORREFcolor);voidPlotC(HDChdc,intx,inty,intxc,intyc,COLORREFcolor);voidPlotE(HDChdc,intx,inty,intxc,intyc,COLORREFcolor);intLineIntersection(doublek,intb,intx1,inty1,intx2,inty2);voidSortPoint(intd[][MAX],intd_num);voidPreProcessing(intp[][MAX],intpoint_num,intin_num);intCreateET(intp[][MAX],intpoint_num,intin_num,intymin,HET[]);LPInsertList(intx1,inty1,intx2,inty2,LPh,LP*t);LPDeleteList(LPhead,LPcurrent,LP*tail);LPSortAEL(LPhead);各個(gè)函數(shù)與數(shù)據(jù)構(gòu)造的定義見(jiàn)下文。3.1.1.畫(huà)線(xiàn)段將2.1里提到的算法思想推廣到所有象限，設(shè)計(jì)函數(shù)voidDrawLine(HDChdc,intx1,inty1,intx2,inty2,COLORREFcolor)其中參數(shù)意義如下：HDChdc畫(huà)圖界面intx1線(xiàn)段一端橫坐標(biāo)inty1線(xiàn)段一端縱坐標(biāo)intx2線(xiàn)段一端橫坐標(biāo)inty2線(xiàn)段一端橫坐標(biāo)COLORREFcolor直線(xiàn)的顏色該部分實(shí)現(xiàn)代碼如下：voidDrawLine(HDChdc,intx1,inty1,intx2,inty2,COLORREFcolor){ inti,interchange,s1,s2; intx,y,dx,dy,dxy,d; x=x1; y=y1; dx=abs(x2-x1); dy=abs(y2-y1); if(x2-x1>0){ s1=1; } else{ s1=-1; } if(y2-y1>0){ s2=1; } else{ s2=-1; } if(dy>dx){ dxy=dx; dx=dy; dy=dxy; interchange=1; } else{ interchange=0; } d=2*dy-dx; for(i=1;i<=dx;i++){ SetPixel(hdc,x,y,color); while(d>=0){ if(interchange==1){ x=x+s1; } else{ y=y+s2; } d=d-2*dx; } if(interchange==1){ y=y+s2; } else{ x=x+s1; } d=d+2*dy; }}3.1.2.畫(huà)圓將2.2中提到的算法思想根據(jù)圓的對(duì)稱(chēng)性推廣到所有象限，其中函數(shù)voidPlotC(HDChdc,intx,inty,intxc,intyc,COLORREFcolor)是根據(jù)圓的對(duì)稱(chēng)性畫(huà)8個(gè)點(diǎn)的輔助函數(shù)。其參數(shù)意義如下：HDChdc畫(huà)圖界面intx目前掃描的點(diǎn)相對(duì)圓心的橫坐標(biāo)距離inty目前掃描的點(diǎn)相對(duì)圓心的縱坐標(biāo)距離intxc圓心橫坐標(biāo)intyc圓心縱坐標(biāo)COLORREFcolor圓的顏色執(zhí)行畫(huà)圓的函數(shù)為voidDrawCircle(HDChdc,intxc,intyc,intr,COLORREFcolor)其參數(shù)意義如下：HDChdc畫(huà)圖界面intxc圓心橫坐標(biāo)intyc圓心縱坐標(biāo)intr圓的半徑COLORREFcolor圓的顏色該部分實(shí)現(xiàn)代碼如下：voidPlotC(HDChdc,intx,inty,intxc,intyc,COLORREFcolor){ SetPixel(hdc,xc+x,yc+y,color); SetPixel(hdc,xc+x,yc-y,color); SetPixel(hdc,xc-x,yc+y,color); SetPixel(hdc,xc-x,yc-y,color); SetPixel(hdc,xc+y,yc+x,color); SetPixel(hdc,xc+y,yc-x,color); SetPixel(hdc,xc-y,yc+x,color); SetPixel(hdc,xc-y,yc-x,color);}voidDrawCircle(HDChdc,intxc,intyc,intr,COLORREFcolor){ intx,y,d; y=r; d=3-2*r; x=0; while(x<=y){ PlotC(hdc,x,y,xc,yc,color); if(d<0){ d=d+4*x+6; } else{ d=d+4*(x-y)+10; y--; } x++; }}3.1.3.畫(huà)橢圓將2.3中提到的算法思想根據(jù)橢圓的對(duì)稱(chēng)性推廣到所有象限，其中函數(shù)voidPlotE(HDChdc,intx,inty,intxc,intyc,COLORREFcolor)是根據(jù)橢圓的對(duì)稱(chēng)性畫(huà)4個(gè)點(diǎn)的輔助函數(shù)。其參數(shù)意義如下：HDChdc畫(huà)圖界面intx目前掃描的點(diǎn)相對(duì)橢圓心的橫坐標(biāo)距離inty目前掃描的點(diǎn)相對(duì)橢圓心的縱坐標(biāo)距離intxc橢圓心橫坐標(biāo)intyc橢圓心縱坐標(biāo)COLORREFcolor橢圓的顏色執(zhí)行畫(huà)橢圓的函數(shù)為voidDrawEllipse(HDChdc,intxc,intyc,inta,intb,COLORREFcolor)其參數(shù)意義如下：HDChdc畫(huà)圖界面intxc橢圓心橫坐標(biāo)intyc橢圓心縱坐標(biāo)inta橢圓的長(zhǎng)半軸長(zhǎng)intb橢圓的短半軸長(zhǎng)COLORREFcolor圓的顏色該部分實(shí)現(xiàn)代碼如下：voidPlotE(HDChdc,intx,inty,intxc,intyc,COLORREFcolor){ SetPixel(hdc,xc+x,yc+y,color); SetPixel(hdc,xc+x,yc-y,color); SetPixel(hdc,xc-x,yc+y,color); SetPixel(hdc,xc-x,yc-y,color);}voidDrawEllipse(HDChdc,intxc,intyc,inta,intb,COLORREFcolor){ intx,y,d,e; y=b; d=2*b*b-2*b*a*a+a*a; x=0; PlotE(hdc,x,y,xc,yc,color); e=(int)((double)(a*a)/sqrt((double)(a*a+b*b))); while(x<=e){ if(d<0){ d=d+2*b*b*(2*x+3); } else{ d=d+2*b*b*(2*x+3)-4*a*a*(y-1); y--; } x++; PlotE(hdc,x,y,xc,yc,color); } d=b*b*(x*x+x)+a*a*(y*y-y)-a*a*b*b; while(y>=0){ PlotE(hdc,x,y,xc,yc,color); y--; if(d<0){ x++; d=d-2*a*a*y-a*a+2*b*b*x+2*b*b; } else{ d=d-2*a*a*y-a*a; } }}3.1.4.多邊形陰影線(xiàn)填充程序設(shè)計(jì)基于2.4中的算法原理。該算法首先要畫(huà)出多邊形，執(zhí)行畫(huà)多邊形的函數(shù)為voidDrawPolygon(HDChdc,intp[][MAX],intpoint_num,intin_num,COLORREFcolor)該函數(shù)遍歷了多邊形的各個(gè)定點(diǎn)，通過(guò)調(diào)用畫(huà)線(xiàn)段函數(shù)voidDrawLine(HDChdc,intx1,inty1,intx2,inty2,COLORREFcolor)來(lái)到達(dá)效果（畫(huà)線(xiàn)段函數(shù)詳見(jiàn)3.1.1）。該畫(huà)多邊形函數(shù)的參數(shù)意義如下：HDChdc畫(huà)圖界面intp[][MAX]儲(chǔ)存多邊形各個(gè)定點(diǎn)的數(shù)組intpoint_num多邊形的總定點(diǎn)數(shù)intin_num多邊形的內(nèi)部定點(diǎn)數(shù)COLORREFcolor多邊形的顏色在執(zhí)行多邊形陰影填充的過(guò)程中需規(guī)定填充陰影線(xiàn)與多邊形棱邊的交點(diǎn)，使用到函數(shù)intLineIntersection(doublek,intb,intx1,inty1,intx2,inty2)該函數(shù)的參數(shù)意義如下：doublek填充陰影線(xiàn)的斜率intb填充陰影線(xiàn)的截距intx1該棱邊的一種定點(diǎn)的橫坐標(biāo)inty1該棱邊的一種定點(diǎn)的縱坐標(biāo)intx2該棱邊另一種定點(diǎn)的橫坐標(biāo)inty2該棱邊另一種定點(diǎn)的縱坐標(biāo)返回值(類(lèi)型int)交點(diǎn)的橫坐標(biāo)該過(guò)程還需要對(duì)一條陰影線(xiàn)與多邊形產(chǎn)生的多種交點(diǎn)按照X坐標(biāo)升序進(jìn)行排列，使用到函數(shù)voidSortPoint(intd[][MAX],intd_num)排序原理為簡(jiǎn)樸的選擇排序。該函數(shù)的參數(shù)意義如下：intd[][MAX]儲(chǔ)存交點(diǎn)坐標(biāo)的數(shù)組intd_num交點(diǎn)個(gè)數(shù)進(jìn)行多邊形陰影線(xiàn)填充的主體函數(shù)為voidPolygonShadow(HDChdc,intp[][MAX],intpoint_num,intin_num,doublea,inth,COLORREFcolor)該函數(shù)的參數(shù)意義如下：HDChdc畫(huà)圖界面intp[][MAX]儲(chǔ)存多邊形各個(gè)定點(diǎn)的數(shù)組intpoint_num多邊形的總定點(diǎn)數(shù)intin_num多邊形的內(nèi)部定點(diǎn)數(shù)doublea陰影線(xiàn)與水平線(xiàn)的夾角inth陰影線(xiàn)之間的間隔COLORREFcolor填充陰影線(xiàn)的顏色該部分實(shí)現(xiàn)代碼如下：voidDrawPolygon(HDChdc,intp[][MAX],intpoint_num,intin_num,COLORREFcolor){ inti; for(i=0;i<=point_num-1-in_num;i++){ if(i==point_num-1-in_num){ DrawLine(hdc,p[0][i],p[1][i],p[0][0],p[1][0],color); } else{ DrawLine(hdc,p[0][i],p[1][i],p[0][i+1],p[1][i+1],color); } } for(i=point_num-in_num;i<=point_num-1;i++){ if(i==point_num-1){ DrawLine(hdc,p[0][i],p[1][i],p[0][point_num-in_num],p[1][point_num-in_num],color); } else{ DrawLine(hdc,p[0][i],p[1][i],p[0][i+1],p[1][i+1],color); } }}intLineIntersection(doublek,intb,intx1,inty1,intx2,inty2){ intb1,b2,min,max,x; b1=y1-(int)(0.5+k*(double)x1); b2=y2-(int)(0.5+k*(double)x2); if(b1<b2){ min=b1; max=b2; } else{ min=b2; max=b1; } if(b>=min&&b<=max){ x=(x1*y2-y1*x2+b*(x2-x1))/((y2-y1)-(int)(0.5+k*(double)(x2-x1))); returnx; } else{ returnDEF; }}voidSortPoint(intd[][MAX],intd_num){ inti,j,min,tempx,tempy; for(i=0;i<=d_num-2;i++){ min=i; for(j=i+1;j<=d_num-1;j++){ if(d[0][j]<d[0][min]){ min=j; } } tempx=d[0][i]; tempy=d[1][i]; d[0][i]=d[0][min]; d[1][i]=d[1][min]; d[0][min]=tempx; d[1][min]=tempy; }}voidPolygonShadow(HDChdc,intp[][MAX],intpoint_num,intin_num,doublea,inth,COLORREFcolor){ DrawPolygon(hdc,p,point_num,in_num,color);//按規(guī)定畫(huà)出多邊形 inti,db,b[MAX]; doublek; k=tan(a); db=(int)(0.5+(double)h/cos(a)); for(i=0;i<=point_num-1;i++){ b[i]=(p[1][i]-p[1][0])-(int)(0.5+k*(double)(p[0][i]-p[0][0]));//對(duì)于每個(gè)頂點(diǎn)作陰影線(xiàn)求截距 } intbmax,bmin; bmax=b[0]; bmin=b[0]; for(i=1;i<=point_num-1;i++){//確認(rèn)陰影線(xiàn)掃描范圍 if(b[i]>bmax){ bmax=b[i]; } if(b[i]<bmin){ bmin=b[i]; } } intbc,d[2][MAX],d_num; bc=bmin+db; while(bc<=bmax){//掃描過(guò)程 d_num=0; for(i=0;i<=point_num-1-in_num;i++){//求該條陰影線(xiàn)與多邊形各條外部棱邊的交點(diǎn) if(i==point_num-1-in_num){ d[0][d_num]=LineIntersection(k,bc,p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][0]-p[0][0],p[1][0]-p[1][0]); } else{ d[0][d_num]=LineIntersection(k,bc,p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][i+1]-p[0][0],p[1][i+1]-p[1][0]); } if(d[0][d_num]!=DEF){ d[1][d_num]=(int)(0.5+k*(double)d[0][d_num])+bc; d[0][d_num]=d[0][d_num]+p[0][0]; d[1][d_num]=d[1][d_num]+p[1][0]; d_num++; } } for(i=point_num-in_num;i<=point_num-1;i++){//求該條陰影線(xiàn)與多邊形各條內(nèi)部棱邊的交點(diǎn) if(i==point_num-1){ d[0][d_num]=d[0][d_num]=LineIntersection(k,bc,p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][point_num-in_num]-p[0][0],p[1][point_num-in_num]-p[1][0]); } else{ d[0][d_num]=d[0][d_num]=LineIntersection(k,bc,p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][i+1]-p[0][0],p[1][i+1]-p[1][0]); } if(d[0][d_num]!=DEF){ d[1][d_num]=(int)(0.5+k*(double)d[0][d_num])+bc; d[0][d_num]=d[0][d_num]+p[0][0]; d[1][d_num]=d[1][d_num]+p[1][0]; d_num++; } } SortPoint(d,d_num);//將交點(diǎn)按照X坐標(biāo)升序排列 for(i=0;i<d_num;i=i+2){//將交點(diǎn)兩兩組合填充中間區(qū)域 DrawLine(hdc,d[0][i],d[1][i],d[0][i+1],d[1][i+1],color); } bc=bc+db;//掃描下一條陰影線(xiàn) }}3.1.5.多邊形區(qū)域掃描填充程序設(shè)計(jì)基于2.5中的算法原理。算法首先要對(duì)多邊形的各個(gè)點(diǎn)進(jìn)行預(yù)處理，使用到函數(shù)voidPreProcessing(intp[][MAX],intpoint_num,intin_num)該函數(shù)的參數(shù)意義如下：intp[][MAX]儲(chǔ)存多邊形各個(gè)定點(diǎn)的數(shù)組intpoint_num多邊形的總定點(diǎn)數(shù)intin_num多邊形的內(nèi)部定點(diǎn)數(shù)之后算法要?jiǎng)?chuàng)立ET表與AEL表。程序的數(shù)據(jù)構(gòu)造定義如下：structlist{ intymax; doublex; doubledx; structlist*next;};structhead{ intnum; structlist*start; structlist*end;};typedefstructlistL;typedefstructheadH;typedefL*LP;其中，list構(gòu)造中具有ymax、x、△x域以及指向下一種節(jié)點(diǎn)的指針，作為AEL表以及ET表中的鏈表部分。而head構(gòu)造的num用于標(biāo)識(shí)ET表中的類(lèi)號(hào)或者AEL表中的掃描線(xiàn)縱坐標(biāo)，start和end分別為對(duì)應(yīng)鏈表的頭結(jié)點(diǎn)和尾節(jié)點(diǎn)，該構(gòu)造作為AEL表以及ET表中每個(gè)類(lèi)的頭部。創(chuàng)立ET表使用到函數(shù)intCreateET(intp[][MAX],intpoint_num,intin_num,intymin,HET[])該函數(shù)的參數(shù)意義如下：intp[][MAX]儲(chǔ)存多邊形各個(gè)定點(diǎn)的數(shù)組intpoint_num多邊形的總定點(diǎn)數(shù)intin_num多邊形的內(nèi)部定點(diǎn)數(shù)intymin掃描線(xiàn)起點(diǎn)縱坐標(biāo)HET[]儲(chǔ)存ET表表頭部分的數(shù)組返回值(類(lèi)型int)ET表中多邊形棱邊信息的數(shù)量在創(chuàng)立ET表的過(guò)程中，波及到鏈表的插入操作，使用到函數(shù)LPInsertList(intx1,inty1,intx2,inty2,LPh,LP*t)該函數(shù)的參數(shù)意義如下：intx1目前棱邊的一種定點(diǎn)的橫坐標(biāo)inty1目前棱邊的一種定點(diǎn)的縱坐標(biāo)intx2目前棱邊另一種定點(diǎn)的橫坐標(biāo)inty2目前棱邊另一種定點(diǎn)的縱坐標(biāo)LPhET表中該類(lèi)鏈表的頭結(jié)點(diǎn)LP*tET表中該類(lèi)鏈表的尾結(jié)點(diǎn)返回值(類(lèi)型LP)更新操作后的ET表中該類(lèi)鏈表的頭結(jié)點(diǎn)算法執(zhí)行過(guò)程中要按照AEL表中的x域以及△x域進(jìn)行升序排列，故需要波及鏈表的排序操作，使用到函數(shù)LPSortAEL(LPhead)排序原理為簡(jiǎn)樸的選擇排序。該函數(shù)的參數(shù)意義如下：LPhead待排序AEL表的頭結(jié)點(diǎn)返回值(類(lèi)型LP)排序后AEL表的頭結(jié)點(diǎn)算法執(zhí)行過(guò)程中要?jiǎng)h去AEL表中ymax=y的組員，故需要波及鏈表的刪除操作，使用到函數(shù)LPDeleteList(LPhead,LPcurrent,LP*tail);該函數(shù)的參數(shù)意義如下：LPhead待操作AEL表的頭結(jié)點(diǎn)LPcurrent待刪除節(jié)點(diǎn)LP*tail待操作AEL表的尾結(jié)點(diǎn)返回值(類(lèi)型LP)刪除操作后AEL表的頭結(jié)點(diǎn)進(jìn)行多邊形區(qū)域掃描填充算法的主體函數(shù)為voidPolygonFill(HDChdc,intp[][MAX],intpoint_num,intin_num,COLORREFcolor)該函數(shù)的參數(shù)意義如下：HDChdc畫(huà)圖界面intp[][MAX]儲(chǔ)存多邊形各個(gè)定點(diǎn)的數(shù)組intpoint_num多邊形的總定點(diǎn)數(shù)intin_num多邊形的內(nèi)部定點(diǎn)數(shù)COLORREFcolor填充的顏色該部分實(shí)現(xiàn)代碼如下：voidPreProcessing(intp[][MAX],intb[][MAX],intpoint_num,intin_num){ inti; for(i=0;i<=point_num-1-in_num;i++){ if(i==point_num-1-in_num){ if(p[1][i]<p[1][0]){ b[0][i]=-1; b[1][0]=1; } elseif(p[1][i]==p[1][0]){ b[0][i]=0; b[1][0]=0; } else{ b[0][i]=1; b[1][0]=-1; } } else{ if(p[1][i]<p[1][i+1]){ b[0][i]=-1; b[1][i+1]=1; } elseif(p[1][i]==p[1][i+1]){ b[0][i]=0; b[1][i+1]=0; } else{ b[0][i]=1; b[1][i+1]=-1; } } } for(i=point_num-in_num;i<=point_num-1;i++){ if(i==point_num-1){ if(p[1][i]<p[1][point_num-in_num]){ b[0][i]=-1; b[1][point_num-in_num]=1; } elseif(p[1][i]==p[1][point_num-in_num]){ b[0][i]=0; b[1][point_num-in_num]=0; } else{ b[0][i]=1; b[1][point_num-in_num]=-1; } } else{ if(p[1][i]<p[1][i+1]){ b[0][i]=-1; b[1][i+1]=1; } elseif(p[1][i]==p[1][i+1]){ b[0][i]=0; b[1][i+1]=0; } else{ b[0][i]=1; b[1][i+1]=-1; } } }}intCreateET(intp[][MAX],intpoint_num,intin_num,intymin,HET[]){ inti,down,e_num,b[2][MAX]; e_num=0; PreProcessing(p,b,point_num,in_num); for(i=0;i<=point_num-1-in_num;i++){ if(i==point_num-1-in_num){ if(p[1][i]!=p[1][0]){ if(p[1][i]<p[1][0]){ down=p[1][i]; if(b[0][i]*b[1][i]==-1){ down++; } } else{ down=p[1][0]; if(b[0][0]*b[1][0]==-1){ down++; } } ET[down-ymin].start=InsertList(p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][0]-p[0][0],p[1][0]-p[1][0],ET[down-ymin].start,&ET[down-ymin].end); e_num++; } } else{ if(p[1][i]!=p[1][i+1]){ if(p[1][i]<p[1][i+1]){ down=p[1][i]; if(b[0][i]*b[1][i]==-1){ down++; } } else{ down=p[1][i+1]; if(b[0][i+1]*b[1][i+1]==-1){ down++; } } ET[down-ymin].start=InsertList(p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][i+1]-p[0][0],p[1][i+1]-p[1][0],ET[down-ymin].start,&ET[down-ymin].end); e_num++; } } } for(i=point_num-in_num;i<=point_num-1;i++){ if(i==point_num-1){ if(p[1][i]!=p[1][point_num-in_num]){ if(p[1][i]<p[1][point_num-in_num]){ down=p[1][i]; if(b[0][i]*b[1][i]==-1){ down++; } } else{ down=p[1][point_num-in_num]; if(b[0][point_num-in_num]*b[1][point_num-in_num]==-1){ down++; } } ET[down-ymin].start=InsertList(p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][point_num-in_num]-p[0][0],p[1][point_num-in_num]-p[1][0],ET[down-ymin].start,&ET[down-ymin].end); e_num++; } } else{ if(p[1][i]!=p[1][i+1]){ if(p[1][i]<p[1][i+1]){ down=p[1][i]; if(b[0][i]*b[1][i]==-1){ down++; } } else{ down=p[1][i+1]; if(b[0][i+1]*b[1][i+1]==-1){ down++; } } ET[down-ymin].start=InsertList(p[0][i]-p[0][0],p[1][i]-p[1][0],p[0][i+1]-p[0][0],p[1][i+1]-p[1][0],ET[down-ymin].start,&ET[down-ymin].end); e_num++; } } } returne_num;}LPInsertList(intx1,inty1,intx2,inty2,LPh,LP*t){ LPn=NULL; n=(LP)malloc(sizeof(L)); if(y1>y2){ n->ymax=y1; n->x=(double)x2; } else{ n->ymax=y2; n->x=(double)x1; } n->dx=(double)(x2-x1)/(double)(y2-y1); n->next=NULL; if(h==NULL){ h=n; } else{ (*t)->next=n; } (*t)=n; returnh;}LPSortAEL(LPhead){ LPc1=NULL,c2=NULL,min=NULL,temp=NULL; for(c1=head;c1!=NULL;c1=c1->next){ min=c1; for(c2=c1->next;c2!=NULL;c2=c2->next){ if(c2->x<min->x){ min=c2; } elseif(c2->x==min->x){ if(c2->dx<min->dx){ min=c2; } } } temp=(LP)malloc(sizeof(L)); temp->next=NULL; temp->ymax=c1->ymax; temp->x=c1->x; temp->dx=c1->dx; c1->ymax=min->ymax; c1->x=min->x; c1->dx=min->dx; min->ymax=temp->ymax; min->x=temp->x; min->dx=temp->dx; free(temp); } returnhead;}LPDeleteList(LPhead,LPcurrent,LP*tail){ LPc=NULL; if(head==current){ head=head->next; } else{ c=head; while(c->next!=current){ c=c->next; } c->next=current->next; if(current->next==NULL){ (*tail)=c; } } current->next=NULL; free(current); returnhead;}voidPolygonFill(HDChdc,intp[][MAX],intpoint_num,intin_num,COLORREFcolor){ DrawPolygon(hdc,p,point_num,in_num,color); inti,ymax,ymin; ymax=p[1][0]; ymin=p[1