第3章_點陣圖形的基本算法

1、第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 第第3章章 點陣圖形的基本算法點陣圖形的基本算法 3.1 基本圖形的點陣轉(zhuǎn)換基本圖形的點陣轉(zhuǎn)換 3.2 直線點陣轉(zhuǎn)換算法直線點陣轉(zhuǎn)換算法 3.3 圓的點陣圖形掃描轉(zhuǎn)換算法圓的點陣圖形掃描轉(zhuǎn)換算法 3.4 橢圓點陣圖形掃描轉(zhuǎn)換算法橢圓點陣圖形掃描轉(zhuǎn)換算法 3.5 多項式曲線的算法多項式曲線的算法 習(xí)習(xí) 題題 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.1 基本圖形的點陣轉(zhuǎn)換基本圖形的點陣轉(zhuǎn)換 評價一個轉(zhuǎn)換算法的優(yōu)劣可以通過如下三個方面來進(jìn)行: (1) 所顯示圖形的精度。轉(zhuǎn)換出的點陣圖形畢竟只是對原始圖形的近似， 有一定的誤差，

2、這個誤差的大小可根據(jù)實際需要而定。 (2) 算法的時間復(fù)雜性， 也就是算法的速度。 (3) 算法的空間復(fù)雜性， 即算法運行過程所需要的內(nèi)存空間的大小。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.2 直線點陣轉(zhuǎn)換算法直線點陣轉(zhuǎn)換算法 3.2.1 描繪線條圖形的要求1. 直線段要顯得筆直 在理論上的直線和點陣圖形中，用像素點表示出的直線是有差別的。圖3.1(a)表示出了一段理論直線段及所有涉及到的像素點。顯然，用所有涉及到的像素點表示的圖形不如用圖3.1(b)中有選擇的部分像素點表示的圖形更像是直線段，也顯得更筆直。當(dāng)然，圖3.2(a)表示出的垂直、水平及45角的直線看起來是筆直的

3、。而圖3.2(b)接近垂直或水平線的直線總是呈現(xiàn)出一種階梯狀或鋸齒狀。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.1 直線段的像素點表示 (a) 理論直線段及所有涉及到的像素點; (b) 應(yīng)當(dāng)選擇的像素點第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.2 直線段表示亮度均勻及連續(xù)性 (a) 垂直、水平及45角的直線段; (b) 其它直線段的像素點表示第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 2. 線段端點位置應(yīng)該準(zhǔn)確 3. 線段亮度均勻 4. 轉(zhuǎn)換算法速度快3.2.2 增量DDA算法 1. 增量DDA算法思路 設(shè)直線的起點坐標(biāo)為(xs，ys)， 終點坐

4、標(biāo)為(xe， ye)， 則直線的方程為y=mx+b (3.2.1) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 其中, 直線的斜率為在y軸上的截距為那么畫直線的最直觀算法是: 給定直線的兩個端點坐標(biāo)后，求得m和b；然后在xsxxe范圍內(nèi)對x均勻取整數(shù)，利用式(3.2.1)進(jìn)行浮點乘法和加法運算，求得y值后再取整數(shù)值即可得到需要的直線上的像素點。 sesexxyym(3.2.2) seessexxxyxyb(3.2.3) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 最簡單的改進(jìn)算法是: 給定直線的兩個端點坐標(biāo)后，求得m和b；當(dāng)|m|1時，在xsxxe范圍內(nèi)將x取整數(shù)，利用式(

5、3.2.1)進(jìn)行浮點乘法和加法運算， 求得y值后再取整數(shù)值；當(dāng)|m|1時，則y先取整數(shù)，利用式(3.2.1)進(jìn)行浮點乘法和加法運算，求得x值后再取整數(shù)值?？梢哉J(rèn)為直線圖形上的點是由有先后順序的一列像素點構(gòu)成的，相鄰的兩點應(yīng)滿足: yi+1=yi+m(xi+1-xi) (3.2.5) mxxyyiiii11 (3.2.4) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 其中, (xi, yi)是第i步求得的像素點坐標(biāo)，(xi+1, yi+1)是第i+1步求得的像素點坐標(biāo)。類似前面的分析，我們應(yīng)要求 并且要求其較大者就是1。也就是說，如果 |m|1，則要求1111iiiiyyxx(3.2.

6、6) 1111iiiiyyxx(3.2.7) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 如果|m|1，則要求 事實上，式(3.2.5)表示所求直線上y值的逐步遞推關(guān)系，此式稱為數(shù)字微分分析器(DDA)。于是，畫直線的DDA算法可分兩種情況描述如下: (a) |m|1的情況： 在xe-xs0時， 有 xi+1=xi+1， yi+1=yi+m (3.2.9) 在xe-xs0時， 有 xi+1=xi-1， yi+1=yi-m (3.2.10) 1111iiiiyyxx(3.2.8) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 (b) |m|1的情況： 在ye-ys0時， 有 y

