第二章二維基本圖形的生成與二維區(qū)域的填充

第二章二維基本圖形的生成與區(qū)域填空重點(diǎn)：掌握二維圖元直線、圓、區(qū)域填充、字符的生成算法。難點(diǎn)：理解二維圖元生成的算法思想并且用C語(yǔ)言進(jìn)行算法的實(shí)現(xiàn)。課時(shí)安排：授課8學(xué)時(shí)（直線、圓：3學(xué)時(shí)；區(qū)域填充：4學(xué)時(shí)；字符：1學(xué)時(shí)）；上機(jī)4學(xué)時(shí)（直線、圓：2學(xué)時(shí)；區(qū)域填充：2學(xué)時(shí)）。1/31/20231第二章二維基本圖形的生成與區(qū)域填空?qǐng)D元生成算法的要求：準(zhǔn)確、亮度均勻、速度快。前面已經(jīng)知道，矢量顯示（隨機(jī)掃描顯示器）和光柵顯示是兩種完全不同的圖形顯示技術(shù)。1/31/20232第二章二維基本圖形的生成與區(qū)域填空目前，光柵顯示技術(shù)占主要地位。原因是：1、光柵顯示可以用顏色或圖案來填充一個(gè)區(qū)域；

2、光柵顯示以象素為單位進(jìn)行讀寫和存儲(chǔ)，可以實(shí)現(xiàn)對(duì)物體細(xì)節(jié)的描述；

3、圖形的任意部分均可以被移動(dòng)和復(fù)制。1/31/20233第二章二維基本圖形的生成與區(qū)域填空在這一章里，主要介紹在光柵輸出設(shè)備上，根據(jù)物體的坐標(biāo)描述構(gòu)造二維幾何圖形的方法。在光柵顯示器上，象素是屏幕的最小顯示單位，因此二維圖形的構(gòu)造就是找出最靠近所描述幾何圖形的那些象素，將它們置入規(guī)定的顏色并放入幀緩存。我們知道，一幅圖是由點(diǎn)、直線、曲線、多邊形填充區(qū)域以及字符串等組成。下面將討論這些基本圖元的生成技術(shù)和算法。

1/31/202342.1直線的掃描轉(zhuǎn)換一、數(shù)學(xué)直線在數(shù)學(xué)上，理想的直線是一條由無窮多個(gè)無限小的連續(xù)的點(diǎn)組成。數(shù)學(xué)直線1/31/202352.1直線的掃描轉(zhuǎn)換

二、光柵平面顯示的直線但在光柵顯示平面上，我們只能用二維光柵格網(wǎng)上盡可能靠近這條直線的象素點(diǎn)的集合來表示它。每個(gè)象素具有一定的尺寸，是顯示平面上可被訪問的最小單位，它的坐標(biāo)x和y只能是整數(shù)，也就是說相鄰像素的坐標(biāo)值是階梯的而不是連續(xù)的。1/31/202362.1直線的掃描轉(zhuǎn)換光柵直線1/31/202372.1直線的掃描轉(zhuǎn)換

三、直線的掃描轉(zhuǎn)換

直線的掃描轉(zhuǎn)換，就是要找出顯示平面上最佳逼近理想直線的那些象素的坐標(biāo)值，并將這些象素置成所要求的顏色。

直線的掃描轉(zhuǎn)換由于一幅圖中可能包含成千上萬條直線，所以要求繪制算法應(yīng)該：

1、最接近數(shù)學(xué)上的直線；1/31/202382.1直線的掃描轉(zhuǎn)換2、沿著線段分布的象素應(yīng)均勻不均勻的例子如下圖所示，對(duì)同樣長(zhǎng)的線段，如果進(jìn)行圖中的掃描轉(zhuǎn)換，就會(huì)因?yàn)樾甭实牟煌?，產(chǎn)生的象素個(gè)數(shù)不相等，這樣將導(dǎo)致象素亮度分布不均勻。3、畫線速度盡可能的快

1/31/202392.1.1生成直線的DDA算法數(shù)值微分法即DDA法(DigitalDifferentialAnalyzer)，是一種基于直線的微分方程來生成直線的方法一、直線DDA算法描述：設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點(diǎn)和終點(diǎn)坐標(biāo)，由直線的微分方程得

=m=直線的斜率(2－1)1/31/2023102.1.1生成直線的DDA算法

可通過計(jì)算由x方向的增量△x引起y的改變來生成直線：xi+1=xi+△x(2－2)yi+1=yi+△y=yi+△x·m(2－3)也可通過計(jì)算由y方向的增量△y引起x的改變來生成直線：yi+1=yi+△y(2－4)xi+1=xi+△x=xi+△y/m(2－5)式(2－2)至(2－5)是遞推的。

1/31/2023112.1.1生成直線的DDA算法二、直線DDA算法思想：選定x2－x1和y2－y1中較大者作為步進(jìn)方向(假設(shè)x2－x1較大)，取該方向上的增量為一個(gè)象素單位(△x=1)，然后利用式(2－1)計(jì)算另一個(gè)方向的增量(△y=△x·m=m)。通過遞推公式(2－2)至(2－5)，把每次計(jì)算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。之所以取x2－x1和y2－y1中較大者作為步進(jìn)方向，是考慮沿著線段分布的象素應(yīng)均勻，這在下圖中可看出。1/31/2023122.1.1生成直線的DDA算法另外，算法實(shí)現(xiàn)中還應(yīng)注意直線的生成方向，以決定Δx及Δy是取正值還是負(fù)值。1/31/2023132.1.1生成直線的DDA算法三、直線DDA算法實(shí)現(xiàn)：1、已知直線的兩端點(diǎn)坐標(biāo)：(x1，y1)，(x2，y2)

2、已知畫線的顏色：color

3、計(jì)算兩個(gè)方向的變化量：dx=x2－x1

dy=y2－y1

4、求出兩個(gè)方向最大變化量的絕對(duì)值：

steps=max(|dx|，|dy|)

1/31/2023142.1.1生成直線的DDA算法5、計(jì)算兩個(gè)方向的增量(考慮了生成方向)：

xin=dx/steps

yin=dy/steps

6、設(shè)置初始象素坐標(biāo)：x=x1,y=y1

7、用循環(huán)實(shí)現(xiàn)直線的繪制：

for(i=1；i<=steps；i++)

