『壹』 直線和圓的顯示（在線等答案）
實驗2 圓與橢圓
給出圓心坐標(xc, yc)和半徑r，逐點畫出一個圓周的公式有下列兩種。
一 直角坐標法
直角坐標系的圓的方程為
由上式導出：
當x-xc從-r到r做加1遞增時，就可以求出對應的圓周點的y坐標。但是這樣求出的圓周上的點是不均勻的，| x-xc | 越大，對應生成圓周點之間的圓周距離也就越長。因此，所生成的圓不美觀。
二 中點畫圓法
如圖1所示，函數為F(x, y)=x2+y2-R2的構造圓，圓上的點為F(x, y)=0，圓外的點F(x, y)>0，圓內的點F(x, y)<0，構造判別式：
d=F(M)=F(xp+1, yp-0.5)=(xp+1)2+(yp-0.5)2
若d＜0，則應取P1為下一像素，而且下一像素的判別式為
d=F(xp+2, yp-0.5)= (xp+2)2+(yp-0.5)2-R2=d+2xp+3
若d≥0，則應取P2為下一像素，而且下一像素的判別式為
d=F(xp+2, yp-1.5)= (xp+2)2+(yp-1.5)2-R2=d+2(xp- yp)+5
我們討論按順時針方向生成第二個八分圓，則第一個像素是（0, R），判別式d的初始值為
d0=F(1, R-0.5)=1.25-R
三 圓的Bresenham演算法
設圓的半徑為r，先考慮圓心在(0, 0)，從x=0、y=r開始的順時針方向的1/8圓周的生成過程。在這種情況下，x每步增加1，從x=0開始，到x=y結束，即有xi+1 = xi + 1；相應的，yi+1則在兩種可能中選擇：yi+1=yi或者yi+1 = yi - 1。選擇的原則是考察精確值y是靠近yi還是靠近yi-1（見圖2），計算式為
y2= r2-(xi+1)2
d1 = yi2-y2 = yi2-r2+(xi+1)2
d2 = y2- (yi - 1)2 = r2-(xi+1)2-(yi - 1)2
令pi=d1-d2，並代入d1、d2，則有
pi = 2(xi+1)2 + yi2+ (yi - 1)2 -2r2 （1.6）
pi稱為誤差。如果pi＜0，則yi+1=yi，否則yi+1=yi - 1。
pi的遞歸式為
pi+1 = pi + 4xi +6+2(yi2+1- yi2)-2(yi+1-yi) （1.7）
pi的初值由式(1.6)代入xi=0，yi=r，得
p1 = 3-2r （1.8）
根據上面的推導，圓周生成演算法思想如下：
（1）求誤差初值，p1=3-2r，i=1，畫點(0, r)。
（2）求下一個光柵位置，其中xi+1=xi+1，如果pi＜0則yi+1=yi，否則yi+1=yi - 1。
（3）畫點(xi+1, yi+1)。
（4）計算下一個誤差，如果pi＜0則pi+1=pi+4xi+6，否則pi+1=pi+4(xi - yi)+10。
（5）i=i+1，如果x=y則結束，否則返回步驟（2）。
程序設計步驟如下。
（1）創建應用程序框架，以上面建立的單文檔程序框架為基礎。
（2）編輯菜單資源。
在工作區的ResourceView標簽中，單擊Menu項左邊"+"，然後雙擊其子項IDR_MAINFRAME，並根據表1中的定義添加編輯菜單資源。此時建好的菜單如圖3所示。
表1 菜單資源表
菜單標題 菜單項標題 標示符ID
圓 中點畫圓 ID_MIDPOINTCIRCLE
Bresenham畫圓 ID_BRESENHAMCIRCLE
（3）添加消息處理函數。
利用ClassWizard（建立類向導）為應用程序添加與菜單項相關的消息處理函數，ClassName欄中選擇CMyView，根據表2建立如下的消息映射函數，ClassWizard會自動完成有關的函數聲明。
表2 菜單項的消息處理函數
菜單項ID 消 息 消息處理函數
ID_MIDPOINTCIRCLE CONMMAN OnMidpointcircle
ID_BRESENHAMCIRCLE CONMMAN OnBresenhamcircle
（4）程序結構代碼，在CMyView.cpp文件中的相應位置添加如下代碼。
void CMyView::OnMidpointcircle() //中點演算法繪制圓，如圖4所示
{
// TODO: Add your command handler code here
CDC* pDC=GetDC();
int xc=300, yc=300, r=50, c=0;
int x,y;
float d;
x=0; y=r; d=1.25-r;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
while(x<=y)
{ if(d<0) d+=2*x+3;
else { d+=2*(x-y)+5; y--;}
x++;
pDC->SetPixel ((xc+x),(yc+y),c);
pDC->SetPixel ((xc-x),(yc+y),c);
pDC->SetPixel ((xc+x),(yc-y),c);
pDC->SetPixel ((xc-x),(yc-y),c);
pDC->SetPixel ((xc+y),(yc+x),c);
pDC->SetPixel ((xc-y),(yc+x),c);
pDC->SetPixel ((xc+y),(yc-x),c);
pDC->SetPixel ((xc-y),(yc-x),c);
}
}
void CMyView::OnBresenhamcircle() //// Bresenham演算法繪制圓，如圖5所示
{
CDC* pDC=GetDC();
int xc=100, yc=100, radius=50, c=0;
int x=0,y=radius,p=3-2*radius;
while(x<y)
{
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
if (p<0)
p=p+4*x+6;
else
{
p=p+4*(x-y)+10;
y-=1;
}
x+=1;
}
if(x==y)
pDC->SetPixel(xc+x, yc+y, c);
pDC->SetPixel(xc-x, yc+y, c);
pDC->SetPixel(xc+x, yc-y, c);
pDC->SetPixel(xc-x, yc-y, c);
pDC->SetPixel(xc+y, yc+x, c);
pDC->SetPixel(xc-y, yc+x, c);
pDC->SetPixel(xc+y, yc-x, c);
pDC->SetPixel(xc-y, yc-x, c);
}
四 橢圓掃描轉換中點演算法
下面討論橢圓的掃描轉換中點演算法，設橢圓為中心在坐標原點的標准橢圓，其方 程為
F(x, y)=b2x2+a2y2-a2b2=0
（1）對於橢圓上的點，有F(x, y)=0；
（2）對於橢圓外的點，F(x, y)>0；
（3）對於橢圓內的點，F(x, y)<0。
以弧上斜率為-1的點作為分界將第一象限橢圓弧分為上下兩部分（如圖6所示）。
法向量：
而在下一個點，不等號改變方向，則說明橢圓弧從上部分轉入下部分。
與中點繪制圓演算法類似，一個像素確定後，在下面兩個候選像素點的中點計算一個判別式的值，再根據判別式符號確定離橢圓最近的點。先看橢圓弧的上半部分，具體演算法如下：
假設橫坐標為xp的像素中與橢圓最近點為（xp, yp），下一對候選像素的中點應為（xp+1，yp-0.5），判別式為
，表明中點在橢圓內，應取正右方像素點，判別式變為
若 ，表明中點在橢圓外，應取右下方像素點，判別式變為
判別式 的初始條件確定。橢圓弧起點為(0, b)，第一個中點為(1,b - 0.5)，對應判別式為
在掃描轉換橢圓的上半部分時，在每步迭代中需要比較法向量的兩個分量來確定核實從上部分轉到下半部分。在下半部分演算法有些不同，要從正上方和右下方兩個像素中選擇下一個像素。在從上半部分轉到下半部分時，還需要對下半部分的中點判別式進行初始化。即若上半部分所選擇的最後一個像素點為(xp, yp)，則下半部分中點判別式應在（xp+0.5, yp-1）的點上計算。其在正下方與右下方的增量計算同上半部分。具體演算法的實現請參考下面的程序設計。
程序設計步驟如下。
（1）創建應用程序框架，以上面建立的單文檔程序框架為基礎。
（2）編輯菜單資源。
在工作區的ResourceView標簽中，單擊Menu項左邊"+"，然後雙擊其子項IDR_MAINFRAME，並根據表3中的定義添加編輯菜單資源。此時建好的菜單如圖7所示。
表3 菜單資源表
菜單標題 菜單項標題 標示符ID
橢圓 中點畫橢圓 ID_MIDPOINTELLISPE
圖7 程序主菜單
（3）添加消息處理函數。
利用ClassWizard（建立類向導）為應用程序添加與菜單項相關的消息處理函數，ClassName欄中選擇CMyView，根據表4建立如下的消息映射函數，ClassWizard會自動完成有關的函數聲明。
表4 菜單項的消息處理函數
菜單項ID 消 息 消息處理函數
ID_MIDPOINTELLISPE CONMMAN OnMidpointellispe
（4）程序結構代碼如下：
void CMyView:: OnMidpointellispe () //中點演算法繪制橢圓，如圖8所示
{
CDC* pDC=GetDC();
int a=200,b=100,xc=300,yc=200,c=0;
int x,y;
double d1,d2;
x=0;y=b;
d1=b*b+a*a*(-b+0.25);
pDC->SetPixel(x+300,y+200,c);
pDC->SetPixel(-x+300,y+200,c);
pDC->SetPixel(x+300,-y+200,c);
pDC->SetPixel(-x+300,-y+200,c);
while(b*b*(x+1)<a*a*(y-0.5))
{
if(d1<0){
d1+=b*b*(2*x+3);
x++;}
else
{d1+=b*b*(2*x+3)+a*a*(-2*y+2);
x++;y--;
}
pDC->SetPixel(x+xc,y+yc,c);
pDC->SetPixel(-x+xc,y+yc,c);
pDC->SetPixel(x+xc,-y+yc,c);
pDC->SetPixel(-x+xc,-y+yc,c);
}
d2=sqrt(b*(x+0.5))+a*(y-1)-a*b;
while(y>0)
{
if(d2<0){
d2+=b*b*(2*x+2)+a*a*(-2*y+3);
x++;y--;}
else
{d2+=a*a*(-2*y+3);
y--;}
pDC->SetPixel(x+xc,y+yc,c);
pDC->SetPixel(-x+xc,y+yc,c);
pDC->SetPixel(x+xc,-y+yc,c);
pDC->SetPixel(-x+xc,-y+yc,c);
}
}
實驗一: 直 線
數學上，理想的直線是由無數個點構成的集合，沒有寬度。計算機繪制直線是在顯示器所給定的有限個像素組成的矩陣中，確定最佳逼近該直線的一組像素，並且按掃描線順序，對這些像素進行寫操作，實現顯示器繪制直線，即通常所說的直線的掃描轉換，或稱直線光柵化。
由於一圖形中可能包含成千上萬條直線，所以要求繪制直線的演算法應盡可能地快。本節介紹一個像素寬直線的常用演算法：數值微分法（DDA）、中點畫線法、Bresenham 演算法。
一. DDA（數值微分）演算法
DDA演算法原理：如圖1-1所示，已知過端點 的直線段 ；直線斜率為 ，從 的左端點 開始，向 右端點步進畫線，步長=1（個像素），計算相應的 坐標 ；取像素點 [ , round（y）] 作為當前點的坐標。計算 ，當 ，即當x每遞增1，y遞增k（即直線斜率）。
注意：上述分析的演算法僅適用於k1的情形。在這種情況下，x每增加1, y最多增加1。當 時，必須把x，y地位互換，y每增加1，x相應增加1/k（請參閱後面的Visual C++程序）。
二. 生成直線的中點畫線法
中點畫線法的基本原理如圖1-2所示。在畫直線段的過程中，當前像素點為P，下一個像素點有兩種選擇，點P1或P2。M為P1與P2中點，Q為理想直線與X=Xp+1垂線的交點。當M在Q的下方時，則P2應為下一個像素點；當M在Q的上方時，應取P1為下一點。
中點畫線法的實現：令直線段為L[ p0(x0,y0), p1(x1, y1)]，其方程式F(x, y)=ax+by+c=0。
其中，a=y0–y1, b=x1–x0, c=x0y1–x1y0；點與L的關系如下。
在直線上，F(x, y)=0；
在直線上方，F(x, y)>0；
在直線下方，F(x, y)<0。
把M代入F（x, y），判斷F的符號，可知Q點在中點M的上方還是下方。為此構造判別式d=F(M)=F(xp+1, yp+0.5)=a(xp+1)+b(yp+0.5)+c。
當d < 0，L(Q點)在M上方，取P2為下一個像素。
當d > 0，L(Q點)在M下方，取P1為下一個像素。
當d=0，選P1或P2均可，取P1為下一個像素。
其中d是xp, yp的線性函數。
三. Bresenham演算法
Bresenham演算法是計算機圖形學領域使用最廣泛的直線掃描轉換演算法。由誤差項符號決定下一個像素取右邊點還是右上方點。
設直線從起點(x1, y1)到終點(x2, y2)。直線可表示為方程y = mx+b，其中b=y1–mx1， m = (y2–y1)/(x2–x1)=dy/dx；此處的討論直線方向限於第一象限，如圖1-3所示，當直線光柵化時，x每次都增加1個單元，設x像素為(xi，yi)。下一個像素的列坐標為xi+1，行坐標為yi或者遞增1為yi+1，由y與yi及yi+1的距離d1及d2的大小而定。計算公式為
y = m(xi + 1) + b （1.1）
d1 = y – yi （1.2）
d2=yi+1–y （1.3）
如果d1–d2>0，則yi+1=yi+1，否則yi+1=yi。
式（1.1）、（1.2）、（1.3）代入d1–d2，再用dx乘等式兩邊，並以Pi=(d1–d2)，dx代入上述等式，得
Pi = 2xidy–2yidx+2dy+(2b–1)dx （1.4）
d1–d2是用以判斷符號的誤差。由於在第一象限，dx總大於0，所以Pi仍舊可以用做判斷符號的誤差。Pi+1為
Pi+1 = Pi+2dy–2(yi+1–yi)dx （1.5）
求誤差的初值P1，可將x1、y1和b代入式（1.4）中的xi、yi，而得到
P1 = 2dy–dx
綜述上面的推導，第一象限內的直線Bresenham演算法思想如下：
（1）畫點（x1, y1），dx=x2–x1，dy=y2–y1，計算誤差初值P1=2dy–dx，i=1。
（2）求直線的下一點位置xi+1 = xi + 1，如果Pi>0，則yi+1=yi+1，否則yi+1=yi。
（3）畫點(xi+1, yi+1)。
（4）求下一個誤差Pi+1，如果Pi>0，則Pi+1=Pi+2dy–2dx，否則Pi+1=Pi+2dy。
（5）i=i+1；如果i<dx+1則轉步驟（2）；否則結束操作。
四. 程序設計
1 程序設計功能說明
為編程實現上述演算法，本程序利用最基本的繪制元素（如點、直線等），繪制圖形。如圖1-4所示，為程序運行主界面，通過選擇菜單及下拉菜單的各功能項分別完成各種對應演算法的圖形繪制。
圖1-4 基本圖形生成的程序運行界面
2 創建工程名稱為「基本圖形的生成」單文檔應用程序框架
（1）啟動VC，選擇「文件」|「新建」菜單命令，並在彈出的新建對話框中單擊「工程」標簽。
（2）選擇MFC AppWizard(exe)，在「工程名稱」編輯框中輸入 「基本圖形的生成」作為工程名稱，單擊「確定」按鈕，出現Step 1對話框。
（3）選擇「單個文檔」選項，單擊「下一個」按鈕，出現Step 2對話框。
（4）接受默認選項，單擊「下一個」按鈕，在出現的Step 3～Step 5對話框中，接受默認選項，單擊「下一個」按鈕。
（5）在Step 6對話框中單擊「完成」按鈕，即完成「基本圖形的生成」應用程序的所有選項，隨後出現工程信息對話框（記錄以上步驟各選項選擇情況），如圖1-5所示，單擊「確定」按鈕，完成應用程序框架的創建。
圖1-5 信息程序基本
3 編輯菜單資源
設計如圖1-4所示的菜單項。在工作區的ResourceView標簽中，單擊Menu項左邊「+」，然後雙擊其子項IDR_MAINFRAME，並根據表1-1中的定義編輯菜單資源。此時VC已自動建好程序框架，如圖1-5所示。
表1-1 菜單資源表
菜單標題 菜單項標題 標示符ID
直線 DDA演算法生成直線 ID_DDALINE
Bresenham演算法生成直線 ID_BRESENHAMLINE
中點演算法生成直線 ID_MIDPOINTLINE
4 添加消息處理函數
利用ClassWizard（建立類向導）為應用程序添加與菜單項相關的消息處理函數，ClassName欄中選擇CMyView，根據表1-2建立如下的消息映射函數，ClassWizard會自動完成有關的函數聲明。
表1-2 菜單項的消息處理函數
菜單項ID 消 息 消息處理函數
ID_DDALINE CONMMAN OnDdaline
ID_MIDPOINTLINE CONMMAN OnMidpointline
ID_BRESENHAMLINE CONMMAN OnBresenhamline
5 程序結構代碼，在CMyView.cpp文件中相應位置添加如下代碼：
// DDA演算法生成直線
void CMyView:: OnDdaline()
{
CDC* pDC=GetDC();//獲得設備指針
int xa=100,ya=300,xb=300,yb=200,c=RGB(255,0,0);//定義直線的兩端點，直線顏色
int x,y;
float dx, dy, k;
dx=(float)(xb-xa), dy=(float)(yb-ya);
k=dy/dx, y=ya;
if(abs(k)<1)
{
for (x=xa;x<=xb;x++)
{pDC->SetPixel (x,int(y+0.5),c);
y=y+k;}
}
if(abs(k)>=1)
{
for (y=ya;y<=yb;y++)
{pDC->SetPixel (int(x+0.5),y,c);
x=x+1/k;}
}
ReleaseDC(pDC);
}
說明：
（1）以上代碼理論上通過定義直線的兩端點，可得到任意端點之間的一直線，但由於一般屏幕坐標採用右手系坐標，屏幕上只有正的x, y值，屏幕坐標與窗口坐標之間轉換知識請參考第3章。
（2）注意上述程序考慮到當k1的情形x每增加1，y最多增加1；當k>1時，y每增加1，x相應增加1/k。在這個演算法中，y與k用浮點數表示，而且每一步都要對y進行四捨五入後取整。
//中點演算法生成直線
void CMyView::OnMidpointline()
{
CDC* pDC=GetDC();
int xa=300, ya=200, xb=450, yb=300,c=RGB(0,255,0);
int a, b, d1, d2, d, x, y;
a=ya-yb, b=xb-xa, d=2*a+b;
d1=2*a, d2=2* (a+b);
x=xa, y=ya;
pDC->SetPixel(x, y, c);
while (x<xb)
{ if (d<0) {x++, y++, d+=d2; }
else {x++, d+=d1;}
pDC->SetPixel(x, y, c);
}
ReleaseDC(pDC);
}
說明：
（1）其中d是xp, yp的線性函數。為了提高運算效率，程序中採用增量計算。具體演算法如下：若當前像素處於d>0情況，則取正右方像素P1(xp+1, yp)，判斷下一個像素點的位置，應計算d1=F(xp+2, yp+0.5)=a(xp+2)+b(yp+0.5)=d+a；，其中增量為a。若d<0時，則取右上方像素P2（xp+1, yp+1）。再判斷下一像素，則要計算d2 = F(xp+2, yp+1.5)=a(xp+2)+b(yp+1.5) + c=d+a+b，增量為a+b。
（2） 畫線從(x0, y0)開始，d的初值d0=F(x0+1, y0+0.5)=F(x0, y0)+a+0.5b，因F(x0, y0)=0，則d0=a+0.5b。
（3）程序中只利用d的符號，d的增量都是整數，只是初始值包含小數，用2d代替d，使程序中僅包含整數的運算。
//Bresenham演算法生成直線
void CMyView::OnBresenhamline()
{
CDC* pDC=GetDC();
int x1=100, y1=200, x2=350, y2=100,c=RGB(0,0,255);
int i,s1,s2,interchange;
float x,y,deltax,deltay,f,temp;
x=x1;
y=y1;
deltax=abs(x2-x1);
deltay=abs(y2-y1);
if(x2-x1>=0) s1=1; else s1=-1;
if(y2-y1>=0) s2=1; else s2=-1;
if(deltay>deltax){
temp=deltax;
deltax=deltay;
deltay=temp;
interchange=1;
}
else interchange=0;
f=2*deltay-deltax;
pDC->SetPixel(x,y,c);
for(i=1;i<=deltax;i++){
if(f>=0){
if(interchange==1) x+=s1;
else y+=s2;
pDC->SetPixel(x,y,c);
f=f-2*deltax;
}
else{
if(interchange==1) y+=s2;
else x+=s1;
f=f+2*deltay;
}
}
}
說明：
（1）以上程序已經考慮到所有象限直線的生成。
（2）Bresenham演算法的優點如下：
① 不必計算直線的斜率，因此不做除法。
② 不用浮點數，只用整數。
③ 只做整數加減運算和乘2運算，而乘2運算可以用移位操作實現。
④ Bresenham演算法的運算速度很快。
『貳』 計算機圖形學中直線的生成演算法
/DDA （Digital Differential Analyzer)法 即 數值微分法 /
想法思路：
對於具有斜率|k|<1的線段，可以讓x從起點到終點計算，x方向每增加（或減少）1像素，即令x=x+1（或x=x-1），則y方向增加(或減少）k像素，即y=y+k（或y=y-1)
代碼
//起點（x1,y1） , 終點（ x2,y2） ,像素顏色color
void DDAline(int x1 ,int y1,int x2,int y2,int color)
{
int x;
float k,y=y1;
k=1.0 * (y2-y1)/(x2-x1);／／斜率k
for( x=x1;x<=x2;x++)
{
putpixel( x, , color);／／對floory四捨五入取整(int)(y+0.5)
y=y+k;
}
}
『叄』 求計算機圖形學中的直線繪制函數法、DDA演算法、中點法和Bresenham演算法的優缺點以及比較.
Bresenham演算法的特點是:
1,不必計巧毀首算直線之斜率,因此不做除法;
2,不用浮點數,只用整數;
3,只做整數加孝數減法和乘2運算,而乘2運算可以用硬體移位實現.
Bresenham演算法速度很快,並適余悄於用硬體實現.
DDA演算法的特點:
浮點數運算
不易硬體實現
中點畫線法特點:
只有整數運算,不含乘除法
可用硬體實現
因(X0,Y0)在直線上,所以F(X0,Y0)=0
『肆』 dda法生成直線的基本原理是什麼為什麼說Bersenham畫圓的演算法效率較高
DDA演算法主要是根據直線公式y = kx + b來推導出來的，其關鍵之處在於如何設定單位步進，即一個方向的步進為單位步進，另一個方向的步進必然是小於1。演算法的具體思路如下：
1. 輸入直線的起點、終點；
2. 計算x方向的間距：△X和y方向的間距：△Y。
3. 確定單位步進，取MaxSteps = max（△X，△Y）; 若△X>=△Y，則X方向的步進為單位步進，X方向步進一個單位，Y方向步進△Y/MaxSteps;否則相反。
4. 設置第一個點的像素值
5. 令循環初始值為1，循環次數為MaxSteps，定義變數x,y，執行以下計算：
a. x增加一個單位步進，y增加一個單位步進
b. 設置位置為（x,y）的像素值
Bresenham演算法是DDA演算法畫線演算法的一種改進演算法。本質上它也是採取了步進的思想。不過它比DDA演算法作了優化，避免了步進時浮點數運算，同時為選取符合直線方程的點提供了一個好思路。首先通過直線的斜率確定了在x方向進行單位步進還是y方向進行單位步進：當斜率k的絕對值|k|<1時，在x方向進行單位步進；當斜率k的絕對值|k|>1時，在y方向進行單位步進。
1. 輸入線段的起點和終點。
2. 判斷線段的斜率是否存在（即起點和終點的x坐標是否相同），若相同，即斜率不存在，
只需計算y方向的單位步進（△Y+1次），x方向的坐標保持不變即可繪制直線。
3. 計算線段的斜率k，分為下面幾種情況處理
a. k等於0，即線段平行於x軸，即程序只需計算x方向的單位步進，y方向的值不變
b. |k|等於1，即線段的x方向的單位步進和y方向的單位步進一樣，皆為1。直接循環△X次計算x和y坐標。
4. 根據輸入的起點和終點的x、y坐標值的大小決定x方向和y方向的單位步進是1還是-1
6. 畫出第一個點。
7. 若|k| <1，設m =0,計算P0，如果Pm>0，下一個要繪制的點為（Xm+單位步進，Ym），
Pm+1 = Pm -2*△Y;
否則要繪制的點為（Xm+單位步進，Ym+單位步進）
Pm+1 = Pm+2*△X-2*△Y；
8. 重復執行第七步△X-1次；
9. 若|k| <1，設m =0,計算Q0，如果Qm>0，下一個要繪制的點為（Xm，Ym+單位步進），
Pm+1 = Pm -2*△X;
否則要繪制的點為（Xm+單位步進，Ym+單位步進）
Pm+1 = Pm+2*△Y-2*△X；
10. 重復執行第9步△Y-1次；
『伍』 分別解釋直線生成演算法DDA法、中點畫線法和Bresenham法的基本原理
DDA稱為數值微分畫線演算法，是直線生成演算法中最簡單的一種。原理相當簡單，就是最直觀的根據斜率的偏移程度，決定是以x為步進方向還是以y為步進方向。然後在相應的步進方向上，步進變數每次增加一個像素，而另一個相關坐標變數則為Yk_1=Yk+m（以x為步進變數為例，m為斜率）
假定直線斜率k在0~1之間，當前象素點為（xp,yp），則下一個象素點有兩種可選擇點P1（xp+1,yp）或P2（xp+1,yp+1）。若P1與P2的中點（xp+1,yp+0.5）稱為M，Q為理想直線與x=xp+1垂線的交點。當M在Q的下方時，則取P2應為下一個象素點；當M在Q的上方時，則取P1為下一個象素點。這就是中點畫線法的基本原理
Bresenham：過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近的像素。該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。
大概就是這樣，預知詳細，可以參考圖形學的書籍