32圓的生成算法-課件

3.2圓的掃描轉(zhuǎn)換

3.2.1算法原理3.2.2構(gòu)造中點偏差判別式3.3橢圓的掃描轉(zhuǎn)換

圓的掃描轉(zhuǎn)換算法下面僅以圓心在原點、半徑R為整數(shù)的圓為例，討論圓的生成算法。假設(shè)圓的方程為：

X2+Y2=R23.2.1中點Bresenham算法原理算法原理：此時最大位移方向為x，每次x方向上走一步，而y方向上或減1，或減0。假定當(dāng)前與圓弧最近者已確定，為P(Xp,Yp)，下一候選點只能是P1(xP+1,yP)，或P2(xP+1,yP－1)，到底選哪一個依舊用中點判斷。MP1P2P(Xp,Yp)構(gòu)造函數(shù)：F（X，Y）=X2+Y2-R2；則

F（X，Y）=0（X，Y）在圓上；

F（X，Y）<0（X，Y）在圓內(nèi)；

F（X，Y）>0（X，Y）在圓外。設(shè)M為P1、P2間的中點，M=(Xp+1,Yp-0.5)3.2.1中點Bresenham算法原理MP1P2P(Xp,Yp)有如下結(jié)論：

F（M）<0->M在圓內(nèi)->取P1F（M）>=0->M在圓外->取P2為此，可采用如下判別式：

3.2.1中點Bresenham算法原理MP1P2P(Xp,Yp)

d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若d<0,則P1為下一個象素，而且再下一個象素的判別式為：

d1=F(xp+2,yp-0.5)=(xp+2)2+(yp-0.5)2-R2

=d+2xp+3即d的增量為2xp+3.3.2.2構(gòu)造中點偏差判別式MP1P2P(Xp,Yp)若d>=0,則P2為下一個象素，那么再下一個象素的判別式為：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2

=d+（2xp+3）+（-2yp+2）即d的增量為2(xp-yp)+5.d的初值:圓的起點為P0(0,R),則第一個中點是(1,R-0.5)d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R3.2.2構(gòu)造中點偏差判別式MP1P2P(Xp,Yp)算法步驟

(1)輸入圓的半徑R。

(2)計算初始值d=1.25－R、x=0、y=R。

(3)繪制點(x,y)及其在八分圓中的另外七個對稱點。

(4)判斷d的符號。若d<0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x－y)+5，再將(x,y)更新為(x+1,y－1)。

(5)當(dāng)x<y時，重復(fù)步驟3和4。否則結(jié)束。3.2.2構(gòu)造中點偏差判別式

MidpointCircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(x<y){if(d<0){d+=2*x+3;x++}else{d+=2*(x-y)+5;x++;y--;}drawpixel(x,y,color);}}3.2.2構(gòu)造中點偏差判別式XY01234567899876543210例子：用bresenham畫圓算法生成X

2+Y2-64

=0第1象限的1/4圓弧。本節(jié)主要講解順時針繪制1/4橢圓的中點Bresenham算法原理。

F（x，y）>0F（x，y）=0F（x，y）<0理想橢圓橢圓的掃描轉(zhuǎn)換3.3橢圓的掃描轉(zhuǎn)換3.3.1橢圓的特征對于橢圓上的點，有F(x,y)=0；對于橢圓外的點，F(xiàn)(x,y)>0；對于橢圓內(nèi)的點，F(xiàn)(x,y)<0。解決問題：

分界點：法向量兩分量相等的點以弧上斜率為－1的點法向量y分量>x分量y分量<x分量y分量=x分量橢圓方程AC橢圓弧段，法矢量的x向分量小于y向分量，斜率k處處滿足|k|＜1，|△x|＞|△y|，所以x方向為主位移方向；在C點，法矢量的x向分量等于y向分量，斜率k滿足k＝－1，|△x|＝|△y|；CB橢圓弧段，法矢量x向分量大于y向分量，斜率k處處滿足|k|＞1，|△y|＞|△x|，所以y方向為主位移方向。A（0，b）B（a，0）y向分量法矢量

x向分量C(,)圖3-11橢圓的法矢量

橢圓的中點Bresenham算法的原理：在部分Ⅰ：每次在主位移x方向上走一步，y方向上退不退步取決于中點偏差判別式的值；在部分Ⅱ：每次在主位移方向y上退一步，x方向上走不走步取決于中點偏差判別式的值。圖3-12橢圓中點Bresenham算法原理A（0，b）B（a，0）ⅠⅡPuPdPlPr

先考慮圖3-12所示部分Ⅰ的AC段橢圓弧。此時中Bresenham畫橢圓算法要從A（0，b）到（,)順時針確定順時針確定最佳逼近于該段橢圓弧的像素點集。由于x方向為主位移方向，假定當(dāng)前點是P（xi，yi），下一步只能在正右方的像素Pu（xi＋1，yi）和右下方的像素Pd（xi＋1，yi－1）中選取。