{putpixel(x，y，color)；/*在(x，y)處，以color色畫點(diǎn)*/

x=x+xin；

y=y+yin；

}1/31/2023152.1.1生成直線的DDA算法四、直線DDA算法特點(diǎn)：該算法簡(jiǎn)單，實(shí)現(xiàn)容易，但由于在循環(huán)中涉及實(shí)型數(shù)的運(yùn)算，因此生成直線的速度較慢。五、直線DDA算法程序：下面給出考慮不同斜率、不同方向直線的DDA畫線算法程序：1/31/2023162.1.1生成直線的DDA算法voidDDAline(intx0,inty0,intx1,inty1,intcolor){intx;floatdx,dy,y,k;dx=x1-x0,dy=y1-y0;k=dy/dx,y=y0;

for(x=x0;x<=x1;x++)

{

putpixel(x，int(y+0.5)，color);//在(x，y)處，以color色畫點(diǎn)

y=y+k;

}

}1/31/2023172.1.2生成直線的Bresenham算法從上面介紹的DDA算法可以看到，由于在循環(huán)中涉及實(shí)型數(shù)據(jù)的加減運(yùn)算，因此直線的生成速度較慢。在生成直線的算法中，Bresenham算法是最有效的算法之一。Bresenham算法是一種基于誤差判別式來生成直線的方法。一、直線Bresenham算法描述：它也是采用遞推步進(jìn)的辦法，令每次最大變化方向的坐標(biāo)步進(jìn)一個(gè)象素，同時(shí)另一個(gè)方向的坐標(biāo)依據(jù)誤差判別式的符號(hào)來決定是否也要步進(jìn)一個(gè)象素。1/31/2023182.1.2生成直線的Bresenham算法我們首先討論m=△y/△x，當(dāng)0≤m≤1且x1<x2時(shí)的Bresenham算法。從DDA直線算法可知這些條件成立時(shí)，公式(2-2)、(2-3)可寫成：xi+1=xi+1(2－6)yi+1=yi+m(2－7)有兩種Bresenham算法思想，它們各自從不同角度介紹了Bresenham算法思想，得出的誤差判別式都是一樣的。1/31/2023192.1.2生成直線的Bresenham算法二、直線Bresenham算法思想之一由于顯示直線的象素點(diǎn)只能取整數(shù)值坐標(biāo)，可以假設(shè)直線上第i個(gè)象素點(diǎn)坐標(biāo)為(xi，yi)，它是直線上點(diǎn)(xi，yi)的最佳近似，并且xi=xi(假設(shè)m<1），如下圖所示。那么，直線上下一個(gè)象素點(diǎn)的可能位置是(xi+1，yi)或(xi+1，yi+1)。1/31/2023202.1.2生成直線的Bresenham算法1/31/2023212.1.2生成直線的Bresenham算法由圖中可以知道，在x=xi+1處，直線上點(diǎn)的y值是y=m(xi+1)+b，該點(diǎn)離象素點(diǎn)(xi+1，yi)和象素點(diǎn)(xi+1，yi+1)的距離分別是d1和d2：d1=y-yi=m(xi+1)+b-yi(2－8)d2=(yi+1)-y=(yi+1)-m(xi+1)-b(2－9)這兩個(gè)距離差是d1-d2=2m(xi+1)-2yi＋2b-1(2－10)1/31/2023222.1.2生成直線的Bresenham算法我們來分析公式(2-10)：

(1)當(dāng)此值為正時(shí)，d1>d2，說明直線上理論點(diǎn)離(xi+1，yi+1)象素較近，下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi+1)。

(2)當(dāng)此值為負(fù)時(shí)，d1<d2，說明直線上理論點(diǎn)離(xi+1，yi)象素較近，則下一個(gè)象素點(diǎn)應(yīng)取(xi+1，yi)。

(3)當(dāng)此值為零時(shí)，說明直線上理論點(diǎn)離上、下兩個(gè)象素點(diǎn)的距離相等，取哪個(gè)點(diǎn)都行，假設(shè)算法規(guī)定這種情況下取(xi+1，yi+1)作為下一個(gè)象素點(diǎn)。1/31/2023232.1.2生成直線的Bresenham算法因此只要利用(d1-d2)的符號(hào)就可以決定下一個(gè)象素點(diǎn)的選擇。為此，我們進(jìn)一步定義一個(gè)新的判別式：pi=△x×(d1-d2)=2△y·xi-2△x·yi+c(2－11)

式(2-11)中的△x=(x2-x1)>0，因此pi與(d1-d2)有相同的符號(hào)；這里△y=y2-y1，m=△y/△x；c=2△y+△x(2b-1)。下面對(duì)式(2-11)作進(jìn)一步處理，以便得出誤差判別遞推公式并消除常數(shù)c。1/31/2023242.1.2生成直線的Bresenham算法將式(2-11)中的下標(biāo)i改寫成i+1，得到：pi+1=2△y·xi+1-2△x·yi+1+c(2－12)

將式(2-12)減去(2-11)，并利用xi+1=xi+1，可得：pi+1=pi+2△y-2△x·(yi+1-yi)(2－13)再假設(shè)直線的初始端點(diǎn)恰好是其象素點(diǎn)的坐標(biāo)，即滿足：y1=mx1+b(2－14)1/31/2023252.1.2生成直線的Bresenham算法由式(2-11)和式(2-14)得到p1的初始值：p1=2△y-△x(2－15)這樣，我們可利用誤差判別變量，得到如下算法表示：初始p1=2△y-△x(2－16)當(dāng)pi≥0時(shí)：yi+1=yi+1,

xi+1=xi+1，

pi+1=pi+2(△y-△x)否則：yi+1=yi,

xi+1=xi+1，

pi+1=pi+2△y

1/31/2023262.1.2生成直線的Bresenham算法從式(2-16)可以看出，第i+1步的判別變量pi+1僅與第i步的判別變量pi、直線的兩個(gè)端點(diǎn)坐標(biāo)分量差△x和△y有關(guān)，運(yùn)算中只含有整數(shù)相加和乘2運(yùn)算，而乘2可利用算術(shù)左移一位來完成，因此這個(gè)算法速度快并易于硬件實(shí)現(xiàn)。三、直線Bresenham算法思想之二由于象素坐標(biāo)的整數(shù)性，數(shù)學(xué)點(diǎn)(xi，yi)與所取象素點(diǎn)(xi，yir)間會(huì)引起誤差(εi)，當(dāng)xi列上已用象素坐標(biāo)(xi，yir)表示直線上的點(diǎn)(xi，yi)，下一直線點(diǎn)B(xi+1，yi+1)，是取象素點(diǎn)C(xi+1，yir)，還是D(xi＋1，y(i+1)r)呢？1/31/2023272.1.2生成直線的Bresenham算法設(shè)A為CD邊的中點(diǎn)，正確的選擇：若B點(diǎn)在A點(diǎn)上方，選擇D點(diǎn)；否則，選C點(diǎn)。用誤差式描述為：ε(xi+1)=BC-AC=(yi+1-yir)-0.5(2－8')1/31/2023282.1.2生成直線的Bresenham算法求遞推公式：ε(xi+2)=(yi+2-y(i+1)r)-0.5=yi+1+m-y(i+1)r-0.5(2－9‘)當(dāng)ε(xi+1)≥0時(shí)，選D點(diǎn)，y(i+1)r=yir+1ε(xi+2)=yi+1+m-yir-1-0.5=ε(xi+1)+m-1(2－10‘)當(dāng)ε(xi+1)﹤0時(shí)，選C點(diǎn)，y(i+1)r=yirε(xi+2)=yi+1+m－yir-0.5=ε(xi+1)+m(2－11')1/31/2023292.1.2生成直線的Bresenham算法初始時(shí)：ε(xs+1)=BC-AC=m-0.5(2－12')1/31/2023302.1.2生成直線的Bresenham算法為了運(yùn)算中不含實(shí)型數(shù)，同時(shí)不影響不等式的判斷，將方程兩邊同乘一正整數(shù)。令方程兩邊同乘2·Δx，即p=2·Δx·ε，則：初始時(shí)：p=2·Δy-Δx(2－13')遞推式：當(dāng)p≥0時(shí)：{p=p+2·(Δy－Δx)；

y++；

x++；

}

