p03直線、圓、橢圓的生成ppt課件

1、第三章第三章 直線、圓、橢圓生成算法直線、圓、橢圓生成算法圖形的掃描轉換光柵化確定一個像素集合，用于圖形的掃描轉換光柵化確定一個像素集合，用于顯示一個圖形的過程。顯示一個圖形的過程。步驟如下：步驟如下：1、確定有關像素、確定有關像素2、用圖形的顏色或其它屬性，對像素進行寫操作。、用圖形的顏色或其它屬性，對像素進行寫操作。對一維圖形，不考慮線寬，則用一個像素寬的直線來對一維圖形，不考慮線寬，則用一個像素寬的直線來顯示圖形。二維圖形的光柵化，即區(qū)域的填充：確定顯示圖形。二維圖形的光柵化，即區(qū)域的填充：確定像素集，填色或圖案。像素集，填色或圖案。任何圖形的光柵化，必須顯示在一個窗口內，否則不任何圖形

2、的光柵化，必須顯示在一個窗口內，否則不予顯示。即確定一個圖形的哪些部分在窗口內，哪些予顯示。即確定一個圖形的哪些部分在窗口內，哪些在窗口外，即裁剪。在窗口外，即裁剪。圖形顯示前需要：掃描轉換+裁剪裁剪-掃描轉換：最常用，節(jié)約計算時間。掃描轉換-裁剪：算法簡單；本章內容本章內容3.1掃描轉換直線段掃描轉換直線段 3.1.1 DDA算法算法 3.1.2中點畫線法中點畫線法 3.1.3Bresenham畫線算法畫線算法3.2圓弧、橢圓弧掃描轉換圓弧、橢圓弧掃描轉換 3.2.1 中點算法中點算法 3.2.2內接正多邊形迫近法內接正多邊形迫近法 3.2.3等面積正多邊形逼近法等面積正多邊形逼近法 3.2