7、i+1=yi+1， xi+1=xi+1/m (3.2.11) 在ye-ys0時， 有 yi+1=yi-1， xi+1=xi-1/m (3.2.12) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 2. 線段DDA算法的偽代碼描述 下面用偽代碼給出DDA算法。 Procedure DDA-line(xs， ys， xe， ye) BEGIN /求線段在兩坐標(biāo)軸方向改變量的較大者/ IF ABS(xe-xs)=ABS(ye-ys) THEN length=ABS(xe-xs)；ELSE length=ABS(ye-ys)； ENDIF 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法

8、/定義dx或dy中的較大值為1/ dx=(xe-xs)/length； dy=(ye-ys)/length； x=xs+0.5*SIGN(dx)； y=ys+0.5*SIGN(dy)； i=1； WHILE (ilength) PLOT(INTEGER(x)， INTEGER(y)； x=x+dx； y=y+dy； i=i+l； END WHILE END 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 其中，函數(shù)SIGN ( )是符號函數(shù)，其表達(dá)式為: 用DDA算法表示的直線如圖3.3所示。 0 10 00 1)(xxxxSIGN(3.2.13) 第第3 3章章 點陣圖形的基本算法點陣

9、圖形的基本算法 圖3.3 用DDA算法表示的直線(a) 實際要求的直線及其近似點；(b) 離散化后用像素點表示的直線 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.2.3 Bresenham直線算法 1. Bresenham直線算法思路 Bresenham直線算法最初是為數(shù)字繪圖儀而設(shè)計的。它的目標(biāo)是選擇表示直線的最佳像素點位置。為此，該算法根據(jù)直線的斜率確定，在x或y方向上每次遞增一個單位，而另一方向上根據(jù)理論直線段與最近像素點的距離每次的增量為0或1。我們首先討論直線斜率0m1, 且xexs時的整數(shù)Bresenham算法，然后再推廣到畫任意線段的算法。 第第3 3章章 點陣圖形

10、的基本算法點陣圖形的基本算法 當(dāng)直線斜率0m1，且xexs時，根據(jù)式(3.2.9)有 在 處，直線上點的坐標(biāo) 。該點與上、下兩點 和 的距離分別是dH和dL: myyxxiiii111(3.2.14) 1ixxbxmyi) 1() 1, 1(iiyx), 1(iiyx iiiLiiiHybxmyydbxmyyyd) 1() 1() 1() 1(3.2.16) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 這個差有如下幾何意義(見圖3.4): (1) 當(dāng)此值為正時，真正的直線上點離像素點 較 近 ， 說 明 下 一 個 直 線 上 的 像 素 點 應(yīng)取 。 (2) 當(dāng)此值為負(fù)時，真正的直