否則：{p=p+2·Δy；

x++；

}(2－14')1/31/2023312.1.2生成直線的Bresenham算法四、直線Bresenham算法實(shí)現(xiàn)條件：0≤m≤1且x1<x21、輸入線段的兩個(gè)端點(diǎn)坐標(biāo)和畫線顏色：x1，y1，x2，y2，color；

2、設(shè)置象素坐標(biāo)初值：x=x1，y=y1；

3、設(shè)置初始誤差判別值：p=2·Δy-Δx；

4、分別計(jì)算：Δx=x2-x1、Δy=y2-y1；

1/31/2023322.1.2生成直線的Bresenham算法5、循環(huán)實(shí)現(xiàn)直線的生成：

for(x=x1；x<=x2；x++)

{putpixel(x,y,color)；

if(p>=0)

{y=y+1；

p=p+2·(Δy-Δx)；

}

else

{p=p+2·Δy；

}}1/31/2023332.1.2生成直線的Bresenham算法五、直線Bresenham算法完善現(xiàn)在我們修正(2-16)公式，以適應(yīng)對(duì)任何方向及任何斜率線段的繪制。如下圖所示，線段的方向可分為八種，從原點(diǎn)出發(fā)射向八個(gè)區(qū)。由線段按圖中所示的區(qū)域位置可決定xi+1和yi+1的變換規(guī)律。容易證明：當(dāng)線段處于①、④、⑧、⑤區(qū)時(shí)，以|△x|和|△y|代替前面公式中的△x和△y，當(dāng)線段處于②、③、⑥、⑦區(qū)時(shí)，將公式中的|△x|和|△y|對(duì)換，則上述兩公式仍有效。1/31/2023342.1.2生成直線的Bresenham算法在線段起點(diǎn)區(qū)分線段方向1/31/2023352.1.2生成直線的Bresenham算法七、直線Bresenham算法特點(diǎn)由于程序中不含實(shí)型數(shù)運(yùn)算，因此速度快、效率高，是一種有效的畫線算法。八、直線Bresenham算法程序voidBresenhamline(intx1,inty1,intx2,inty2,intcolor)

{

intx,y,dx,dy,s1,s2,p,temp,interchange,i;

x=x1;

y=y1;

dx=abs(x2-x1);

dy=abs(y2-y1);

if(x2>x1)

s1=1;

else

s1=-1;

1/31/2023362.1.2生成直線的Bresenham算法if(y2>y1)

s2=1;

else

s2=-1;

if(dy>dx)

{

temp=dx;

dx=dy;

dy=temp;

interchange=1;

}

else

interchange=0;

p=2*dy-dx;

1/31/2023372.1.2生成直線的Bresenham算法for(i=1;i<=dx;i++)

{

putpixel(x,y,color);

if(p>=0)

{

if(interchange==0)

y=y+s2;

else

x=x+s1;

p=p-2*dx;

}

if(interchange==0)

x=x+s1;

else

y=y+s2;

p=p+2*dy;

}

}1/31/2023382.1直線的生成習(xí)題1.DDA法生成直線的基本原理是什么？1/31/2023392.2圓的生成這里僅討論圓心位于坐標(biāo)原點(diǎn)的圓的掃描轉(zhuǎn)換算法，對(duì)于圓心不在原點(diǎn)的圓，可先用平移變換，將它的圓心平移到原點(diǎn)，然后進(jìn)行掃描轉(zhuǎn)換，最后再平移到原來的位置。有幾種較容易的方法可以得到圓的掃描轉(zhuǎn)換，但是效率都不高。例如：直角坐標(biāo)法和極坐標(biāo)法：1、直角坐標(biāo)法圓的直角坐標(biāo)方程為x2+y2=R2

若取x作為自變量，解出y，得到1/31/2023402.2圓的生成(2－17)

我們可以先掃描轉(zhuǎn)換四分之一的圓周。讓自變量x從0到R以單位步長(zhǎng)增加，在每一步時(shí)可解出y，然后調(diào)用畫點(diǎn)函數(shù)即可逐點(diǎn)畫出圓。但這樣做，由于有乘方和平方根運(yùn)算，并且都是浮點(diǎn)運(yùn)算，算法效率不高。而且當(dāng)x接近R值時(shí)(圓心在原點(diǎn))，在圓周上的點(diǎn)（R，0）附近，由于圓的斜率趨于無窮大，使得圓周上有較大的間隙。1/31/2023412.2圓的生成2、極坐標(biāo)法假設(shè)圓周上一點(diǎn)P（x，y）處的半徑與x軸的夾角為θ，則圓的極坐標(biāo)方程為

x=Rcosθ

(2－18)y=Rsinθ利用下面將要介紹的圓周上點(diǎn)的對(duì)稱性，那么自變量θ的取值范圍就是(0，45°)。這個(gè)方法涉及三角函數(shù)計(jì)算和乘法運(yùn)算，計(jì)算量較大。因此，也不是一種有效的方法。1/31/2023422.2.1圓的八分對(duì)稱性圓心位于原點(diǎn)的圓有四條對(duì)稱軸x=0、y=0、x=y和x=－y，見下圖。從而若已知圓弧上一點(diǎn)P(x，y)，就可以得到其關(guān)于四條對(duì)稱軸的七個(gè)對(duì)稱點(diǎn)，這種性質(zhì)稱為八分對(duì)稱性。因此只要能畫出八分之一的圓弧，就可以利用對(duì)稱性的原理得到整個(gè)圓弧。下面的函數(shù)CirclePoints()用來顯示P(x，y)及其七個(gè)對(duì)稱點(diǎn)。1/31/2023432.2.1圓的八分對(duì)稱性voidCirclePoints(x,y,color)

intx,y,color;

{

putpixel(x,y,color);

putpixel(x,－y,color);

putpixel(－x,y,color);

putpixel(－x,－y,color);

putpixel(y,x,color);

putpixel(y,－x,color);

putpixel(－y,x,color);

putpixel(－y,－x,color);

}1/31/2023442.2.1圓的八分對(duì)稱性圓的八分對(duì)稱性注意：

當(dāng)圓心不在原點(diǎn)時(shí)，只須在putpixel()函數(shù)中加上平移量x0、y0（圓心坐標(biāo)）即可。1/31/2023452.2.1圓的八分對(duì)稱性例如當(dāng)x0=300，y0=200時(shí)，則：…

putpixel(x0+x，y0+y，color)；

putpixel(x0+x，y0-y，color)；

putpixel(x0-x，y0+y，color)；

putpixel(x0-x，y0-y，color)；

putpixel(x0+y，y0+x，color)；

putpixel(x0+y，y0-x，color)；

putpixel(x0-y，y0+x，color)；

putpixel(x0-y，y0-x，color)；

…1/31/2023462.2.2中點(diǎn)算法生成圓中點(diǎn)畫圓算法在一個(gè)方向上取單位間隔，在另一個(gè)方向的取值由兩種可能取值的中點(diǎn)離圓的遠(yuǎn)近而定。實(shí)際處理中，用決策變量的符號(hào)來確定象素點(diǎn)的選擇，因此算法效率較高。一、中點(diǎn)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，起點(diǎn)在(0，R)處，終點(diǎn)在(

,)處，順時(shí)針生成八分之一圓，利用對(duì)稱性掃描轉(zhuǎn)換全部圓。為了應(yīng)用中點(diǎn)畫圓法，我們定義一個(gè)圓函數(shù)F(x，y)=x2+y2-R2(2－19)1/31/2023472.2.2中點(diǎn)算法生成圓任何點(diǎn)(x，y)的相對(duì)位置可由圓函數(shù)的符號(hào)來檢測(cè)：

<0點(diǎn)(x，y)位于數(shù)學(xué)圓內(nèi)F(x，y)=0點(diǎn)(x，y)位于數(shù)學(xué)圓上(2－20)>0點(diǎn)(x，y)位于數(shù)學(xué)圓外

1/31/2023482.2.2中點(diǎn)算法生成圓如下圖所示，圖中有兩條圓弧A和B，假定當(dāng)前取點(diǎn)為Pi(xi，yi)，如果順時(shí)針生成圓，那么下一點(diǎn)只能取正右方的點(diǎn)E(xi+1，yi)或右下方的點(diǎn)SE(xi+1，yi-1)兩者之一。中點(diǎn)畫線算法1/31/2023492.2.2中點(diǎn)算法生成圓假設(shè)M是E和SE的中點(diǎn)，則：1、當(dāng)F(M)<0時(shí)，M在圓內(nèi)(圓弧A)，這說明點(diǎn)E距離圓更近，應(yīng)取點(diǎn)E作為下一象素點(diǎn)；

2、當(dāng)F(M)>0時(shí)，M在圓外(圓弧B)，表明SE點(diǎn)離圓更近，應(yīng)取SE點(diǎn)；

3、當(dāng)F(M)=0時(shí)，在E點(diǎn)與SE點(diǎn)之中隨便取一個(gè)即可，我們約定取SE點(diǎn)。1/31/2023502.2.2中點(diǎn)算法生成圓二、中點(diǎn)畫圓算法思想因此，我們用中點(diǎn)M的圓函數(shù)作為決策變量di，同時(shí)用增量法來迭代計(jì)算下一個(gè)中點(diǎn)M的決策變量di+1。(2－21)下面分兩種情況來討論在迭代計(jì)算中決策變量di+1的推導(dǎo)。1、見圖（a），若di<0，則選擇E點(diǎn)，接著下一個(gè)中點(diǎn)就是，這時(shí)新的決策變量為：(2－22)1/31/2023512.2.2中點(diǎn)算法生成圓（a）(di<0)中點(diǎn)畫線算法1/31/2023522.2.2中點(diǎn)算法生成圓式(2－22)減去(2－21)得：di+1=di+2xi+3(2－23)2、見圖（b），若di≥0，則選擇SE點(diǎn)，接著下一個(gè)中點(diǎn)就是，這時(shí)新的決策變量為：(2－24)

1/31/2023532.2.2中點(diǎn)算法生成圓（b）(di≥0)中點(diǎn)畫線算法式(2－24)減去(2－21)得：di+1=di+2(xi-yi)+5(2－25)1/31/2023542.2.2中點(diǎn)算法生成圓我們利用遞推迭代計(jì)算這八分之一圓弧上的每個(gè)點(diǎn)，每次迭代需要兩步處理：

（1）用前一次迭代算出的決策變量的符號(hào)來決定本次選擇的點(diǎn)。

（2）對(duì)本次選擇的點(diǎn)，重新遞推計(jì)算得出新的決策變量的值。剩下的問題是計(jì)算初始決策變量d0，如下圖所示。對(duì)于初始點(diǎn)(0，R)，順時(shí)針生成八分之一圓，下一個(gè)中點(diǎn)M的坐標(biāo)是，所以：1/31/2023552.2.2中點(diǎn)算法生成圓(2—26）生成圓的初始條件和圓的生成方向

1/31/2023562.2.2中點(diǎn)算法生成圓三、中點(diǎn)畫圓算法實(shí)現(xiàn)1、輸入：圓半徑r、圓心(x0，y0)；

2、確定初值：x=0，y=r、d=5/4-r；

3、While(x<=y)

{

利用八分對(duì)稱性，用規(guī)定的顏色color畫八個(gè)象素點(diǎn)(x，y)；

若d≥0

{

y=y-1；

d=d+2(x-y)+5；

}

否則

d=d+2x+3；

x=x+1；

}1/31/2023572.2.2中點(diǎn)算法生成圓四、中點(diǎn)畫圓算法完善在上述算法中，使用了浮點(diǎn)數(shù)來表示決策變量d。為了簡(jiǎn)化算法，擺脫浮點(diǎn)數(shù)，在算法中全部使用整數(shù)，我們使用e=d-1/4代替d。顯然，初值d0=5/4-r對(duì)應(yīng)于e0=1-r。決策變量d<0對(duì)應(yīng)于e<-1/4。算法中其它與d有關(guān)的式子可把d直接換成e。又由于e的初值為整數(shù)，且在運(yùn)算過程中的迭代值也是整數(shù)，故e始終是整數(shù)，所以e<-1/4等價(jià)于e<0。因此，可以寫出完全用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法。

要求：寫出用整數(shù)實(shí)現(xiàn)的中點(diǎn)畫圓算法程序，并上機(jī)調(diào)試，觀看運(yùn)行結(jié)果。1/31/2023582.2.2中點(diǎn)算法生成圓五、中點(diǎn)畫圓算法程序voidMidpointCircle(intx0,inty0,intr,intcolor)

{

intx,y;

floatd;

x=0;

y=r;

d=5.0/4-r;

1/31/2023592.2.2中點(diǎn)算法生成圓while(x<=y)

{

putdot(x0,y0,x,y,color);

if(d<0)

d+=x*2.0+3;

else

{

d+=2.0*(x-y)+5;

y--;

}

x++;

}

}1/31/2023602.2.2中點(diǎn)算法生成圓putdot(x0,y0,x,y,color)

{

putpixel(x0+x,y0+y,color);

putpixel(x0+x,y0-y,color);

putpixel(x0-x,y0+y,color);

putpixel(x0-x,y0-y,color);

putpixel(x0+y,y0+x,color);

putpixel(x0+y,y0-x,color);

putpixel(x0-y,y0+x,color);

putpixel(x0-y,y0-x,color);

}1/31/2023612.2.3正負(fù)算法生成圓正負(fù)法是利用平面曲線將平面劃分成正負(fù)區(qū)域，對(duì)當(dāng)前點(diǎn)產(chǎn)生的圓函數(shù)進(jìn)行符號(hào)判別，利用負(fù)反饋調(diào)整以決定下一個(gè)點(diǎn)的產(chǎn)生來直接生成圓弧。一、正負(fù)畫圓算法描述設(shè)要顯示圓的圓心在原點(diǎn)(0，0)，半徑為R，初始點(diǎn)的坐標(biāo)為(0，R)，順時(shí)針生成八分之一圓，令：F(x，y)=x2+y2-R2則圓的方程為：F(x，y)=0(2-27)當(dāng)點(diǎn)(x，y)在圓內(nèi)時(shí)，則F(x，y)<0；

當(dāng)點(diǎn)(x，y)在圓外時(shí)，則F(x，y)>0；

當(dāng)點(diǎn)(x，y)在圓上時(shí)，則F(x，y)=0；1/31/2023622.2.3正負(fù)算法生成圓二、正負(fù)畫圓算法思想現(xiàn)以下圖的AB弧為例，來說明正負(fù)畫圓法(順時(shí)針生成圓)。1/31/2023632.2.3正負(fù)算法生成圓假設(shè)當(dāng)前點(diǎn)為Pi(xi，yi)，取下一個(gè)點(diǎn)Pi+1(xi+1，yi+1)的原則是：

1、當(dāng)F(xi，yi)≤0時(shí)：取xi+1=xi+1，yi+1=yi。即向右走一步，從圓內(nèi)走向圓外。對(duì)應(yīng)圖(a)中的從Pi到Pi+1。

2、當(dāng)F(xi，yi)>0時(shí)：取xi+1=xi，yi+1=yi-1。即向下走一步，從圓外走向圓內(nèi)。對(duì)應(yīng)圖(b)中的從Pi到Pi+1。由于向圓內(nèi)或向圓外走取決于F(xi，yi)的正負(fù)，因此稱為正負(fù)法。下面分兩種情況求出F(xi，yi)的遞推公式：

1/31/2023642.2.3正負(fù)算法生成圓(1)當(dāng)F(xi，yi)≤0時(shí)，向右走，取xi+1=xi+1，yi+1=yi，則F(xi+1，yi+1)=F(xi+1，yi)

=(xi+1)2+yi2-R2

=(xi2+yi2-R2)+2xi+1

=F(xi，yi)+2xi+1(2-28)1/31/2023652.2.3正負(fù)算法生成圓(2)當(dāng)F(xi，yi)>0時(shí)，向下走，取xi+1=xi，yi+1=yi-1，則F(xi+1，yi+1)=F(xi，yi-1)

=xi2+(yi-1)2-R2

=(xi2+yi2-R2)-2yi+1

=F(xi，yi)-2yi+1(2-29)1/31/2023662.2.3正負(fù)算法生成圓初始時(shí)，x=0，y=R，故F(0，R)=(02+R2)-R2=0(2-30)公式(2-28)、(2-29)和(2-30)就構(gòu)成正負(fù)畫圓算法的核心。給象素坐標(biāo)(x，y)及F賦初始值后，進(jìn)入循環(huán)畫點(diǎn)；畫點(diǎn)后，根據(jù)F的符號(hào)進(jìn)行F值的遞推和下一個(gè)點(diǎn)的獲取，直到x>y為止。同前面介紹的一樣，利用圓的八分對(duì)稱性，循環(huán)一次，畫八個(gè)點(diǎn)。1/31/2023672.2.3正負(fù)算法生成圓三、正負(fù)畫圓算法實(shí)現(xiàn)注意：初值不同、圓的生成方向不同時(shí)，當(dāng)前點(diǎn)和下一個(gè)點(diǎn)的獲取原則是不同的，見下圖。例如，初始點(diǎn)(R，0)，逆時(shí)針生成圓，從圖（b）可知：若當(dāng)前點(diǎn)Pi在圓內(nèi)，則下一點(diǎn)Pi+1(xi，yi+1)，即向上走一步；

若當(dāng)前點(diǎn)Pi在圓外，則下一點(diǎn)Pi+1(xi-1，yi)，即向左走一步；1/31/2023682.2.3正負(fù)算法生成圓(a)順時(shí)針生成圓(b)逆時(shí)針生成圓1/31/2023692.2.3正負(fù)算法生成圓四、正負(fù)畫圓算法特點(diǎn)物理意義清楚，程序中只含整數(shù)運(yùn)算，因此算法速度快。五、正負(fù)畫圓算法程序

//順時(shí)針生成圓

voidPNARC(intx0,inty0,intr,intcolor)

{

intx=0,y=r,f=0;

1/31/2023702.2.3正負(fù)算法生成圓while(x<=y)

{

putdot(x0,y0,x,y,color);

if(f<=0)

{

f=f+2*x+1;

x++;

}

else

{

f=f-2*y+1;

y--;

}

}

}1/31/2023712.2圓的生成習(xí)題1.用自己的語(yǔ)言描述中點(diǎn)畫圓算法。1/31/2023722.3區(qū)域填充前面介紹的直線和圓都屬于線劃圖，然而，光柵顯示的一個(gè)重要特點(diǎn)是能進(jìn)行面著色，區(qū)域填充就是在一個(gè)閉合區(qū)域內(nèi)填充某種顏色或圖案。區(qū)域填充一般分兩類：多邊形填充和種子填充。一、多邊形填充1、填充條件多邊形的頂點(diǎn)序列(Pi，i=0，1，…，n)、填充色。2、多邊形內(nèi)點(diǎn)的判別準(zhǔn)則對(duì)多邊形進(jìn)行填充，關(guān)鍵是找出多邊形內(nèi)的象素。在順序給定多邊形頂點(diǎn)坐標(biāo)的情況下，如何判明一個(gè)象素點(diǎn)是處于多邊形的內(nèi)部還是外部呢？1/31/2023732.3區(qū)域填充從測(cè)試點(diǎn)引出一條伸向無窮遠(yuǎn)處的射線(假設(shè)是水平向右的射線)，因?yàn)槎噙呅问情]合的，那么：