3、.4生成圓弧的正負法生成圓弧的正負法 3.1直線段的掃描轉換算法直線段的掃描轉換算法n直線的掃描轉換直線的掃描轉換: 確定最佳逼近于該直線確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這的一組象素，并且按掃描線順序，對這些象素進行寫操作。些象素進行寫操作。n三個常用算法：三個常用算法：n數(shù)值微分法數(shù)值微分法DDA）n中點畫線法中點畫線法nBresenham算法。算法。3.1.1數(shù)值微分法）數(shù)值微分法） 假定直線的起點、終點分別為：（x0,y0), (x1,y1)，且都為整數(shù)。(X i+1 ,Yi + k)(X i , Int(Yi +0.5)(X i , Yi)柵格交點表示象素點位置。3

4、.1.1數(shù)值微分數(shù)值微分(DDA)法法n基本思想基本思想n已知過端點已知過端點P0 (x0, y0), P1(x1, y1)的直線段的直線段Ln y=kx+bn直線斜率為直線斜率為n這種方法直觀，但效率太低，因為每一步需要一次這種方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次舍入運算。浮點乘法和一次舍入運算。 0101xxyyk)(,;10yroundxbkxystepxxxxxx令計算yi+1= kxi+1+b = kxi+b+kx = yi+kx 當x =1;yi+1 = yi+k 即：當x每遞增1，y遞增k(即直線斜率)；注意上述分析的算法僅適用于k 1的情形。在這種情況下，x每

5、增加1,y最多增加1。當 k 1時，必須把x，y地位互換n增量算法：在一個迭代算法中，如果每增量算法：在一個迭代算法中，如果每一步的一步的x、y值是用前一步的值加上一個值是用前一步的值加上一個增量來獲得，則稱為增量算法。增量來獲得，則稱為增量算法。nDDA算法就是一個增量算法。算法就是一個增量算法。數(shù)值微分數(shù)值微分(DDA)法法void DDALine(int x0,int y0,int x1,int y1,int color) int x；float dx, dy, y, k;dx, = x1-x0, dy=y1-y0; k=dy/dx, y=y0; for (x=x0; xx1, x+)

6、drawpixel (x, int(y+0.5), color); y=y+k; 數(shù)值微分(DDA)法n例：畫直線段P0(0,0)-P1(5,2)nx int(y+0.5) y+0.5n000+0.5n100.4+0.5n210.8+0.5n311.2+0.5n421.6+0.5n522.0+0.50 1 2 3 4 5321Line: P0(0, 0)- P1(5, 2)實現(xiàn)實現(xiàn)DDA畫線程序畫線程序n步驟：步驟：n第一步：建立一個第一步：建立一個DDALine的工程文件；的工程文件；n第二步：添加第二步：添加ddaline()成員函數(shù)成員函數(shù)n方法：在工作區(qū)中選擇方法：在工作區(qū)中選擇CLA

7、SSVIEW類窗口，類窗口，右擊右擊CDDAlineView類，選擇類，選擇“add member function”，定義如下的成員函數(shù)：，定義如下的成員函數(shù)：n void ddaline(CDC* pDC,int x0,int y0,int x1,int y1,COLORREF color);第三步：編寫自定義的成員函數(shù)第三步：編寫自定義的成員函數(shù)ddaline()程序程序void CDDALineView:ddaline(CDC* pDC, int x0, int y0, int x1, int y1, COLORREF color) int length,i; float x,y,dx

8、,dy; length=abs(x1-x0); if (abs(y1-y0)length) length=abs(y1-y0); dx=(float)(x1-x0)/length; dy=(float)(y1-y0)/length; x=x0+0.5;y=y0+0.5; for (i=1;iSetPixel(int)x,(int)y,color); x=x+dx;y=y+dy; 第四步：編寫第四步：編寫OnDraw()函數(shù)函數(shù)void CDDALineView:OnDraw(CDC* pDC)CDDALineDoc* pDoc = GetDocument();ASSERT_VALID(pDoc

9、);/ TODO: add draw code for native data here ddaline(pDC,100,100,400,100,RGB(255,0,0); ddaline(pDC,400,100,400,400,RGB(0,255,0); ddaline(pDC,400,400,100,400,RGB(0,0,255); ddaline(pDC,100,400,100,100,RGB(255,255,0); ddaline(pDC,100,100,400,400,RGB(255,0,255); ddaline(pDC,100,400,400,100,RGB(0,255,255

10、);數(shù)值微分(DDA)法n缺陷： 在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實現(xiàn)。中點畫線法n原理：假定直線斜率0K P2離直線更近更近-取P2 。nM在Q的上方- P1離直線更近更近-取P1nM與Q重合， P1、P2任取一點。n問題：如何判斷M與Q點的關系？P=(xp,yp)QP2P13.1.2中點畫線法中點畫線法假設直線方程為：ax+by+c=0其中a=y0-y1, b=x1-x0, c=x0y1-x1y0由常識知：欲判斷中點M點是在Q點上方還是在Q點下方，只需把M代入F(x,y),并檢查它的符號。點在直線下方點在直線上方點在直線上面0,0,0,yxFy

11、xFyxFP=(xp,yp)QP2P1構造判別式：d=F(M)=F(xp+1,yp+0.5) =a(xp+1)+b(yp+0.5)+c當d0，M在直線(Q點)上方，取右方P1；當d=0，選P1或P2均可，約定取P1；能否采用增量算法呢？P=(xp,yp)QP2P1若d0 -M在直線上方-取P1;此時再下一個象素的判別式為 d1=F(xp+2, yp+0.5) =a(xp+2)+b(yp+0.5)+c = a(xp +1)+b(yp +0.5)+c +a =d+a； 增量為aP=(xp,yp)QP2P1n若dM在直線下方-取P2;n此時再下一個象素的判別式為n d2= F(xp+2, yp+1.

12、5)n =a(xp+2)+b(yp+1.5)+cn = a(xp +1)+b(yp +0.5)+c +a +b =d+a+b ； 增量為abP=(xp,yp)QP2P1n畫線從(x0, y0)開場，d的初值nd0=F(x0+1, y0+0.5)= a(x0 +1)+b(y0 +0.5)+cn = F(x0, y0)+a+0.5b = a+0.5b n由于只用d 的符號作判斷，為了只包含整數(shù)運算, n可以用2d代替d來擺脫小數(shù)，提高效率。void Midpoint Line (int x0,int y0,int x1, int y1,int color) int a, b, d1, d2, d,

13、 x, y; a=y0-y1, b=x1-x0, d=2*a+b; d1=2*a, d2=2* (a+b); x=x0, y=y0; drawpixel(x, y, color); while (xx1) if (d0) x+; y+; d+=d2; else x+; d+=d1; drawpixel (x, y, color); /* while */ /* mid PointLine */n例：用中點畫線法P0(0,0) P1(5,2)na=y0-y1=-2 b=x1-x0=5nd0=2a+b=1 d1=2a=-4 d2=2(a+b)=6nixiyidn1 001n2 10-3n3 213

14、n4 31-1n5 4250 1 2 3 4 5321中點畫線算法nMidpointLine(CDC *pDC, int x0, int y0, int x1, int y1, COLORREF color)nint a,b,delta1,delta2,d,x,y;n/傳入的端點坐標x值相等nif(x0=x1)nif(y0y1)nnfor(int i=y0;iSetPixel(x0,i,color);nnelse nfor(int i=y1;iSetPixel(x0,i,color);nnreturn;nn/斜率判斷，斜率絕對值大于1，則m為false，否則為truenbool m=(fabs

15、(y1-y0)=fabs(x1-x0);n/如果傳入的坐標值x1x1)nd=x0;x0=x1;x1=d;nd=y0;y0=y1;y1=d;na=y0-y1;nb=x1-x0;nx=x0;y=y0;npDC-SetPixel(x,y,color);n/斜率絕對值小于等于1的情況nif(m)n/第一種情況，y值遞增nif(y0=y1)nd=2*a+b;ndelta1=2*a;delta2=2*(a+b);nwhile(xx1)nif (dSetPixel(x,y,color);nnn/第三種情況，y值遞減nelse nd=2*a-b;ndelta1=2*a;delta2=2*(a-b);nwhil

16、e(xx1)nif (dSetPixel(x,y,color);nnnn/斜率絕對值大于1nelsen/第二種情況，y值遞增nif(y0=y1)nd=a+2*b;ndelta1=2*b;delta2=2*(a+b);nwhile(yy1)nif (dSetPixel(x,y,color);nnn/第四種情況，y值遞減nelsend=a-2*b;ndelta1=-2*b;delta2=2*(a-b);nwhile(yy1)nif (dSetPixel(x,y,color);nnnnBresenham畫線算法 在直線生成的算法中Bresenham算法是最有效的算法之一。令 k=y/x，就0k1的情

17、況來說明Bresenham算法。由DDA算法可知：yi+1=yi+k (1) 由于k不一定是整數(shù)，由此式求出的yi也不一定是整數(shù)，因此要用坐標為xi,yir的象素來表示直線上的點，其中yir表示最靠近yi的整數(shù)。Bresenham畫線算法 設圖中xi列上已用xi,yir作為表示直線的點，又設B點是直線上的點，其坐標為xi+1,yi+1），顯然下一個表示直線的點（ xi+1,yi+1,r只能從圖中的C或者D點中去選。設A為CD邊的中點。 若B在A點上面則應取D點作為（ xi+1,yi+1,r），否則應取C點。(x)的幾何意義為能確定B在A點上面或下面，令(xi+1)=yi+1-yir-0.5 (

18、2) 若B在A的下面，則有(xi+1)0。由圖可知 yi+1,r=yir+1，若(xi+1)0 (3) yi+1,r=yir， 若(xi+1)0Bresenham畫線算法由式2和式3可得到 (xi+2)=yi+2 - yi+1,r - 0.5 =yi+1 + k - yi+1,r - 0.5 （4） yi+1 - yir -0.5 + k - 1,當(xi+1)0 yi+1 - yir -0.5 + k, 當(xi+1)0 (xi+2)= (xi+1) + k -1 ,當(xi+1)0 (xi+2)= (xi+1) + k , 當(xi+1)0 由式1和式2可得到 (x2)= k - 0.5

19、(5)Bresenham畫線算法nBresenhamLine(CDC *pDC, int x1, int y1, int x2, int y2, COLORREF color)nnint x,y,dx,dy,p;n/傳入端點坐標x值相等nif (x1 = x2)nnif (y1 y2)nnfor (int i=y1;iSetPixel(x1,i,color);nnelsennfor (int i=y2;iSetPixel(x1,i,color);nnreturn;nnn/斜率判斷，斜率絕對值大于，則m為false，否則為truenBOOL m = (fabs(y2-y1) x2)nnp=x1;

20、x1=x2;x2=p;np=y1;y1=y2;y2=p;nnx = x1;ny = y1;ndx = x2 - x1;ndy = y2 - y1;nn/斜率絕對值小于等于nif (m)nn/第一種情況，y遞增nif (y1 = y2)nnp = (dy1) - dx;nwhile (x SetPixel(x,y,color);nif (p 0)nx+;p=p+(dy1);nelsenx+;y+;p=p+(dy-dx)1);nnn/第三種情況，y遞減nelsennp = dx - (dy1);nwhile (x SetPixel(x,y,color);nif (p 0)nx+;p=p-(dy1)

21、;nelsenx+;y-;p=p-(dy+dx)1);nnnn/斜率絕對值大于nelsenn/第二種情況，y遞增nif (y1 = y2)nnp = (dx1) - dy;nwhile (y SetPixel(x,y,color);nif (p 0)ny+;p=p+(dx1);nelsenx+;y+;p=p+(dx-dy)1);nnn/第四種情況，y遞減nelsennp = (dx= y2)nnpDC-SetPixel(x,y,color);nif (p 0)ny-;p=p+(dx1);nelsenx+;y-;p=p+(dx+dy)SetPixel(x0+x,y0+y,c); pDC-SetP

22、ixel(x0-x,y0+y,c); pDC-SetPixel(x0+x,y0-y,c); pDC-SetPixel(x0-x,y0-y,c); pDC-SetPixel(x0+y,y0+x,c); pDC-SetPixel(x0-y,y0+x,c); pDC-SetPixel(x0+y,y0-x,c); pDC-SetPixel(x0-y,y0-x,c); 對于圓心在對于圓心在x0,y0)、半徑為、半徑為r的圓，先對圓心在原點，半徑的圓，先對圓心在原點，半徑為為r的的8分圓進行掃描轉換，每確定一個象素，可輸出原始圓的分圓進行掃描轉換，每確定一個象素，可輸出原始圓的8個個點。點。3.2.4中點

23、畫圓法中點畫圓法利用圓的對稱性，只須討論1/8圓。第二個8分圓P為當前點亮象素，那么，下一個點亮的象素可能是P1Xp+1，Yp或P2Xp +1，Yp -1)。MP1P2PXp ，Yp ）構造函數(shù)：FX，Y）=X2 + Y2 - R2 ；那么 FX，Y）= 0 （X，Y在圓上； FX，Y） 0 （X，Y在圓外。設M為P1、P2間的中點，M=(Xp+1,Yp-0.5)MP1P2有如下結論： FM）M在圓內- 取P1 FM）= 0 -M在圓外- 取P2為此，可采用如下判別式： MP1P2 d = F(M) = F(xp + 1, yp - 0.5) =(xp + 1)2 + (yp - 0.5) 2

24、 - R2 若d=0, 則P2 為下一個象素，那么再下一個象素的判別式為： d1 = F(xp + 2, yp - 1.5) = (xp + 2)2 + (yp - 1.5) 2 - R2 = d + （2xp + 3）+（-2 yp + 2） 即d 的增量為 2 (xp - yp) +5. d的初值: d0 = F(1, R-0.5) = 1 + (R-0.5)2 - R2 = 1.25 - RMP1P2算法步驟：算法步驟：1.輸入圓的半徑輸入圓的半徑R。2.計算初始值計算初始值d=1.25-R、x=0、y=R。3.繪制點繪制點(x,y)及其在八分圓中的另外七個對稱點。及其在八分圓中的另外七

25、個對稱點。4.判斷判斷d的符號。若的符號。若d0，則先將，則先將d更新為更新為d+2x+3，再將再將(x,y)更新為更新為(x+1,y)；否則先將；否則先將d更新為更新為d+2(x-y)+5，再將，再將(x,y)更新為更新為(x+1,y-1)。5.當當x=y時，重復步驟時，重復步驟3和和4。否則結束。否則結束。 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1.25-r; drawpixel(x,y,color); while(xy) if(d0) d+ = 2*x+3; x+; elsed+ = 2*(x-y)

26、+ 5; x+;y-; drawpixel(x,y,color); n為了進一步提高算法的效率，可以將上面的算法中的浮點數(shù)改寫成整數(shù)，將乘法運算改成加法運算，即僅用整數(shù)實現(xiàn)中點畫圓法。n使用e=d-0.25代替dne0=1-R算法優(yōu)化算法優(yōu)化算法步驟：算法步驟：1.輸入圓的半徑輸入圓的半徑R。2.計算初始值計算初始值d=1-R、x=0、y=R。3.繪制點繪制點(x,y)及其在八分圓中的另外七個對稱點。及其在八分圓中的另外七個對稱點。4.判斷判斷d的符號。若的符號。若d0， 則 先 將， 則 先 將 d更 新 為更 新 為d+2x+3，再將，再將(x,y)更新為更新為(x+1,y)；否則先；否則

27、先將將d更新為更新為d+2(x-y)+5，再將，再將(x,y)更新為更新為(x+1,y-1)。5.當當x=y時，重復步驟時，重復步驟3和和4。否則結束。否則結束。中點畫圓法程序代碼中點畫圓法程序代碼 MidpointCircle(int r, int color) int x,y; float d; x=0; y=r; d=1-r; drawpixel(x,y,color); while(x=y) if(d0) d+ = 2*x+3; x+ elsed+ = 2*(x-y) + 5; x+;y-; drawpixel(x,y,color); 上述算法能否再改進呢？上述算法能否再改進呢？注意到注

28、意到d的增量是的增量是x,y的線性函數(shù)，的線性函數(shù)，每當每當x遞增遞增1，則，則d的增量遞增的增量遞增x=2每當每當y遞減遞減1，則，則d的增量遞增的增量遞增y=2x初始值初始值=3；y初始值初始值=-2r+2x=0; y=r; d=1-r; .if(d0) d+ = 2*x+3; x+ ;elsed+ = 2*(x-y) + 5; x+;y-; x=0;y=r;d=1-r;d1=3;d2=-2*r+2; .if(d0) d+ = d1; x+;d1+=2 ;elsed+ = d1+d2; x+;y-; d1+=2;d2+=2 MidpointCircle(int r, int color)

29、int x,y; int d; x=0; y=r; d=1-r;d1=3;d2=-2*r+2; while(xy) drawpixel(x,y,color); if(d0) d+ = d1; x+;d1+=2 else d+ = d1+d2; x+;y-; d1+=2;d2+=2; 程序實現(xiàn)步驟：n(1)建立MidPointCircle工程文件；n(2)右擊CMidPointCircleView類，建立成員n 函數(shù)n void MidpointCircle(CDC *pDC,int x0, int y0, int r, COLORREF color)n int CirPot(CDC *pDC,

30、int x0, int y0, int x, int y, COLORREF color) (3) 編寫成員函數(shù)代碼，程序如下：nvoid CMidPointCircleView:MidpointCircle(CDC *pDC,int x0, int y0, int r, COLORREF color)nn int x,y;n float d;n x=0;y=r;d=1.25-r;n CirPot(pDC,x0,y0,x,y,color);nwhile (x=y)nn if(dSetPixel(x0+x),(y0+y),color); pDC-SetPixel(x0+y),(y0+x),col

31、or); pDC-SetPixel(x0+y),(y0-x),color); pDC-SetPixel(x0+x),(y0-y),color); pDC-SetPixel(x0-x),(y0-y),color); pDC-SetPixel(x0-y),(y0-x),color); pDC-SetPixel(x0-y),(y0+x),color); pDC-SetPixel(x0-x),(y0+y),color);return 0;（4編寫OnDraw(CDC* pDC)函數(shù)，程序如下：void CMidPointCircleView:OnDraw(CDC* pDC)CMidPointCircl

32、eDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);/ TODO: add draw code for native data hereMidpointCircle(pDC,100, 100, 10, RGB(255,0,0); MidpointCircle(pDC,500, 300, 60, RGB(255,255,0);(5)編譯、運行程序，查看結果。3.2.5 Bresenham3.2.5 Bresenham畫圓算法畫圓算法 現(xiàn)在從A點開始向右下方逐點來尋找弧AB要用的點。如圖中點Pi-1是已選中的一個表示圓弧上的點，根據(jù)弧AB的走向，下一個點應該

33、從Hi或者Li中選擇。顯然應選離AB最近的點作為顯示弧AB的點。 假設圓的半徑為R，顯然，當xhi2 + yhi2 -R2 R2 - (xli2 + yli2)時，應該取Li。否則取Hi。令di = xhi2 + yhi2 + xli2 + yli2 - 2R2 顯然，當di 0 時應該取Li。 否則，取Hi。Pi-1HiLi應取Hi還是取Li剩下的問題是如何快速的計算剩下的問題是如何快速的計算didi。設圖中設圖中Pi-1Pi-1的坐標為的坐標為(xi-1,yi-1)(xi-1,yi-1)，則，則HiHi和和LiLi的坐標為的坐標為(xi,yi-1)(xi,yi-1)和和(xi,yi-1-1

34、 )(xi,yi-1-1 )di = xi2 + yi-12 + xi2 + (yi-1-1)2 di = xi2 + yi-12 + xi2 + (yi-1-1)2 - 2R2- 2R2=2xi2 + 2yi-12 - 2yi-1 - 2R2 =2xi2 + 2yi-12 - 2yi-1 - 2R2 di+1 = (xi + 1)2 + yi2 + (xi + 1)2 di+1 = (xi + 1)2 + yi2 + (xi + 1)2 + (yi - 1)2 - 2R2+ (yi - 1)2 - 2R2=2xi2 + 4xi + 2yi2 - 2yi - 2R2 + 3=2xi2 + 4x

35、i + 2yi2 - 2yi - 2R2 + 3Pi-1HiLi應取Hi還是取LiBresenham畫圓算法當di取Hi - yi=yi-1，那么 di+1 = di + 4xi-1 + 7當di 0時-取Li - yi=yi-1-1，那么 di+1 = di + 4(xi-1-yi-1) + 11 易知 x0=0，y0=R,x1=x0+1 因此 d0=12 + y02 + 12 +(y0 - 1)2 - 2R2 = 3 - 2y0 = 3 - 2RPi-1HiLi應取Hi還是取LiBresenhamBresenham畫圓算法代碼畫圓算法代碼void CircleBres(int radius

36、) int x=0,y=radius,p=3-2*radius; while (xy) Drawpixel(x,y,c) ; x+; if (p F(xi,yi) 向右- 向圓外Pi在圓外時- F(xi,yi)0 - 向下- 向圓內即求得Pi點后選擇下一個象素點Pi+1的規(guī)則為：當F(xi,yi) 0 取xi+1 = xi+1，yi+1 = yi;當F(xi,yi) 0 取xi+1 = xi， yi+1 = yi - 1;這樣用于表示圓弧的點均在圓弧附近，且使F(xi,yi) 時正時負，故稱正負法?？焖儆嬎愕年P鍵是F(xi,yi) 的計算，能否采用增量算法？n若F(xi,yi) 知，計算F(x

37、i+1,yi+1) 可分兩種情況：n1、F(xi,yi)0- xi+1 = xi+1，yi+1 = yi;n - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2n - = (xi+1)2+ yi2 -R2 = F(xi,yi) +2xi +1n2、 F(xi,yi)0- xi+1 = xi，yi+1 = yi -1;n - F(xi+1,yi+1)= (xi+1 )2 +(yi+1 )2 -R2n - = xi2+(yi 1)2-R2 = F(xi,yi) - 2yi +1n3、初始值：圓弧起點(0,R),圓弧終點(R，0)3.2.7生成圓弧的多邊形逼近法n 圓的內接

38、正多邊形迫近法n 圓的等面積正多邊形迫近法圓的內接正多邊形逼近法n思想：當一個正多邊形的邊數(shù)足夠多時，該多邊形可以和圓無限接近。即n因此，在允許的誤差范圍內，可以用正多邊形代替圓。n設內接正n邊形的頂點為Pi(xi,yi), Pi的幅角為i ,每一條邊對應的圓心角為a，則有nxi =Rcos i nyi =Rsin i圓邊正內接多邊形）nn(lim圓的內接正多邊形逼近法 內接正內接正n邊形代替圓邊形代替圓計算多邊形各頂點的遞推公式計算多邊形各頂點的遞推公式 Xi+1 Rcos( a+ i) = Yi +1 Rsin (a+ i)Xi+1 cos a- sin a Xi = Yi +1 sin

39、a cosa Yi由于由于: a是常數(shù)，是常數(shù)， sin a， cosa只在開始時計算只在開始時計算一次所以，一個頂點只需一次所以，一個頂點只需4次乘法，共次乘法，共4n次乘次乘法，外加直線段的中點算法的計算量。法，外加直線段的中點算法的計算量。圓的等面積正多邊形逼近法n當用內接正多邊形逼近圓時，其面積要小于圓的面積；而當用圓的外切正多邊形逼近圓時，其面積則要大于圓的面積。為了使近似代替圓的正多邊形和圓之間在面積上相等，只有使該正多邊形和圓弧相交，稱之為圓的等面積正多邊形。圓的等面積正多邊形逼近法步驟：求多邊形徑長，從而求所有頂點坐標值由逼近誤差值，確定邊所對應的圓心角3.3 橢圓的掃描轉換橢圓的掃描轉換3.3.1 橢圓的特征橢圓的特征baxy圖5-14 長半軸為a，短半軸為b的標準橢圓(x,y)(x,-y)(-x,-y)(-x,y)0),(222222bayaxbyxF 對于橢圓上的點，有F(x,y)=0； 對于橢圓外的點，F(xiàn)(x,y)0； 對于橢圓內的點，F(xiàn)(x,y)0，取Pd(xi+1,yi-1)p(xi,yi)pu(xi+1,yi)pd(xi+1,yi-1)M(xi+1,yi-0