11、線上點離像素點 較近，說明下一個直線像素點應(yīng)取 。 (3) 當(dāng)此值為零時，真正的直線上點離上、下兩個像素點的距離相等，我們規(guī)定取 作為下一個直線像素點。 ) 1, 1(iiyx) 1, 1(iiyx), 1(iiyx ), 1(iiyx ), 1(iiyx 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.4 Bresenham直線算法示意圖第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 因此，只要利用(dL-dH)的符號就可以決定下一個像素點的選擇。如果我們定義一個新的判別式: (3.2.17) 因此, 式中的x=(xe-xs)0，pi與(dL-dH)有相同符號； y=ye-

12、ys；常數(shù)c=2y+x(2b-1)。pi的一個優(yōu)點是省去了(dL-dH)中為了計算m所需要的除法運算。我們知道除法運算用硬件實現(xiàn)是比較復(fù)雜的。 cyxxyddxpiiHLi22)(第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 現(xiàn)在我們要進(jìn)一步化簡上述誤差判別式以得到遞推公式，消除常數(shù)c。以i+1代換式(3.2.17)中的i，得到將此式與式(3.2.17)相減， 并利用 可得 再假設(shè)直線的初始端點恰好是其像素點的坐標(biāo)，即滿足: cyxxypiii11122 (3.2.18) 11iixx)(2211iiiiyyxypp(3.2.19)bxmy11(3.2.20)第第3 3章章 點陣圖形的

13、基本算法點陣圖形的基本算法 于是可得pi的初值p1: p1=2y-x (3.2.21) 這樣，利用誤差判別變量，并注意到每一步x的增量為xi+1-xi=1就可得到如下的算法表示: (2) 如果pi0， 則有 1211iixxxyp(3.2.22) )(222111xypxyppyyiiiii(3.2.23) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 (3) 如果pi0，則有該算法的主要步驟如下: (1) 輸入線段的兩個端點, 分別存于(xs, ys)和(xe， ye)中。 (2) 將第一點作為起始點， 即有(x1，y1)=(xs，ys)。 yppyyiiii2111第第3 3章章

14、點陣圖形的基本算法點陣圖形的基本算法 (3) 分別計算x、y及p1，若p10，則下一點為(x1+1，y1)； 否則，下一點為(x1+1，y1+1)。 (4) 以單位步長增加x坐標(biāo)，按式(3.2.23)或式(3.2.24)計算pi。若pi 0，則下一點的y坐標(biāo)不變，否則y坐標(biāo)加1。 (5) 重復(fù)步驟(4)直到x逐步增加到xe為止。2. Bresenham直線整數(shù)偽代碼描述 下面給出的是完整的整數(shù)坐標(biāo)的直線Bresenham算法。用Bresenham算法表示的直線見圖3.5。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.5 用Bresenham 算法表示的直線 (a) 實際要求的直

15、線及其近似點； (b) 離散化后用像素點表示的直線 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 Procedure Bresenhamline(xs， ys， xe， ye) BEGIN dx=ABS(xe-xs)； dy=ABS(ye-ys)； x=xs； y=ys； s1=SIGN(xe-xs)； s2=SIGN(ye-ys)； If dydx THEN temp=dx； dx=dy:dy=temp； interchange=1； ELSE interchange=0； ENDIF 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 p=2*dy-dx； FOR i=1 TO

16、dx PLOT(x， y)； IF p=0 THEN IF interchange=1 THEN x=x+s1； ELSE y=y+s2； ENDIF p=p-2*dx； ENDIF 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 IF interchange=1 THEN y=y+s2； ELSE x=x+s1； ENDIF p=p+2*dy； NEXT i； END 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.3 圓的點陣圖形掃描轉(zhuǎn)換算法圓的點陣圖形掃描轉(zhuǎn)換算法 1. 直角坐標(biāo)方法 圓也是基本圖形之一。為了簡單起見，假設(shè)圓的圓心在坐標(biāo)原點，半徑為R，于是可得其方程為 x

17、2+y2=R2 (3.3.1) 解出y， 得到 (3.3.2) 畫出的圓如圖3.6所示。 22xRy第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.6 四分之一圓弧的離散表示 (a) 圓弧曲線; (b) 圓弧的離散表示 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 作為整圓部分的圓弧也可利用對稱性算出，只是這時算出一段八分圓弧后不需要全部的對稱點。在我們算出如圖3.7所示的圓弧。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.7 圓弧八分對稱性關(guān)系示意圖第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 2. 折線逼近法圓可以用其內(nèi)接正多邊形來逼近。更廣泛地

18、說，曲線也可用折線來逼近，每段折線越短，曲線逼近越好，但執(zhí)行時間也越長。我們從折線逼近一段圓弧出發(fā)來討論這種逼近的基本思想。假設(shè)圓弧的起始和終止角分別為ts和te，半徑為R，用折線代替圓弧容許的最大誤差為。 如果用n段等長折線來逼近圓弧，則每段圓弧曲線對應(yīng)的圓弧角度為=(te-ts)/n。 當(dāng)充分小時，圓弧和對應(yīng)弦的最大誤差是22814sin22cos1 RRRe(3.3.3) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 為了使e，把代入上式后得到3. 實例分析 假設(shè)要畫一個半圓弧，其半徑R=256個像素點單位，于是圓弧的角度為te-ts=。若要求誤差不超過兩個像素點單位，即2，則所

19、需要的折線段n為22Rttnse(3.3.4) 13 42562n(3.3.5) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 即用13段折線來逼近這個半圓弧。 那么如何求折線段的端點位置呢?我們知道圓的參數(shù)方程為對圓弧來說，參數(shù)tts, te，而每一折線端點處的參數(shù)為 ti=ts+i i = 0，1，2， ， n (3.3.7) 因此，各折線段的端點坐標(biāo)為 2 , 0 coscosttRytRx (3.3.6) 2 , 0 coscosttRytRxii(3.3.8)第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 顯然, 直接利用公式(3.3.8)求折線的端點的計算是很費時的。

20、為此，我們根據(jù)相鄰折線段的端點間的遞推關(guān)系來遞推地計算折線段的端點: 3.3.2 Bresenham圓弧算法 1. Bresenham圓弧算法思路 coss)(sscos)cos(11iiiiiiiiyinxtinRyinyxtRx(3.3.9) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 考慮圖3.8所示的情況，假定像素點(xi，yi)是在x=xi時最靠近圓周的像素點，那么在x=xi+1時要得到的最靠近圓周的像素點只可能是: H(xi+1，yi)或L(xi+1，yi-1)，因為這一段圓弧曲線隨x的增加，y單調(diào)減小，且x方向改變量大于y方向的改變量。 第第3 3章章 點陣圖形的基本算

21、法點陣圖形的基本算法 圖3.8 Bresenham圓弧算法示意圖第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 (1) yi-1yyi 時的情況： 此時圓弧曲線從H和L兩點之間穿過， 定義 dH=y2i-y20 dL=y2-(yi-1) 20為x=xi+1時圓周上點的y坐標(biāo)分別與H和L點的y坐標(biāo)平方之差，因為R2=(xi+1) 2+y2，所以有 dH=y2i-R2+(xi+1) 2 dL=R2-(xi+1) 2-(yi-1) 2(3.3.10)(3.3.11)第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 由此也可以看出這兩個量的幾何意義是從圓心(原點)到H(或L)距離的平方與到圓

22、周距離的平方之差。如果dHdL，則L比H更接近于實際的圓。如果dHdL，則H比L更接近于實際的圓。因此，我們把判別變量定義為dH和dL的差，用pi表示: pi=dH-dL=2(xi+1) 2+(yi-1)2+y2i-2R2 (3.3.12)并在pi0時選擇像素點H(xi+1，yi)； 否則選擇像素點L(xi+1， yi-1)。 (2) yyi-1時的情況： 此時圓弧曲線從H和L兩點下方通過，顯然要選擇的是H和L中靠下方的點， 即y坐標(biāo)為yi-1-1的點L。此時式(3.3.11)中定義的dH 0， dL 0，故同時有pi 0。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 (3) yyi

23、時的情況： 此時圓弧曲線從H和L兩點上方通過，顯然要選擇的是H和L中y坐標(biāo)為yi-1的點，即H。此時式(3.3.11)中定義的dH0，dL0，故同時有pi0。 總之，無論哪一種情況成立，我們的判別規(guī)則都是一致的，即當(dāng)pi 0時選擇的像素點為H(xi+1，yi-1)； 否則選擇的像素點為L(xi+1，yi)。 繼續(xù)求解下一個像素點，就要求出下一步的判別表達(dá)式pi+1。用i+1代換式(3.3.12)中的i可得 pi+1 =2(xi+1+1) 2+(yi+1-1) 2+y2i+1-2R2 (3.3.13) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 這一計算公式需要作數(shù)次乘法運算，結(jié)合式(

24、3.3.12)，可把上式重寫為 pi+1=pi+4xi+6+2(y2i+1-y2i)-2(yi+1-yi) 算法每次從直接計算p1開始，以后則按照式(3.3.14)遞推計算下一個判別變量。把點(x1， y1)=(0，R)代入式(3.3.12)，可得到 p1=3-2R (3.3.15) 0 10)(40 64iiiiiiipyxppxp(3.3.14) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 因此，算法可表示為(2) 如果pi0， 則有 10)(4111iiiiiiyxppyy(3.3.16) 1231iiixpRp(3.3.17) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本

25、算法 (3) 如果pi0， 則有2. Bresenham畫圓算法的偽代碼描述 下面給出圓心在原點(a，b)，半徑為r的整圓的Bresenham畫圓算法。6411iiiiixppyy(3.3.18) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 Procedure Bresenhamcircle(radius) BEGIN r為圓的半徑，圓心在點(a，b) x=0; y=r+b; p=3-2*r; WHILE xy DO BEGIN PLOT(x+a，y+b); 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 IF p0 THEN p=p+4*x+6; ELSE p=p+4*(x-

26、y)+10; y=y-1; ENDIF x=x+1; END END 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.9中利用Bresenham畫圓算法只畫出了四分之一的圓，其余的部分可用對稱關(guān)系求得。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.9 Bresenham 畫圓算法四分之一圓弧的離散表示 (a) 圓弧曲線; (b) 圓弧的離散表示 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.4 橢圓點陣圖形掃描轉(zhuǎn)換算法橢圓點陣圖形掃描轉(zhuǎn)換算法 對于一個如圖3.10所示的標(biāo)準(zhǔn)橢圓， 其方程為我們也可以用如下隱函數(shù)形式的方程表示為 F(x, y)=b2x2+

27、a2y2-a2b2=0 (3.4.2) 12222byax(3.4.1) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.4.1 橢圓弧正負(fù)算法 1. 橢圓弧正負(fù)算法思路 不同于圓，橢圓只具有四分對稱性，我們需要轉(zhuǎn)換位于第一象限的四分之一橢圓，其它部分可利用四分對稱性獲得。依據(jù)橢圓的隱式方程(3.4.2)， 可以有如下結(jié)論： 平面上一點(x, y)是否在橢圓內(nèi)、在橢圓上或在橢圓外，等價于F(x, y)大于0、等于0或小于0。假設(shè)當(dāng)前求得點Pi(xi， yi)，并定義相應(yīng)的判別函數(shù)為 pi=F(xi，yi)=b2x2i+a2y2i-a2b2 (3.4.3) 第第3 3章章 點陣圖形的基

28、本算法點陣圖形的基本算法 則依據(jù)上述結(jié)論可得以下結(jié)論： (1) 如果pi0， 則說明此時點(xi, yi)是在橢圓內(nèi)或在橢圓上，因此應(yīng)該沿水平方向向橢圓外移動得到下一點，其坐標(biāo)應(yīng)為 Pi+1=(xi+1， yi+1)=(xi+1，yi) (3.4.4) 于是Pi+1 =b2x2i+1+a2y2i+1-a2b2 =b2(xi+1)2+a2y2i-a2b2 =pi+b2(2xi+1) (3.4.5) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 (2) 如果pi0， 則說明此時點(xi, yi)是在橢圓外， 因此應(yīng)該沿垂直方向向橢圓內(nèi)移動得到下一點，其坐標(biāo)應(yīng)為 Pi+1=(xi+1，yi+

29、1)=(xi， yi-1) (3.4.6) 于是 pi+1=b2x2i+1+a2y2i+1-a2b2 =b2x2i +a2 (y i-1) 2-a2b2 =pi+a2(1-2yi) (3.4.7) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 如果橢圓方程的a和b都是整數(shù)，顯然填充的第一個像素應(yīng)該是(x1， y1)=(0， b)，所以pi的初始值為 p1=F(0， b)=0 (3.4.8) 掃描轉(zhuǎn)換算法的終止條件應(yīng)該是y=0或者x=a。2. 橢圓弧正負(fù)算法的偽代碼描述 基于上述規(guī)則，我們可以得到如下所示的橢圓掃描轉(zhuǎn)換算法:Procedure Ellipse(a，b) BEGIN x=0

30、:y=b； a0=a; a=a*a:b=b*b； 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 p1=0； PLOT(x，y)； WHILE(y0 ORxa)DO BEGIN IF p1=0 THEN p1=p1+b*(2x+1)； x=x+1; ELSE 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 p1=p1+a*(1-2y)； y=y-1；ENDIF PLOT(x，y)； END END 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.4.2 橢圓弧中點算法 1. 橢圓弧中點算法思路 如圖3-11所示，當(dāng)?shù)谝幌笙薜乃姆种粰E圓弧的x從0變到a時， 橢圓弧的變化率