若射線與多邊形邊界的交點(diǎn)個(gè)數(shù)為奇數(shù)時(shí)，則該點(diǎn)為內(nèi)點(diǎn)(例：圖中測(cè)試點(diǎn)4引出的射線)；

反之，交點(diǎn)個(gè)數(shù)為偶數(shù)時(shí)，則該點(diǎn)為外點(diǎn)。(例：測(cè)試點(diǎn)2引出的射線)。1/31/2023742.3區(qū)域填充多邊形內(nèi)點(diǎn)的判別準(zhǔn)則和奇異點(diǎn)1/31/2023752.3區(qū)域填充3、奇異點(diǎn)的處理上述的判別準(zhǔn)則，在大多數(shù)情況下是正確的，但當(dāng)水平掃描線正好通過多邊形頂點(diǎn)時(shí)，要特別注意。例如，圖中過頂點(diǎn)的射線1、射線6，它們與多邊形的交點(diǎn)個(gè)數(shù)為奇數(shù)，按照判別準(zhǔn)則它們應(yīng)該是內(nèi)點(diǎn)，但實(shí)際上卻是外點(diǎn)。而圖中過頂點(diǎn)的射線3、射線5，對(duì)于判別準(zhǔn)則的使用又是正確的。1/31/2023762.3區(qū)域填充綜合以上情況，我們將多邊形的頂點(diǎn)分為兩大類：(1)局部極值點(diǎn)：如圖中的點(diǎn)P1、P2、P4和P6。對(duì)于這些點(diǎn)來說，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的同一側(cè)。