再考慮圖3-12所示部分CB段橢圓弧。此時中Bresenham畫橢圓算法要從C（,)到B（a，0）順時針確定最佳逼近于該段橢圓弧像素點集。由于y方向為主位移方向，假定當(dāng)前點是P（xi，yi），下一步只能在正下方像素Pl（xi，yi－1）和右下方的像素Pr（xi＋1，yi－1）中選取。3.3.2構(gòu)造上半部分Ⅰ中點偏差判別式在上半部分Ⅰ，x方向每次加1，y方向上減不減1取決于中點偏差判別式的值。從P（xi，yi）走第一步，為了選取下一像素點的，需將Pu（xi＋1，y

i）和Pd（xi＋1，yi－1）的中點M（xi＋1，yi－0.5）代入隱函數(shù)，構(gòu)造中點偏差判別式：

當(dāng)d1<0時，中點M在橢圓內(nèi)，下一像素點應(yīng)點亮Pu，即y方向不退步；當(dāng)d>0時，中點M在橢圓外，下一像素點應(yīng)點亮Pd，即y方向退一步；當(dāng)d＝0時，中點M在橢圓上，Pu、Pd和橢圓的距離相等，點亮Pu或Pd均可，約定取Pd，如圖3-13所示。P（xi，yi）Pu（xi＋1，yi）M（xi+1，yi-0.5）Pd（xi＋1，yi－1）圖3-13上半部分像素點的選取

因此，（3-17）

d1<0⑴當(dāng)d1<0時，下一步的中點坐標(biāo)為：M（xi＋2，yi-0.5）。所以下一步中點偏差判別式為：P（xi，yi)M（xi＋1，yi－0.5）M（xi＋2，yi－0.5）上半部分Ⅰ的遞推公式⑵當(dāng)d1≥0時，下一步的中點坐標(biāo)為：M（xi＋2，yi－1.5）。所以下一步中點偏差判別式為：P（xi，yi）M（xi＋1，yi－0.5）M（xi＋2，yi－1.5）d1≥0

2.中點偏差判別式d1的初值

上半部分橢圓的起點為A（0，b），因此，第一個中點是（1，b－0.5），對應(yīng)的d1的初值為：

（3-20）

yxP（xi，yi）Pr（xi＋1，yi－1）圖3-15下半部分像素點的選取3.3.4構(gòu)造Ⅱ中點偏差判別式構(gòu)造中點偏差判別式：

Pl（xi，yi－1）

當(dāng)d2<0時，中點M在橢圓內(nèi)，下一像素點應(yīng)點亮Pr，即x方向上走一步；當(dāng)d2>0時，中點M在橢圓外，下一像素點應(yīng)點亮Pl，即x方向上不走步；當(dāng)d2＝0時，中點M在橢圓上，Pl、Pr和橢圓的距離相等，點亮Pl或Pr均可，約定取Pl，如圖3-15所示。因此，（3-22）

3.3.5下半部分Ⅱ的遞推公式P（xi，yi）M（xi＋0.5，yi－1）M（xi＋1.5，yi－2）d2<0

⑴當(dāng)d2<0時，下一步的中點坐標(biāo)為：M（xi＋1.5，yi－2）。所以下一步中點偏差判別式為：⑵當(dāng)d2≥0時，下一步的中點坐標(biāo)為：M（xi＋0.5，yi－2）。所以下一步中點偏差判別式為：（3-24）

P（xi，yi）M（xi＋0.5，yi－1）M（xi＋0.5，yi－2）d2≥0

y向分量為：則對于上半部分橢圓上一點任意P（xi，yi）如果在其當(dāng)前中點M（xi＋1，yi－0.5）處，滿足x向分量小于y向分量：2.中點偏差判別式d2的初值在上半部分Ⅰ，法矢量的x向分量小于y向分量；在C點，法矢量的x向分量等于y向分量；在下半部分Ⅱ，法矢量的x向分量大于y向分量。x向分量為：

（3-25）

P（xi，yi）Pu（xi＋1，yi）Pl（xi，yi－1）MⅠ（xi＋1，yi－0.5）Pd（xi＋1，yi－1）=Pr（xi＋1，yi－1）圖3-17下半部分的初值假定圖3-17中P（xi，yi）點是橢圓上半部分Ⅰ的最后一個像素，MⅠ（xi＋1，yi－0.5）是用于判斷點亮Pu和Pd像素的中點。

由于下一像素轉(zhuǎn)入了下半部分Ⅱ，所以其中點改為判斷Pl和Pr的中點MⅡ（xi＋0.5，yi－1），所以下半部分的初值d20為：算法步驟：1.輸入橢圓的長半軸a和短半軸b。2.計算初始值d=b2+a2(-b+0.25)、x=0、y=b。3.繪制點(x,y)及其在四分象限上的另外三個對稱點。4.判斷d的符號。若d≤0，則先將d更新為d+b2(2x+3)，再將(x,y)更新為(x+1,y)；否則先將d更新為d+b2(2x+3)+a2(-2y+2)，再將(x,y)更新為(x+1,y-1)。5.當(dāng)b2(x+1)<a2(y-0.5)時，重復(fù)步驟3和4。否則轉(zhuǎn)到步驟6。6.用上半部分計算的最后點(x,y)來計算下半部分中d的初值：7.繪制點(x,y)及其在四分象限上的另外三個對稱點。8.判斷d的符號。若d≤0，則先將d更新為b2(2xi+2)+a2(-2yi+3)，再將(x,y)更新為(x+1,y-1)；否則先將d更新為d+a2(-2yi+3)，再將(x,y)