31、是從0到-1，從-1到-變化的，因此我們應(yīng)該基于變化率為-1的點將第一象限的四分之一橢圓弧分成兩部分， 然后確定邊界上的像素點。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 圖3.11 橢圓弧處理示意圖 xyabO變化率1第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 第一象限內(nèi)變化率為-1的點應(yīng)滿足即有1),(),(yyxFxyxF(3.4.9) 122yaxb(3.4.9) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 結(jié)合橢圓方程，不難求得此點的x坐標(biāo)是于是結(jié)合第一象限橢圓弧曲線上x方向在增加而y方向在減小這一情況得出如下結(jié)論: （1）當(dāng)0 xxc時，第一象限橢圓

32、弧曲線上x方向的變化大于y方向的變化，令x = 1，求解y。 （2）當(dāng)xcxa時，第一象限橢圓弧曲線上y方向的變化大于x方向的變化，令y=-1，求解x。 abaabaaxc22222 (3.4.11) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 (3) 當(dāng)0 xxc時，如果當(dāng)前像素點是(xi，yi)，則下一個像素點(xi+1，yi+1)的選擇方法為: xi+1= xi+1，即x方向的改變量為1。由于y在減小，且改變量不超過x的改變量，因此取整后的y的改變量只能是0或-1，下一個要選擇的像素點只能是H(xi+1，yi)或L (xi+1，yi+1) 。H和L的具體選擇可以根據(jù)兩者之間中點

33、的函數(shù)值進(jìn)行判別。如果F(xi+1, yi-1/2)0，表明中點位于橢圓內(nèi)部，則像素點H靠近橢圓，應(yīng)該選擇像素點H； 反之則應(yīng)該選擇像素點L。 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 基于中點判別規(guī)則，我們也可以比較容易地判別xxc成立與否: 如果a2(yi-1/2)b2(xi+1)，即 成立，則xxc。下面我們分兩種情況來推導(dǎo)中點判別函數(shù)的增量公式。首先考慮0 xxc時的橢圓弧曲線。 給定當(dāng)前點(xi, yi)后，相應(yīng)的判別函數(shù)是 (3.4.12)如果pi0，則我們應(yīng)選擇的像素點是H，新的判別函數(shù)是1)2/1() 1(222iyaxb222222)21() 1()21, 1(b

34、ayaxbyxFpiiiii2222221)21()2()21, 2(bayaxbyxFpiiiii(3.4.13) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 其遞推計算公式為 pi+1=pi+b2(2xi+3) (3.4.14) 否則，有pi 0，應(yīng)選擇的是像素點L，相應(yīng)地有pi+1=pi+b2(2xi+3)+2a2(1-yi) (3.4.16) 2222221)23()2()21, 2(bayaxbyxFpiiiii(3.4.15) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 當(dāng)xcxa時，我們可以類似地得到 下面分別確定pi的初始值。如果橢圓方程的a和b都是整數(shù)，顯

35、然填充的第一個像素應(yīng)該是(x1, y1)=(0, b)，所以0 )23() 1(20 )23(22121iiiiiiiiipyaxbpppyapp(3.4.17) )41()21()21, 1 (22222221babbababbFp(3.4.18) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 如果xixc，則(xi+1，yi+1)只能從兩點(xi，yi-1)，(xi+1，yi-1)中選擇一個，并且判別時的初始值應(yīng)重新設(shè)置為 掃描轉(zhuǎn)換算法的終止條件應(yīng)該是y=0。 2. 橢圓中點算法的偽代碼描述 基于上述規(guī)則，我們可以得到如下所示的橢圓掃描轉(zhuǎn)換算法: 2222221) 1()21()