(2)非極值點(diǎn)：如圖中的點(diǎn)P3、P5。對(duì)于這些點(diǎn)來說，進(jìn)入該點(diǎn)的邊線和離開該點(diǎn)的邊線位于過該點(diǎn)掃描線的兩側(cè)。處理奇異點(diǎn)規(guī)則：（1）對(duì)于局部極值點(diǎn)，應(yīng)看成兩個(gè)點(diǎn)；（2）對(duì)于非極值點(diǎn)，應(yīng)看成一個(gè)點(diǎn)。1/31/2023772.3區(qū)域填充4、逐點(diǎn)判別算法步驟：(1)求出多邊形的最小包圍盒：從Pi(xi，yi)中求極值，xmin、ymin、xmax、ymax。(2)對(duì)包圍盒中的每個(gè)象素引水平射線進(jìn)行測(cè)試。(3)求出該射線與多邊形每條邊的有效交點(diǎn)個(gè)數(shù)。(4)如果個(gè)數(shù)為奇數(shù)：該點(diǎn)置為填充色。(5)否則：該點(diǎn)置為背景色。逐點(diǎn)判別算法雖然簡(jiǎn)單，但不可取，原因是速度慢。它割斷了各象素之間的聯(lián)系，孤立地考慮問題，由于要對(duì)每個(gè)象素進(jìn)行多次求交運(yùn)算，求交時(shí)要做大量的乘除運(yùn)算，從而影響了填充速度。1/31/2023782.3區(qū)域填充二、種子填充種子填充是將區(qū)域內(nèi)的一點(diǎn)(種子)賦予給定的顏色，然后將這種顏色擴(kuò)展到整個(gè)區(qū)域內(nèi)的過程。

