2.2圓的生成算法2.2.1基礎知識

給出圓心坐標(xc,yc)r，逐點畫出一個圓周的公式有下列兩種：⒈直角坐標法

(xxc)2+(yyc)2=r2由上式導出：

當xxc從r到r作加1遞增時，就可以求出對應的圓周點的y坐標。但是這樣求出的圓周上的點是不均勻的，xxc越大，對應生成圓周點之間的圓周距離也就越長。因此，所生成的圓不美觀。12.2圓的生成算法2.2.1基礎知識(續）

⒉極坐標法

x=xc+r·cosθ，y=yc+r·sinθ

當θ從0到π作遞增時，由此式便可求出圓周上均勻分布的360個點的(x,y)坐標。利用圓周坐標的對稱性，此算法還可以簡化。將圓周分為8個象限(圖2.3)，只要將第1a象限中的圓周光柵點求出，其余7部分圓周就可以通過對稱法則計算出來。

圖2.3圓心在(0,0)點圓周生成時的對稱變換22.2圓的生成算法2.2.2圓的Bresenham算法

設圓的半徑為r。先考慮圓心在(0,0)，并從x=0、y=r開始的順時針方向的1/8圓周的生成過程。在這種情況下，x每步增加1，從x=0開始，到x=y結束。即有

xi+1=xi+1

yi+1=yi或者yi+1=yi1選擇的原則是考察精確值y是靠近yi還是靠近yi1(圖2.4)，計算式為y2=r2(xi+1)2d1=yi2y2=yi2r2+(xi+1)2d2=y2(yi1)2=r2(xi+1)2(yi1)2圖2.4y的位置

32.2圓的生成算法令pi=d1d2，并代入d1、d2，則有

pi=2(xi+1)2+yi2+(yi1)22r2(2.6)pi稱為誤差。如果pi<0則yi+1=yi，否則yi+1=yi1。pi的遞歸式為

pi+1=pi+4xi

+6+2(yi2+1yi2)2(yi+1yi)(2.7)pi的初值由式(2.6)代入xi=0，yi=r而得

p1=32r(2.8)根據上面的推導，圓周生成算法思想如下：⒈求誤差初值，p1=32r，i=1，畫點(0,r)；⒉求下一個光柵位置，其中xi+1=xi+1，如果pi<0則yi+1=yi，否則yi+1=yi1；⒊畫點(xi+1,yi+1)；⒋計算下一個誤差，如果pi<0則pi+1=pi+4xi+6，否則pi+1=pi+4(xiyi)+10；⒌i=i+1，如果x=y則結束，否則返回步驟2。42.2圓的生成算法

圓的Bresenham算法的程序實現如下：

circle(xc,yc,radius,c)intxc,yc,radius,c;{intx,y,p;x=0;y=radius;p=32*radius；

while(x<y){plot_circle_points(xc,yc,x,y,c);if(p<0)p=p+4*x+6;else{p=p+4*(xy)+10;y=1;}x+=1;}

52.2圓的生成算法if(x==y)plot_circle_points(xc,yc,x,y,c);}plot_circle_points(xc,yc,x,y,c)intxc,yc,x,y,c;{set_pixel(xc+x,yc+y,c);set_pixel(xcx,yc+y,c);set_pixel(xc+x,ycy,c);set_pixel(xcx,ycy,c);set_pixel(xc+y,yc+x,c);

set_pixel(xcy,yc+x,c);set_pixel(xc+y,ycx,c);set_pixel(xcy,ycx,c);}62.3區域填充算法2.3.1基礎知識

區域填充即給出一個區域的邊界，要求對邊界范圍內的所有像素單元賦予指定的顏色代碼。區域填充中最常用的是多邊形填色。

多邊形的表示方法頂點表示點陣表示7圖2.5掃描線與多邊形相交

圖2.6光柵化后直線變成離散點

多邊形填色一個首要的問題，是判斷一個像素是在多邊形內還是多邊形外。數學上提供的方法是“掃描交點的奇偶數判斷法”。(掃描線與邊界相交奇數次后進入該多邊形，相交偶數次后走出該多邊形。）

2.3區域填充算法2.3.1基礎知識(續）

82.3區域填充算法填色算法分為兩大類：

⒈掃描線填色(Scan-LineFilling)算法。這類算法建立在多邊形邊界的矢量形式數據之上，可用于程序填色，也可用于交互填色。⒉種子填色(SeedFilling)算法。這類算法建立在多邊形邊界的圖像形式數據之上，并還需提供多邊形邊界內一點的坐標。所以，它一般只能用于人機交互填色，而難以用于程序填色。92.3區域填充算法2.3.2掃描線填色算法

算法的基本思想：多邊形以n、x_array、y_array的形式給出，其中，x_array、y_array中存放著多邊形的n個頂點的x，y坐標。用水平掃描線從上到下掃描由點線段構成的多段定義成的多邊形。每根掃描線與多邊形各邊產生一系列交點。這些交點按照x坐標進行分類，將分類后的交點成對取出，作為兩個端點，以所需要填的色彩畫水平直線。多邊形被掃描完畢后，填色也就完成。102.3區域填充算法2.3.2掃描線填色算法(續）

需要解決或改進的問題：⒈左、右頂點處理。左頂點2：y1<y2<y3

右頂點2：y1>y2>y3其中y1、y2、y3是3個相鄰的頂點的y坐標。當掃描線與多邊形的每個頂點相交時，會同時產生2個交點。這時，填色就會因掃描交點的奇偶計數出錯而出現錯誤。圖2.7多邊形的頂點

對所有左、右頂點作如下處理：左、右頂點的入邊(以該頂點為終點的那條邊，即1–2邊)之終點刪去。對于左頂點，入邊端點(x1,y1)、(x2,y2)修改為(x1,y1)、(,y21)；對于右頂點，入邊端點(x1,y1)、(x2,y2)修改為(x1,y1)、(,y2+1)；112.3區域填充算法2.3.2掃描線填色算法(續）

⒉

水平邊處理。水平邊(y1=y2)與水平掃描線重合無法求交點。因此，將水平邊畫出后刪去，不參加求交點及求交點以后的操作。

⒊掃描線與邊的求交點方法采用遞歸算法。以(x1,y1)、(x2,y2)為端點的邊與第i+1條掃描線的交點為此式表示交點不為(x1,y1)。否則，交點為(x1,y1)。⒋

減少求交計算量，采用活性邊表。對于一根掃描線而言，與之相交的邊只占多邊形全部邊的一部分,每根掃描線與多邊形所有邊求交的操作是一種浪費，需要加以改進。122.3區域填充算法

活性邊表(ActiveListofSide)的采用將多邊形的邊分成兩個子集：與當前掃描線相交的邊的集合，以及與當前掃描線不相交的邊的集合。對后者不必進行求交運算，這樣就提高了算法的效率。圖2.8活性邊表及其指針的表示

132.3區域填充算法在上述線性表上加入兩個指針first和last，形成活性邊表。活性邊表中每個元素的內容包括以下四項：邊的maxy值；與當前掃描線相交的點的x坐標值；邊的y方向當前總長y2-y1；邊的斜率的倒數1/m。活性邊表在每根掃描線掃描之后刷新。調整first和last指針之間的參加求交運算的邊元素的值；調整first和last指針，以便使新邊進入激活范圍。活性邊表構成方法如下：將經過左、右頂點處理并剔除水平邊后的多邊形各邊按照maxy值排序，存入一個線性表中。14程序結構見課本32頁。掃描線填色算法優、缺點：優點：對于每個象素只訪問一次，輸入輸出的要求可降為最少；缺點：對于各種表的維持和排序的耗費大。掃描線（y=4）：623057.540.5

ymaxxΔy1/m掃描線（y=3）：322-25740.5

p3p4

p2p3012345678

7654321p1p2p3p4p5p4p5p2p315邊填充算法（區域掃描轉換算法）基本思想：對每條掃描線和多邊形邊的交點，將該掃描線上交點右方的所有像素取補。（對每條邊作處理的順序隨意）p1p2p3p4p5算法優、缺點：優點：簡單，適用于具有禎緩存的圖形系統；缺點：每個象素可能被訪問多次，輸入輸出的量大。16柵欄填充算法對于每條掃描線與多邊形邊的交點，將交點與柵欄之間的像素取補。柵欄線優點：減少了訪問次數172.3區域填充算法

種子填色又稱邊界填色(BoundaryFilling)。它的功能是，給出多邊形光柵化后的邊界位