36、1,21(bayaxbyxFpiiii(3.4.19) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 Procedure Ellipse(a，b) BEGIN x=0:y=b； a=a*a:b=b*b； p1=b-a*y+a/4； PLOT(x，y)； x=x+1; WHILE(a*y-a/2b*x) DO BEGIN IF p10 THEN 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 p1=p1+2*b*x+b； ELSE y=y-1； p1=p1+2*b*x+b-2*a*y； ENDIF x=x+1； PLOT(x，y)； END p1=b*(x+1/2)*(x+1/2)

37、+a*(y-1)*(y-1)-a*b； WHILE(y0) DO 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 BEGIN y=y-1； IF p10 THEN x=x+1； p1=p1+2*b*x-2*a*y+a； ELSE p1=p1-2*y*a+a； ENDIF PLOT(x，y)； END END 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.5 多項式曲線的算法多項式曲線的算法 3.5.1 多項式函數(shù)的計算法 多項式函數(shù)f(x)=anxn+a1x+ a0可直接利用四則運算計算，也可以利用下述分解計算，以避免反復(fù)的求冪運算： f(x)=(anx+an-1)x+x+a

38、1x+a0 (3.5.1) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 3.5.2 三次多項式函數(shù)的差分計算法 1. 三階差分計算 設(shè)給定的三次多項式為 y=f(x)=a3x3+a2x2+a1x+a0 xxs, xe (3.5.2) 并令當(dāng)前給出的曲線上第i-1個像素點的坐標(biāo)值為(xi-1，yi-1)，下一個像素點的x坐標(biāo)值為xi=xi-1+x，y坐標(biāo)為 yi=a3(xi-1+x) 3+a2(xi-1+x) 2+a1(xi-1+x)+a0 (3.5.3) 注意到 yi-1=a3x3i-1+a2x2i-1+a1xi-1+a0 (3.5.4) 第第3 3章章 點陣圖形的基本算法點陣圖形的

39、基本算法 可求得一階差值 yi= yi- yi - 1= a3( 3 x2i - 1 x + 3 xi - 1 (x)2+(x)3)+a2(2xi-1x+(x)2)+a1x 為xi-1的二階多項式，比原方程降了一階。由一階差值yi可得 yi=yi+yi-1 (3.5.6) 把i-1代入式(3.5.5)可得yi-1=a3(3x2i-2x+3xi-2(x)2+(x)3)+a2(2xi-2x+(x)2)+a1x (3.5.7) (3.5.5)第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 由此可得二階差值2yi=yiyi-1=6a3(xi-2(x)2+(x)3)+2a2（x）2 (3.5.8)

40、 為xi-2的一階多項式，比原方程降了二階。由二階差值2yi可得yi=2yi+yi-1 (3.5.9) 把i-1代入式(3.5.8)可得2yi-1=6a3 (xi -3(x)2+(x)3) (3.5.10) 由此可得三階差值3yi=2yi-2yi-1=6a3(x)3 (3.5.11) 相對于x坐標(biāo)為常數(shù)值，于是有 2yi=6a3(x)3+2yi-1 (3.5.12) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 2. 差分計算法步驟 總結(jié)上述三階差分的計算可以看出，若要計算出下一個像素點(xi, yi)，需要知道前面的三個像素點(xi -1， yi-1)、(xi -2， yi-2)和(

41、xi -3，yi-3)。因此，用差分法繪制多項式曲線的計算步驟是： 第一步為初始計算，先計算必需的初始值：x0=xs, y0=f(x0) x1=x0+x, y1=f(x1), y1=y1-y0 x2=x1+x， y2=f(x2)， y2=y2-y1, 2y2=y2-y1 (3.5.13) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 和三階差分常量: 3y2=6a3(x) 3 (3.5.14) 第二步是正式的遞推計算過程: xi=xi-1+x 2y=3yi+2yi-1 yi=2yi+yi-1 yi=yi+yi-1 (3.5.15) 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法

42、3. 多項式曲線圖的質(zhì)量 多項式曲線圖應(yīng)反映多項式方程的特征，對于一些具有特殊意義的點，包括拐點和極點，都要在曲線上準(zhǔn)確地表現(xiàn)出來。這些都依賴于對曲線性質(zhì)的分析。另外，曲線的質(zhì)量不僅反映在特征表達(dá)上，還要求曲線的線條光滑、均勻及粗細(xì)適當(dāng)。在前面求解直線和圓弧曲線時我們不斷地比較兩個坐標(biāo)軸方向的增量， 始終保持增量的最大值為1。對多項式曲線而言，這需要復(fù)雜的分析比較。上述算法只是保證了像素點在x方向的均勻增加。為避免y方向增加過大帶來曲線圖形的不連續(xù)，可將用上述算法求解的相鄰像素點用直線相連。這也是繪制一般的曲線時保證連續(xù)曲線圖形仍連續(xù)的方法之一。 第第3 3章章 點陣圖形的基本算法點陣圖形的基

43、本算法 4. 多項式曲線圖差分算法的偽代碼描述 基于上述分析，我們可以得到如下所示的三次多項式曲線的差分算法掃描轉(zhuǎn)換算法: Procedure DrawPolynomial(xs，xe，deltax) BEGIN x=xs:y0=Polynomial(x)； MoveTo(x，y0)； x=x+deltax:y1=Polynomial(x)； deltay1=y1-y0； drawLineTo(x，y1)； 第第3 3章章 點陣圖形的基本算法點陣圖形的基本算法 x=x+deltax:y2=Polynomial(x)； deltay2=y2-y1； delta2y2=deltay2-deltay1； draw