1、填充條件區(qū)域內(nèi)一點(diǎn)的坐標(biāo)即種子坐標(biāo)、邊界色、填充色。

2、連通方式區(qū)域是互相連通著的象素的集合，連通方式可分為四連通和八連通。1/31/2023792.3區(qū)域填充四連通：從區(qū)域內(nèi)一點(diǎn)出發(fā)，可通過四個(gè)方向：上、下、左、右到達(dá)該區(qū)域內(nèi)部的任意象素。八連通：區(qū)域內(nèi)部從一個(gè)象素到達(dá)另一個(gè)象素的移動(dòng)路徑，除了上、下、左、右四個(gè)方向外，還允許沿著對(duì)角線方向。1/31/2023802.3區(qū)域填充注意：（1）八連通區(qū)域中，既然區(qū)域內(nèi)的兩個(gè)象素可以通過對(duì)角線相通，那么，區(qū)域邊界上的象素則不能通過對(duì)角線相連，否則填充就會(huì)溢出到區(qū)域外，因此，八連通區(qū)域的邊界線必須是四連通的，見下圖(a)；（2）而四連通區(qū)域，其邊界象素是四連通和八連通的都可以，見下圖(b)。1/31/2023812.3區(qū)域填充

(a)八連通區(qū)域四連通邊界(b)四連通區(qū)域八連通(或四連通)邊界

1/31/2023822.3區(qū)域填充3、內(nèi)點(diǎn)(x,y)的檢測(cè)條件(1)if(getpixel(x,y)!=邊界色&&getpixel(x,y)!=填充色)(2)if(getpixel(x,y)!=背景色)這兩個(gè)條件任何一個(gè)都可以用來檢測(cè)象素點(diǎn)(x,y)是不是尚未填充。推薦使用條件(1)進(jìn)行象素點(diǎn)檢測(cè)。1/31/2023832.3.1邊相關(guān)掃描線多邊形填充算法邊相關(guān)掃描線填充算法屬于多邊形填充類。它比逐點(diǎn)判別算法速度提高很多，是一種較經(jīng)典的多邊形填充算法。該算法利用了掃描線的相關(guān)性和多邊形邊的相關(guān)性，而不是逐點(diǎn)進(jìn)行處理。一、邊相關(guān)掃描線填充算法描述

掃描線的相關(guān)性：某條掃描線上相鄰的象素，幾乎都具有同樣的內(nèi)外性質(zhì)，這種性質(zhì)只有遇到多邊形邊線與該掃描線的交點(diǎn)時(shí)才會(huì)發(fā)生改變。見下圖(a)。1/31/2023842.3.1邊相關(guān)掃描線多邊形填充算法邊的相關(guān)性：由于相鄰掃描線上的交點(diǎn)是與多邊形的邊線相關(guān)的。對(duì)同一條邊，前一條掃描線yi與該邊的交點(diǎn)為xi，而后一條掃描線yi+1=yi+1與該邊的交點(diǎn)則為xi+1=xi+1/m，利用這種相關(guān)性可以省去大量的求交運(yùn)算。見下圖(b)所示。1/31/2023852.3.1邊相關(guān)掃描線多邊形填充算法(a)掃描線的相關(guān)性(b)邊的相關(guān)性

邊相關(guān)掃描線填充算法的實(shí)現(xiàn)需要建立兩個(gè)表：邊表（ET）和活動(dòng)邊表（AET）。1/31/2023862.3.1邊相關(guān)掃描線多邊形填充算法1、邊表（ET：EdgeTable）用來對(duì)除水平邊外的所有邊進(jìn)行登記，來建立邊的記錄。邊的記錄定義為：掃描線y對(duì)應(yīng)的ET表1/31/2023872.3.1邊相關(guān)掃描線多邊形填充算法第一項(xiàng)：某邊的最大y值（ymax）。注意要進(jìn)行奇異點(diǎn)處理：對(duì)于非極值點(diǎn)應(yīng)該ymax=ymax-1。

第二項(xiàng)：某邊的最小的y對(duì)應(yīng)的x值。

第三項(xiàng)：某邊斜率的倒數(shù):1/m。

第四項(xiàng)：指針。用來指向同一條掃描線相交的其它邊，如果其它邊不存在，則該項(xiàng)置空。1/31/2023882.3.1邊相關(guān)掃描線多邊形填充算法二、邊相關(guān)掃描線填充算法思想1、根據(jù)給出的多邊形頂點(diǎn)坐標(biāo)，建立ET表；求出頂點(diǎn)坐標(biāo)中最大y值ymax和最小y值ymin。2、初始化AET表指針，使它為空。3、使用掃描線的yj值作為循環(huán)變量，使其初值為ymin。對(duì)于循環(huán)變量yj的每一整數(shù)值，重復(fù)作以下事情，直到y(tǒng)j大于ymax，或ET表與AET表都為空為止：1/31/2023892.3.1邊相關(guān)掃描線多邊形填充算法(1)如果ET表中yj桶非空，則將yj桶中的全部記錄合并到AET表中。(2)對(duì)AET表鏈中的記錄按x的大小從小到大排序。(3)依次取出AET表各記錄中的xi坐標(biāo)值，兩兩配對(duì)填充，即將每對(duì)xi之間的象素填上所要求的顏色。

1/31/2023902.3.1邊相關(guān)掃描線多邊形填充算法(4)如果AET表中某記錄的ymax=yj，則刪除該記錄。(5)對(duì)于仍留在AET表中的每個(gè)記錄，用xi+1/m代替xi進(jìn)行修改，這就是該記錄的邊線與下一條掃描線yj+1的交點(diǎn)。(6)使yj加1，以便進(jìn)入下一輪循環(huán)。1/31/2023912.3.1邊相關(guān)掃描線多邊形填充算法對(duì)下圖(a)的多邊形利用邊相關(guān)掃描線填充算法進(jìn)行處理：1、首先建立ET表。注意：在做奇異點(diǎn)處理時(shí)，當(dāng)該邊最大y值對(duì)應(yīng)的頂點(diǎn)為非極值點(diǎn)時(shí)，邊記錄的第一項(xiàng)：ymax=ymax-1。例如：P3P4邊、P3P2邊、P4P5邊，見下圖(b)。2、接著建立AET表。AET表的建立過程就是有效地進(jìn)行填充的操作，在這個(gè)期間不斷地做以下工作：1/31/2023922.3.1邊相關(guān)掃描線多邊形填充算法（1）合并ET表；（2）x遞增排序；（3）實(shí)施填充；（4）刪除ymax＝y(tǒng)j的邊；（5）修改邊記錄xi=xi+1/m；（6）yj+1進(jìn)入下一輪循環(huán)。結(jié)果見下圖(c)。1/31/2023932.3.1邊相關(guān)掃描線多邊形填充算法(a)多邊形(b)ET表(c)AET表

1/31/2023942.3.1邊相關(guān)掃描線多邊形填充算法四、邊相關(guān)掃描線填充算法實(shí)現(xiàn)1、根據(jù)給定的多邊形頂點(diǎn)坐標(biāo)，建立ET表。2、AET表初始化，每個(gè)桶置空。3、for(y=ymin;y<=ymax;y++){

合并當(dāng)前掃描線y的ET表；將y桶中每個(gè)記錄按x項(xiàng)升序排列；在當(dāng)前y值下，將兩兩記錄的x值之間的象素進(jìn)行填充；刪除y=ymax的邊記錄；修改邊記錄x=x+1/m；}1/31/2023952.3.1邊相關(guān)掃描線多邊形填充算法五、邊相關(guān)掃描線填充算法特點(diǎn)該算法充分利用多邊形的邊相關(guān)性和掃描線的相關(guān)性，使用ET表對(duì)多邊形的非水平邊進(jìn)行登記；用AET表的建立和更新來支持填充，大大地減少了求交點(diǎn)的計(jì)算量，有效地提高了填充速度。1/31/2023962.3.2掃描線種子填充算法該算法屬于種子填充算法，它是以掃描線上的區(qū)段為單位進(jìn)行操作。所謂區(qū)段，就是一條掃描線上相連著的若干內(nèi)部象素的集合。一、掃描線種子填充算法思想掃描線種子填充算法的基本思想是：首先填充當(dāng)前掃描線上的位于給定區(qū)域內(nèi)的一區(qū)段，然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于該區(qū)段內(nèi)是否存在需要填充的新區(qū)段，如果存在，則依次把它們保存起來。反復(fù)這個(gè)過程，直到所保存的各區(qū)段都填充完畢。1/31/2023972.3.2掃描線種子填充算法二、掃描線種子填充算法實(shí)現(xiàn)借助于堆棧，上述算法實(shí)現(xiàn)步驟如下：1、初始化堆棧。

2、種子壓入堆棧。

3、while（堆棧非空）

{

(1)從堆棧彈出種子象素。

(2)如果種子象素尚未填充，則：a.求出種子區(qū)段：xleft、xright;b.填充整個(gè)區(qū)段。1/31/2023982.3.2掃描線種子填充算法c.檢查相鄰的上掃描線的xleft≤x≤xright區(qū)間內(nèi),是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleft≤x≤xright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。d.檢查相鄰的下掃描線的xleft≤x≤xright區(qū)間內(nèi)，是否存在需要填充的新區(qū)段，如果存在的話，則把每個(gè)新區(qū)段在xleft≤x≤xright范圍內(nèi)的最右邊的象素，作為新的種子象素依次壓入堆棧。}1/31/2023992.3.2掃描線種子填充算法四、掃描線種子填充算法特點(diǎn)1、該算法考慮了掃描線上象素的相關(guān)性，種子象素不再代表一個(gè)孤立的象素，而是代表一個(gè)尚未填充的區(qū)段。2、進(jìn)棧時(shí)，只將每個(gè)區(qū)段選一個(gè)象素進(jìn)棧（每個(gè)區(qū)段最右邊或最左邊的象素），這樣解決了堆棧溢出的問題。3、種子出棧時(shí)，則填充整個(gè)區(qū)段。4、這樣有機(jī)的結(jié)合：一邊對(duì)尚未填充象素的登記（象素進(jìn)棧），一邊進(jìn)行填充（象素出棧），既可以節(jié)省堆?？臻g，又可以實(shí)施快速填充。

1/31/20231002.3.3邊標(biāo)志填充算法在光柵顯示平面上，多邊形是封閉的，它是用某一邊界色圍成的一個(gè)閉合區(qū)域，填充是逐行進(jìn)行的，即用掃描線逐行對(duì)多邊形求交，在交點(diǎn)對(duì)之間填充。邊標(biāo)志填充算法就是在逐行處理時(shí)，利用邊界色作為標(biāo)志來進(jìn)行填充的。例如某掃描線從左到右掃描時(shí)碰到邊界色，立刻改變標(biāo)志的狀態(tài)，接下來再根據(jù)標(biāo)志的狀態(tài)決定某象素點(diǎn)是否填充。1/31/20231012.3.3邊標(biāo)志填充算法一、邊標(biāo)志填充算法思想掃描線具有連貫性，這種連貫性只有在掃描線與多邊形相交處才會(huì)發(fā)生變化，而每次的變化結(jié)果：無非是在前景色和背景色之間相互“切換”。邊標(biāo)志填充算法正是基于這一發(fā)現(xiàn)，先在屏幕上生成多邊形輪廓線，然后逐條掃描處理。處理中：逐點(diǎn)讀取象素值，若為邊界色，則對(duì)該象素值進(jìn)行顏色切換。1/31/20231022.3.3邊標(biāo)志填充算法二、邊標(biāo)志填充算法實(shí)現(xiàn)1、用邊界色畫出多邊形輪廓線，也就是將多邊形邊界所經(jīng)過的象素打上邊標(biāo)志。2、為了縮小范圍，加快填充速度，須找出多邊形的最小包圍盒：xmin、ymin、xmax、ymax。如下圖所示。1/31/20231032.3.3邊標(biāo)志填充算法邊標(biāo)志填充算法3、逐條掃描線進(jìn)行處理，對(duì)每條掃描線依從左往右的順序，逐個(gè)訪問該掃描線上的象素。每遇到邊界象素，標(biāo)志取反。然后，按照標(biāo)志是否為真，決定象素是否為填充色。1/31/20231042.3.3邊標(biāo)志填充算法三、邊標(biāo)志填充算法特點(diǎn)該算法思想簡(jiǎn)單，實(shí)現(xiàn)容易。既不需要求交點(diǎn)、交點(diǎn)排序、邊的登記，也不需要使用鏈表、堆棧等數(shù)據(jù)結(jié)構(gòu)。四、邊標(biāo)志填充算法程序EdgeMarkFill(intp[][2],intn,intboundarycolor,intnewcolor)

1/31/20231052.3.3邊標(biāo)志填充算法{

inti,x,y,flag,xmin,xmax,ymin,ymax;

setcolor(boundarycolor);/*設(shè)置畫筆色*/

for(i=0;i<n;i++)

line(p[i][0],p[i][1],p[(i+1)%n][0],p[(i+1)%n])[1]);/*畫出多邊形的n條邊*/

用求極值的算法，從多邊形頂點(diǎn)數(shù)組p中，求出xmin,xmax,ymin,ymax;

1/31/20231062.3.3邊標(biāo)志填充算法for(y=ymin;y<=ymax;y++)

{

flag=-1;

for(x=xmin;x<=xmax;x++)

{

if(getpixel(x,y)==boundarycolor)

flag=(-1)

*flag;

if(flag==1)

putpixel(x,y,newcolor);

}

}

}1/31/20231072.3.3邊標(biāo)志填充算法五、邊標(biāo)志填充算法錯(cuò)誤處理1、該算法雖然簡(jiǎn)單，但程序運(yùn)行后會(huì)出現(xiàn)局部錯(cuò)誤。從下圖可以發(fā)現(xiàn)，對(duì)于多邊形頂點(diǎn)為局部極值點(diǎn)時(shí)，掃描線與多邊形的相交次數(shù)不再是偶數(shù)，而是奇數(shù)，填充時(shí)會(huì)出現(xiàn)“抽絲”現(xiàn)象。即某掃描線上不該填充的區(qū)段填上色，而應(yīng)該填充的區(qū)段卻沒有填上色。

解決的辦法：判斷多邊形頂點(diǎn)的性質(zhì)，如果是局部極值點(diǎn)，那么掃描線碰上它則不改變標(biāo)志。1/31/20231082.3.3邊標(biāo)志填充算法2、特別當(dāng)心多邊形邊界的掃描轉(zhuǎn)換。在這里就不能考慮：不同的斜率產(chǎn)生的直線要亮度均勻，如下圖(a)所示。否則當(dāng)掃描線y遇到斜率小于1的邊界線時(shí)，碰到幾個(gè)邊界點(diǎn)，會(huì)引起標(biāo)志的無序改變，將導(dǎo)致填充的錯(cuò)誤。解決的辦法：對(duì)于不同斜率的邊界，都要使用斜率大于1的直線掃描轉(zhuǎn)換方法：每次y方向增長(zhǎng)一步，x方向增長(zhǎng)1/m步距，以保證掃描線y遇到斜率小于1的邊界時(shí)，只能遇到一個(gè)點(diǎn)。請(qǐng)看下圖(b)。

1/31/20231092.3.3邊標(biāo)志填充算法在邊標(biāo)志填充算法中要注意多邊形邊界的掃描轉(zhuǎn)換1/31/20231102.3.4圖案填充前面介紹的區(qū)域填充算法，都是把區(qū)域內(nèi)部的象素全部置成同一種顏色。但在實(shí)際應(yīng)用中，有時(shí)需要用圖案來填充平面區(qū)域。這可以將前面的填充算法中寫象素的那部分代碼稍加修改來實(shí)現(xiàn):

在確定了區(qū)域內(nèi)點(diǎn)后，不是馬上對(duì)該象素填色，而是先將該象素映射到圖案位圖的對(duì)應(yīng)位置。根據(jù)圖案該位置的象素值，決定填充顏色。1/31/20231112.3.4圖案填充一、圖案填充方式：1、透明方式:

若是以透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫象素，否則，不改變?cè)撓笏氐闹怠?、不透明方式:

而若是以不透明方式填充圖案，則當(dāng)圖案位圖的對(duì)應(yīng)位置為1時(shí)，用前景色寫象素，否則，用背景色寫象素。

1/31/20231122.3.4圖案填充二、圖案定位法：

1、相對(duì)定位法:

把圖案原點(diǎn)與填充區(qū)域邊界或內(nèi)部的某點(diǎn)對(duì)齊。這樣，當(dāng)被填充的多邊形移動(dòng)時(shí)，圖案也跟著移動(dòng)，看起來比較自然。對(duì)于多邊形，可取邊界上最左邊的頂點(diǎn)，而對(duì)于圓和橢圓這樣具有光滑邊界的區(qū)域，則最好取區(qū)域內(nèi)部某一點(diǎn)，如取中心與圖案原點(diǎn)對(duì)齊。1/31/20231132.3.4圖案填充2、絕對(duì)定位法：

把圖案原點(diǎn)與屏幕原點(diǎn)對(duì)齊。該方法可以將整個(gè)屏幕看成被要填充的圖案布滿，只是要填充的區(qū)域是透明的，可以讓圖案顯露出來，其它區(qū)域?qū)Υ藞D案卻是不透明的，圖案被全部擋住。這種方法比較簡(jiǎn)單，并且在相鄰區(qū)域用同一圖案填充時(shí)，可以達(dá)到無縫連接的效果。但它有一個(gè)潛在的毛病，即當(dāng)區(qū)域移動(dòng)時(shí)，圖案不會(huì)跟著移動(dòng)。其效果是區(qū)域內(nèi)的圖案變了。1/31/20231142.3.4圖案填充三、圖案填充算法實(shí)現(xiàn)下面討論在第二種絕對(duì)定位法下用不透明方式對(duì)平面區(qū)域填充圖案：假設(shè)填充圖案是一個(gè)M×N的位圖，用M×N的數(shù)組存放。M、N一般比需要填充區(qū)域的尺寸小得多（8×8、16×16、32×32），所以圖案總是設(shè)計(jì)成周期性的，使之能通過重復(fù)使用來構(gòu)成任意尺寸的圖案。當(dāng)確定了區(qū)域內(nèi)點(diǎn)p（x,y）后，則圖案位圖上的對(duì)應(yīng)位置為p'（x%M，y%N），其中%為C語(yǔ)言整除取余運(yùn)算符,然后取出圖案位圖該位置的象素進(jìn)行填充。1/31/20231152.3.4圖案填充四、圖案填充算法程序//采用不透明方式絕對(duì)定位法填充圖案的程序偽代碼:maskpixel(intx,inty,intnewcolor,intbackgroundcolor)

{

intxx,yy;

intmaskcode[8][8]={0,0,0,0,1,0,0,0,/*磚縫圖案*/

0,0,0,0,1,0,0,0,

0,0,0,0,1,0,0,0,

1,1,1,1,1,1,1,1,

1,0,0,0,0,0,0,0,

1,0,0,0,0,0,0,0,

1,0,0,0,0,0,0,0,

1,1,1,1,1,1,1,1

};

1/31/20231162.3.4圖案填充xx=x%8;/*多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)x映射到圖案坐標(biāo)xx*/

yy=y%8;/*多邊形區(qū)域內(nèi)點(diǎn)坐標(biāo)y到圖案坐標(biāo)yy*/

if(maskcode[yy][xx])

putpixel(x,y,newcolor);/*newcolor為前景色*/

else

putpixel(x,y,backgroundcolor);/*backgroundcolor為背景色*/

}1/31/20231172.4.1點(diǎn)陣字符我們討論的字符是指字母、數(shù)字、漢字、標(biāo)點(diǎn)等符號(hào)。計(jì)算機(jī)中，字符由一個(gè)數(shù)字編碼唯一標(biāo)識(shí)，對(duì)于一個(gè)字符來說，它所對(duì)應(yīng)的編碼是由它所屬的字符集決定。1、ASCII碼目前，國(guó)際上普遍采用的字符編碼是ASCII碼（AmericanStandardCodeforInformationInterchange）美國(guó)信息交換標(biāo)準(zhǔn)代碼。它是用七位二進(jìn)制數(shù)進(jìn)行編碼，共能表示128個(gè)字符，其中編碼0～31表示控制字符（不可顯示），編碼32～127表示英文字母、數(shù)字、標(biāo)點(diǎn)符號(hào)等可顯示字符。一個(gè)字符的ASCII碼用一個(gè)字節(jié)（8位）表示，其最高位不用或者作為奇偶校驗(yàn)位。1/31/20231182.4.1點(diǎn)陣字符2、國(guó)標(biāo)碼我國(guó)除了采用ASCII碼外，還制定了漢