dda演算法圓

A. 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次；

B. DDA演算法的演算法描述

DDA演算法的C語言描述如下。當 時，實現代碼： voidDDALine(intx0,inty0,intx1,inty1,intcolor){intx;floatdx,dy,y,k;dx=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;x<=x1;x++){Drawpixel(x,int(y+0.5),color);y=y+k;}}當 時，實現代碼： voidDDALine(intx0,inty0,intx1,inty1,intcolor){inty;floatdx,dy,x,k;dx=x1-x0,dy=y1-y0;k=dx/dy,x=x0;for(y=y0;y<=y1;y++){Drawpixel(int(x+0.5),y,color);x=x+k;}}任意斜率代碼實現如下：（注意自己補上，此處n做分母可能為0） voidDDALine(intx0,inty0,intx1,inty1,intcolor){intdx,dy,n,k;floatxinc,yinc,x,y;dx=x1-x0;dy=y1-y0;if(abs(dx)>abs(dy))n=abs(dx);elsen=abs(dy);xinc=(float)dx/n;yinc=(float)dy/n;x=(float)x0;y=(float)y0;for(k=1;k<=n;k++){Drawpixel(int(x+0.5),int(y+0.5),color);x+=xinc;y+=yinc;}}

C. 怎麼使用DDA演算法完成程序

#include <graphics.h>
#include <math.h>
#define ROUND(a) ((int)(a+0.5))

#define OX 320
#define OY 240

void lineDDA (int xa, int ya, int xb, int yb, int color);
void setpixel (int x, int y, int color);

main(){

int gdrive=DETECT, gmode=0;

initgraph(&gdrive, &gmode, "d:\\tc");
setbkcolor(BLACK);
line (0, OY, 2*OX, OY);
line (OX, 0, OX, 2*OY);

lineDDA (100, 10, 0, 0, RED);
getch ();
closegraph();

return 0;
}

/*
* DDA, digital differential analyzer, algoritm to calculating pixel position.
* Donald Hearn & M. Pauline Baker, Computer Graphics: C Version,
* Second Edition, 清華大學出版社, 2004, p88
*/
void lineDDA (int xa, int ya, int xb, int yb, int color) {
int dx = xb - xa;
int dy = yb - ya;
int steps, i;
float xIncrement, yIncrement;
float x=xa;
float y=ya;

if(abs(dx) > abs(dy))
steps = abs(dx);
else
steps = abs(dy);
/*
* y=kx+b, if k>0, x+1 and y+k; if k<0, y+1 and x+1/k.
*/
xIncrement = dx/(float)steps;
yIncrement = dy/(float)steps;

putpixel (ROUND(x), ROUND(y), color);
for (i=0; i<steps; i++) {
x += xIncrement;
y += yIncrement;
setpixel (ROUND(x), ROUND(y), color);
}
return;
}

void setpixel (int x, int y, int color) {
/* printf ("(%d,%d)", x, y);
*/ putpixel (OX+x, OY-y, color);
return;
}

D. 如何簡單理解DDA演算法

DDA稱為數值微分畫線演算法。
是直線生成演算法中最簡單的一種.原理相當簡單,就是最直觀的根據斜率的偏移程度,決定是以x為步進方向還是以y為步進方向.然後在相應的步進方向上,步進變數每次增加一個像素,而另一個相關坐標變數則為Yk_1=Yk+m（以x為步進變數為例,m為斜率）。

E. 畫圓的常見演算法

畫圓的基本演算法有逐點比較和DDA積分法，
代碼示例 WinC下運行

#include "Conio.h"
#include "graphics.h"
#include "process.h"
#define Ni_circle 0
#define Shun_circle 1
#define closegr closegraph

void initgr();
void draw_Base_circle();
void draw_cabu_circle();
void close_graph();
void acrroods();
static float x0,y0;

void initgr(void) /* BGI初始化 */
{
int gd = DETECT, gm = 0; /* 和gd = VGA,gm = VGAHI是同樣效果 */
registerbgidriver(EGAVGA_driver);/* 注冊BGI驅動後可以不需要.BGI文件的支持運行 */
initgraph(&gd, &gm, "");
}

void acrroods() /*屏幕中心坐標 */
{
x0=getmaxx()/2;
y0=getmaxy()/2;
}

void draw_Base_circle() /*畫圓及寫參數*/
{
line(x0-200,y0,x0+200,y0); outtextxy(x0+220,y0,"Z");
line(x0,y0-180,x0,y0+180); outtextxy(x0+10,y0+180,"X");
outtextxy(x0-10,y0+10,"O");
circle(x0,y0,150);
textcolor(YELLOW);
directvideo=0;
gotoxy(46,2);cprintf("Circle start:X0 Y0 Z150");
gotoxy(46,3);cprintf("Circle end :X0 Y0 Z150");
gotoxy(46,4);cprintf("Units :Pixel");
gotoxy(46,5);cprintf("Circle now:");
}

void close_graph() /*關圖形系統*/
{
closegraph();
}

void draw_cabu_circle(int sstep,int Directory)/*關鍵的圓插補函數*/
{
int flag=0;
float Fm,Xm,Ym;
Xm=x0+150; Ym=y0;
moveto(Xm,Ym);
setcolor(RED);
while(1) /*分象限，順圓和逆圓討論*/
{
Fm=(Xm-x0)/(Xm-x0)+(Ym-y0)/(Ym-y0)-150/150;/*圓判斷公式*/
if(Fm>=0){
if(!Directory){ /*逆圓判斷*/
if(Xm>=x0&&Ym<=y0)
{
if(flag) break; /*if語句判斷象限，以下一樣*/
else Xm=Xm-sstep;
}
if(Xm<=x0&&Ym<=y0)
{
flag=1; Ym=Ym+sstep;
}
if(Xm<=x0&&Ym>=y0)
Xm=Xm+sstep;
if(Xm>=x0&&Ym>=y0)
Ym=Ym-sstep;
}
else { /*it is Directory's else*/
if(Xm>x0&&Ym<y0)
Ym=Ym+sstep;
if(Xm<=x0&&Ym<=y0)
Xm=Xm+sstep;
if(Xm<x0&&Ym>y0) {
flag=1; Ym=Ym-sstep;}
if(Xm>=x0&&Ym>=y0) {
if(flag) break;
Xm=Xm-sstep;}
}
}
else{ /*it is Fm's else*/
if(!Directory) {
if(Xm>x0&&Ym<y0)
{
if(flag) break;
else Ym=Ym-sstep;
}
if(Xm<=x0&&Ym<=y0)
{
flag=1; Xm=Xm-sstep;
}
if(Xm<=x0&&Ym>=y0)
Ym=Ym+sstep;
if(Xm>=x0&&Ym>=y0)
Xm=Xm+sstep;
}
else{
if(Xm>x0&&Ym<y0)
Xm=Xm+sstep;
if(Xm<=x0&&Ym<=y0)
Ym=Ym-sstep;
if(Xm<=x0&&Ym>=y0){
flag=1; Xm=Xm-sstep;}
if(Xm>=x0&&Ym>=y0) {
if(flag) break;
else Ym=Ym+sstep;}
}
}
lineto(Xm,Ym);
gotoxy(58,5); printf("X%3.0f Y0 Z%3.0f ",Ym-y0,Xm-x0);
delay(800);
}
}

void circle_demo(int Directory) /*控制圓插補兩次*/
{
int i=0,sstep;
initgr(); /* BGI初始化 */
sleep(2);
acrroods(&x0,&y0);
for(i=0;i<2;i++)
{
draw_Base_circle(150);
if(i==0){
sstep=6;
draw_cabu_circle(sstep,Directory);}
else{
sstep=1;
draw_cabu_circle(sstep,Directory);}
getch();
cleardevice();
setcolor(WHITE);
}
}

/* 圓插補部分的函數區結束*/

int main(void)
{
int choice=0;
initgr(); /* BGI初始化 */

while(choice!=4)
{
setfillstyle(1,RED);
bar(200,30,400,80);
setcolor(GREEN);
settextstyle(3,0,10);
outtextxy(220,50,"DEMO PROGRAM BY P.Y.F");
setcolor(WHITE);
settextstyle(0,0,1);
outtextxy(200,140,"2. Shun_Circle demo.");
outtextxy(200,160,"3. Ni_Circle demo.");
outtextxy(200,180,"4. Quit the program.");
outtextxy(160,200,"Please enter your choice:"); gotoxy(46,13);
scanf("%d",&choice);

switch(choice)
{
case 2: circle_demo(Ni_circle);break;
case 3: circle_demo(Shun_circle);break;
case 4: break;
default: printf("\nChoice wrong,try again!");
}
}

getch(); /* 暫停一下，看看前面繪圖代碼的運行結果 */
closegr(); /* 恢復TEXT屏幕模式 */
return 0;
}

具體看看《計算機圖形學》。

F. 為什麼用dda演算法生成圓周或橢圓不需要用到三角運算，所以運算效率高

一個自耕農家庭里，牛頓誕生了。牛頓是一個早產兒，出生時只有三磅重，接生婆和他的親人都擔心他能否活下來。誰也沒有料到這個看起來微不足道的小東西會成為了一位震古爍今的科學巨人，並且竟活到了85歲的高齡。

牛頓出生前三個月父親便去世了。在他兩歲時，母親改嫁給一個牧師，把牛頓留在外祖母身邊撫養。11歲時，母親的後夫去世，母親帶著和後夫所生的一子二女回到牛頓身邊。牛頓自幼沉默寡言，性格倔強，這種習性可能來自它的家庭處境。

大約從五歲開始，牛頓被送到公立學校讀書。少年時的牛頓並不是神童，他資質平常，成績一般，但他喜歡讀書，喜歡看一些介紹各種簡單機械模型製作方法的讀物，並從中受到啟發，自己動手製作些奇奇怪怪的小玩意，如風車、木鍾、折疊式提燈等等。

傳說小牛頓把風車的機械原理摸透後，自己製造了一架磨坊的模型，他將老鼠綁在一架有輪子的踏車上，然後在輪子的前面放上一粒玉米，剛好那地方是老鼠可望不可及的位置。老鼠想吃玉米，就不斷的跑動，於是輪子不停的轉動；又一次他放風箏時，在繩子上懸掛著小燈，夜間村人看去驚疑是彗星出現；他還製造了一個小水鍾。每天早晨，小水鍾會自動滴水到他的臉上，催他起床。他還喜歡繪畫、雕刻，尤其喜歡刻日晷，家裡牆角、窗檯上到處安放著他刻畫的日晷，用以驗看日影的移動。

牛頓12歲時進了離家不遠的格蘭瑟姆中學。牛頓的母親原希望他成為一個農民，但牛頓本人卻無意於此，而酷愛讀書。隨著年歲的增大，牛頓越發愛好讀書，喜歡沉思，做科學小實驗。他在格蘭瑟姆中學讀書時，曾經寄宿在一位劑師家裡，使他受到了化學試驗的熏陶。

牛頓在中學時代學習成績並不出眾，只是愛好讀書，對自然現象由好奇心，例如顏色、日影四季的移動，尤其是幾何學、哥白尼的日心說等等。他還分門別類的記讀書筆記，又喜歡別出心裁的作些小工具、小技巧、小發明、小試驗。

當時英國社會滲透基督教新思想，牛頓家裡有兩位都以神父為職業的親戚，這可能影響牛頓晚年的宗教生活。從這些平凡的環境和活動中，還看不出幼年的牛頓是個才能出眾異於常人的兒童。

後來迫於生活，母親讓牛頓停學在家務農，贍養家庭。但牛頓一有機會便埋首書卷，以至經常忘了幹活。每次，母親叫他同傭人一道上市場，熟悉做交易的生意經時，他便懇求傭人一個人上街，自己則躲在樹叢後看書。有一次，牛頓的舅父起了疑心，就跟蹤牛頓上市鎮去，發現他的外甥伸著腿，躺在草地上，正在聚精會神地鑽研一個數學問題。牛頓的好學精神感動了舅父，於是舅父勸服了母親讓牛頓復學，並鼓勵牛頓上大學讀書。牛頓又重新回到了學校，如飢似渴地汲取著書本上的營養。有一次，他去郊外遊玩，之後靠在一棵蘋果樹下休息，忽然，一個蘋果從樹上掉下來。他覺得很奇怪，為什麼蘋果會從上往下掉而不是從下往上掉？他帶著這個疑問回到了家裡研究，後來他發現原來地球是有引力的能把物體吸住。隨後，就出現了《牛頓物理引力學》。

求學歲月

1661年，19歲的牛頓以減費生的身份進入劍橋大學三一學院，靠為學院做雜務的收入支付學費，1664年成為獎學金獲得者，1665年獲學士學位。

17世紀中葉，劍橋大學的教育制度還滲透著濃厚的中世紀經院哲學的氣味，當牛頓進入劍橋時，哪裡還在傳授一些經院式課程，如邏輯、古文、語法、古代史、神學等等。兩年後三一學院出現了新氣象，盧卡斯創設了一個獨辟蹊徑的講座，規定講授自然科學知識，如地理、物理、天文和數學課程。

講座的第一任教授伊薩克·巴羅是個博學的科學家。這位學者獨具慧眼，看出了牛頓具有深邃的觀察力、敏銳的理解力。於是將自己的數學知識，包括計算曲線圖形面積的方法，全部傳授給牛頓，並把牛頓引向了近代自然科學的研究領域。

在這段學習過程中，牛頓掌握了算術、三角，讀了開普勒的《光學》，笛卡爾的《幾何學》和《哲學原理》，伽利略的《兩大世界體系的對話》，胡克的《顯微圖集》，還有皇家學會的歷史和早期的哲學學報等。

牛頓在巴羅門下的這段時間，是他學習的關鍵時期。巴羅比牛頓大12歲，精於數學和光學，他對牛頓的才華極為贊賞，認為牛頓的數學才超過自己。後來，牛頓在回憶時說道：「巴羅博士當時講授關於運動學的課程，也許正是這些課程促使我去研究這方面的問題。」

當時，牛頓在數學上很大程度是依靠自學。他學習了歐幾里得的《幾何原本》、笛卡兒的《幾何學》、沃利斯的《無窮算術》、巴羅的《數學講義》及韋達等許多數學家的著作。其中，對牛頓具有決定性影響的要數笛卡兒的《幾何學》和沃利斯的《無窮算術》，它們將牛頓迅速引導到當時數學最前沿～解析幾何與微積分。1664年，牛頓被選為巴羅的助手，第二年，劍橋大學評議會通過了授予牛頓大學學士學位的決定。

1665～1666年嚴重的鼠疫席捲了倫敦，劍橋離倫敦不遠，為恐波及，學校因此而停課，牛頓於1665年6月離校返鄉。

由於牛頓在劍橋受到數學和自然科學的熏陶和培養，對探索自然現象產生濃厚的興趣，家鄉安靜的環境又使得他的思想展翅飛翔。1665～1666年這段短暫的時光成為牛頓科學生涯中的黃金歲月，他在自然科學領域內思潮奔騰，才華迸發，思考前人從未思考過的問題，踏進了前人沒有涉及的領域，創建了前所未有的驚人業績。

1665年初，牛頓創立級數近似法,以及把任意冪的二項式化為一個級數的規則；同年11月，創立正流數法(微分)；次年1月，用三棱鏡研究顏色理論；5月，開始研究反流數法(積分)。這一年內，牛頓開始想到研究重力問題，並想把重力理論推廣到月球的運動軌道上去。他還從開普勒定律中推導出使行星保持在它們的軌道上的力必定與它們到旋轉中心的距離平方成反比。牛頓見蘋果落地而悟出地球引力的傳說，說的也是此時發生的軼事。

總之，在家鄉居住的兩年中，牛頓以比此後任何時候更為旺盛的精力從事科學創造，並關心自然哲學問題。他的三大成就：微積分、萬有引力、光學分析的思想都是在這時孕育成形的。可以說此時的牛頓已經開始著手描繪他一生大多數科學創造的藍圖。

1667年復活節後不久，牛頓返回到劍橋大學，10月1日被選為三一學院的仲院侶(初級院委)，翌年3月16日獲得碩士學位，同時成為正院侶(高級院委)。1669年10月27日，巴羅為了提攜牛頓而辭去了教授之職，26歲的牛頓晉升為數學教授，並擔任盧卡斯講座的教授。巴羅為牛頓的科學生涯打通了道路，如果沒有牛頓的舅父和巴羅的幫助，牛頓這匹千里馬可能就不會馳騁在科學的大道上。巴羅讓賢，這在科學史上一直被傳為佳話。

偉大的成就～建立微積分

在牛頓的全部科學貢獻中，數學成就佔有突出的地位。他數學生涯中的第一項創造性成果就是發現了二項式定理。據牛頓本人回憶，他是在1664年和1665年間的冬天，在研讀沃利斯博士的《無窮算術》時，試圖修改他的求圓面積的級數時發現這一定理的。

笛卡爾的解析幾何把描述運動的函數關系和幾何曲線相對應。牛頓在老師巴羅的指導下，在鑽研笛卡爾的解析幾何的基礎上，找到了新的出路。可以把任意時刻的速度看是在微小的時間范圍里的速度的平均值，這就是一個微小的路程和時間間隔的比值，當這個微小的時間間隔縮小到無窮小的時候，就是這一點的准確值。這就是微分的概念。

求微分相當於求時間和路程關系得在某點的切線斜率。一個變速的運動物體在一定時間范圍里走過的路程，可以看作是在微小時間間隔里所走路程的和，這就是積分的概念。求積分相當於求時間和速度關系的曲線下面的面積。牛頓從這些基本概念出發，建立了微積分。

微積分的創立是牛頓最卓越的數學成就。牛頓為解決運動問題，才創立這種和物理概念直接聯系的數學理論的，牛頓稱之為"流數術"。它所處理的一些具體問題，如切線問題、求積問題、瞬時速度問題以及函數的極大和極小值問題等，在牛頓前已經得到人們的研究了。但牛頓超越了前人，他站在了更高的角度，對以往分散的努力加以綜合，將自古希臘以來求解無限小問題的各種技巧統一為兩類普通的演算法——微分和積分，並確立了這兩類運算的互逆關系，從而完成了微積分發明中最關鍵的一步，為近代科學發展提供了最有效的工具，開辟了數學上的一個新紀元。

牛頓沒有及時發表微積分的研究成果，他研究微積分可能比萊布尼茨早一些，但是萊布尼茨所採取的表達形式更加合理，而且關於微積分的著作出版時間也比牛頓早。

在牛頓和萊布尼茨之間，為爭論誰是這門學科的創立者的時候，竟然引起了一場悍然大波，這種爭吵在各自的學生、支持者和數學家中持續了相當長的一段時間，造成了歐洲大陸的數學家和英國數學家的長期對立。英國數學在一個時期里閉關鎖國，囿於民族偏見，過於拘泥在牛頓的「流數術」中停步不前，因而數學發展整整落後了一百年。

應該說，一門科學的創立決不是某一個人的業績，它必定是經過多少人的努力後，在積累了大量成果的基礎上，最後由某個人或幾個人總結完成的。微積分也是這樣，是牛頓和萊布尼茨在前人的基礎上各自獨立的建立起來的。

1707年，牛頓的代數講義經整理後出版，定名為《普遍算術》。他主要討論了代數基礎及其(通過解方程)在解決各類問題中的應用。書中陳述了代數基本概念與基本運算，用大量實例說明了如何將各類問題化為代數方程，同時對方程的根及其性質進行了深入探討，引出了方程論方面的豐碩成果，如，他得出了方程的根與其判別式之間的關系，指出可以利用方程系數確定方程根之冪的和數，即「牛頓冪和公式」。

牛頓對解析幾何與綜合幾何都有貢獻。他在1736年出版的《解析幾何》中引入了曲率中心，給出密切線圓(或稱曲線圓)概念，提出曲率公式及計算曲線的曲率方法。並將自己的許多研究成果總結成專論《三次曲線枚舉》，於1704年發表。此外，他的數學工作還涉及數值分析、概率論和初等數論等眾多領域。

偉大的成就～對光學的三大貢獻

在牛頓以前，墨子、培根、達·芬奇等人都研究過光學現象。反射定律是人們很早就認識的光學定律之一。近代科學興起的時候，伽利略靠望遠鏡發現了「新宇宙」，震驚了世界。荷蘭數學家斯涅爾首先發現了光的折射定律。笛卡爾提出了光的微粒說……

牛頓以及跟他差不多同時代的胡克、惠更斯等人，也象伽利略、笛卡爾等前輩一樣，用極大的興趣和熱情對光學進行研究。1666年，牛頓在家休假期間，得到了三棱鏡，他用來進行了著名的色散試驗。一束太陽光通過三棱鏡後，分解成幾種顏色的光譜帶，牛頓再用一塊帶狹縫的擋板把其他顏色的光擋住，只讓一種顏色的光在通過第二個三棱鏡，結果出來的只是同樣顏色的光。這樣，他就發現了白光是由各種不同顏色的光組成的，這是第一大貢獻。

牛頓為了驗證這個發現，設法把幾種不同的單色光合成白光，並且計算出不同顏色光的折射率，精確地說明了色散現象。揭開了物質的顏色之謎，原來物質的色彩是不同顏色的光在物體上有不同的反射率和折射率造成的。公元1672年，牛頓把自己的研究成果發表在《皇家學會哲學雜志》上，這是他第一次公開發表的論文。

許多人研究光學是為了改進折射望遠鏡。牛頓由於發現了白光的組成，認為折射望遠鏡透鏡的色散現象是無法消除的(後來有人用具有不同折射率的玻璃組成的透鏡消除了色散現象)，就設計和製造了反射望遠鏡。

牛頓不但擅長數學計算，而且能夠自己動手製造各種試驗設備並且作精細實驗。為了製造望遠鏡，他自己設計了研磨拋光機，實驗各種研磨材料。公元1668年，他製成了第一架反射望遠鏡樣機，這是第二大貢獻。公元1671年，牛頓把經過改進得反射望遠鏡獻給了皇家學會，牛頓名聲大震，並被選為皇家學會會員。反射望遠鏡的發明奠定了現代大型光學天文望遠鏡的基礎。

同時，牛頓還進行了大量的觀察實驗和數學計算，比如研究惠更斯發現的冰川石的異常折射現象，胡克發現的肥皂泡的色彩現象，「牛頓環」的光學現象等等。

牛頓還提出了光的「微粒說」，認為光是由微粒形成的，並且走的是最快速的直線運動路徑。他的「微粒說」與後來惠更斯的「波動說」構成了關於光的兩大基本理論。此外，他還製作了牛頓色盤等多種光學儀器。

偉大的成就～構築力學大廈

牛頓是經典力學理論的集大成者。他系統的總結了伽利略、開普勒和惠更斯等人的工作，得到了著名的萬有引力定律和牛頓運動三定律。

在牛頓以前，天文學是最顯赫的學科。但是為什麼行星一定按照一定規律圍繞太陽運行？天文學家無法圓滿解釋這個問題。萬有引力的發現說明，天上星體運動和地面上物體運動都受到同樣的規律——力學規律的支配。

早在牛頓發現萬有引力定律以前，已經有許多科學家嚴肅認真的考慮過這個問題。比如開普勒就認識到，要維持行星沿橢圓軌道運動必定有一種力在起作用，他認為這種力類似磁力，就像磁石吸鐵一樣。1659年，惠更斯從研究擺的運動中發現，保持物體沿圓周軌道運動需要一種向心力。胡克等人認為是引力，並且試圖推到引力和距離的關系。

1664年，胡克發現彗星靠近太陽時軌道彎曲是因為太陽引力作用的結果；1673年，惠更斯推導出向心力定律；1679年，胡克和哈雷從向心力定律和開普勒第三定律，推導出維持行星運動的萬有引力和距離的平方成反比。

牛頓自己回憶，1666年前後，他在老家居住的時候已經考慮過萬有引力的問題。最有名的一個說法是：在假期里，牛頓常常在花園里小坐片刻。有一次，象以往屢次發生的那樣，一個蘋果從樹上掉了下來……

一個蘋果的偶然落地，卻是人類思想史的一個轉折點，它使那個坐在花園里的人的頭腦開了竅，引起他的沉思：究竟是什麼原因使一切物體都受到差不多總是朝向地心的吸引呢？牛頓思索著。終於，他發現了對人類具有劃時代意義的萬有引力。

牛頓高明的地方就在於他解決了胡克等人沒有能夠解決的數學論證問題。1679年，胡克曾經寫信問牛頓，能不能根據向心力定律和引力同距離的平方成反比的定律，來證明行星沿橢圓軌道運動。牛頓沒有回答這個問題。1685年，哈雷登門拜訪牛頓時，牛頓已經發現了萬有引力定律：兩個物體之間有引力，引力和距離的平方成反比，和兩個物體質量的乘積成正比。

當時已經有了地球半徑、日地距離等精確的數據可以供計算使用。牛頓向哈雷證明地球的引力是使月亮圍繞地球運動的向心力，也證明了在太陽引力作用下，行星運動符合開普勒運動三定律。

在哈雷的敦促下，1686年底，牛頓寫成劃時代的偉大著作《自然哲學的數學原理》一書。皇家學會經費不足，出不了這本書，後來靠了哈雷的資助，這部科學史上最偉大的著作之一才能夠在1687年出版。

牛頓在這部書中，從力學的基本概念(質量、動量、慣性、力)和基本定律(運動三定律)出發，運用他所發明的微積分這一銳利的數學工具，不但從數學上論證了萬有引力定律，而且把經典力學確立為完整而嚴密的體系，把天體力學和地面上的物體力學統一起來，實現了物理學史上第一次大的綜合。

站在巨人的肩上

牛頓的研究領域非常廣泛，他除了在數學、光學、力學等方面做出卓越貢獻外，他還花費大量精力進行化學實驗。他常常六個星期一直留在實驗室里，不分晝夜的工作。他在化學上花費的時間並不少，卻幾乎沒有取得什麼顯著的成就。為什麼同樣一個偉大的牛頓，在不同的領域取得的成就竟那麼不一樣呢？

其中一個原因就是各個學科處在不同的發展階段。在力學和天文學方面，有伽利略、開普勒、胡克、惠更斯等人的努力，牛頓有可能用已經准備好的材料，建立起一座宏偉壯麗的力學大廈。正象他自己所說的那樣「如果說我看得遠，那是因為我站在巨人的肩上」。而在化學方面，因為正確的道路還沒有開辟出來，牛頓沒法走到可以砍伐材料的地方。

牛頓在臨終前對自己的生活道路是這樣總結的：「我不知道在別人看來，我是什麼樣的人；但在我自己看來，我不過就象是一個在海濱玩耍的小孩，為不時發現比尋常更為光滑的一塊卵石或比尋常更為美麗的一片貝殼而沾沾自喜，而對於展現在我面前的浩瀚的真理的海洋，卻全然沒有發現。」

這當然是牛頓的謙遜。

怪異的牛頓

牛頓並不善於教學，他在講授新近發現的微積分時，學生都接受不了。但在解決疑難問題方面的能力，他卻遠遠超過了常人。還是學生時，牛頓就發現了一種計算無限量的方法。他用這個秘密的方法，算出了雙曲面積到二百五十位數。他曾經高價買下了一個棱鏡，並把它作為科學研究的工具，用它試驗了白光分解為的有顏色的光。

開始，他並不願意發表他的觀察所得，他的發現都只是一種個人的消遣，為的是使自己在寂靜的書齋中解悶，他獨自遨遊於自己所創造的超級世界裡。後來，在好友哈雷的竭力勸說下，才勉強同意出版他的手稿，才有劃時代巨著《自然哲學的數學原理》的問世。

作為大學教授，牛頓常常忙得不修邊幅，往往領帶不結，襪帶不系好，馬褲也不紐扣，就走進了大學餐廳。有一次，他在向一位姑娘求婚時思想又開了小差，他腦海了只剩下了無窮量的二項式定理。他抓住姑娘的手指，錯誤的把它當成通煙斗的通條，硬往煙斗里塞，痛得姑娘大叫，離他而去。牛頓也因此終生未娶。

牛頓從容不迫地觀察日常生活中的小事，結果作出了科學史上一個個重要的發現。他馬虎拖沓，曾經鬧過許多的笑話。一次，他邊讀書，邊煮雞蛋，等他揭開鍋想吃雞蛋時，卻發現鍋里是一隻懷表。還有一次，他請朋友吃飯，當飯菜准備好時，牛頓突然想到一個問題，便獨自進了內室，朋友等了他好久還是不見他出來，於是朋友就自己動手把那份雞全吃了，雞骨頭留在盤子，不告而別了。等牛頓想起，出來後，發現了盤子里的骨頭，以為自己已經吃過了，便轉身又進了內室，繼續研究他的問題。

牛頓晚年

但是由於受時代的限制，牛頓基本上是一個形而上學的機械唯物主義者。他認為運動只是機械力學的運動，是空間位置的變化；宇宙和太陽一樣是沒有發展變化的；靠了萬有引力的作用，恆星永遠在一個固定不變的位置上……

隨著科學聲譽的提高，牛頓的政治地位也得到了提升。1689年，他被當選為國會中的大學代表。作為國會議員，牛頓逐漸開始疏遠給他帶來巨大成就的科學。他不時表示出對以他為代表的領域的厭惡。同時，他的大量的時間花費在了和同時代的著名科學家如胡克、萊布尼茲等進行科學優先權的爭論上。

晚年的牛頓在倫敦過著堂皇的生活，1705年他被安妮女王封為貴族。此時的牛頓非常富有，被普遍認為是生存著的最偉大的科學家。他擔任英國皇家學會會長，在他任職的二十四年時間里，他以鐵拳統治著學會。沒有他的同意，任何人都不能被選舉。

晚年的牛頓開始致力於對神學的研究，他否定哲學的指導作用，虔誠地相信上帝，埋頭於寫以神學為題材的著作。當他遇到難以解釋的天體運動時，竟提出了「神的第一推動力」的謬論。他說「上帝統治萬物，我們是他的僕人而敬畏他、崇拜他」。

1727年3月20日，偉大艾薩克·牛頓逝世。

G. 直線和圓的顯示（在線等答案）

實驗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（即直線斜率）。
注意：上述分析的演算法僅適用於k1的情形。在這種情況下，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）注意上述程序考慮到當k1的情形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演算法的運算速度很快。

H. DDA演算法的介紹

DDA演算法，是計算機圖形學中一種基於直線的微分方程來生成直線的方法，由於有浮點數運算與取整，該演算法不利於硬體實現1。

I. DDA演算法的演算法思想

直線的基本微分方程為： 。
設直線通過點 和 ，則直線方程可表示為： 。
如果已知第 點的坐標，可用步長 和 得到第 點的坐標為：

或
如下圖：


將算得的直線上每個點的當前坐標，按四捨五入得到光柵點的位置。

J. DDA方法的應用

DDA自問世以來已經獲得極為廣泛的應用。裴覺民等^［23］將DDA方法應用在裂隙岩體邊坡工程中，對原始邊坡和開挖後的邊坡進行了計算，並考慮了爆破作用對邊坡穩定性的影響。T.C.Ke^［24］應用DDA方法和極限平衡法研究了某邊坡的穩定性，指出了DDA方法的優越性；Xuecheng Dong^［25］將 DDA 方法應用在三峽船閘邊坡的穩定性研究中；S.L.Zhao等^［26］、G.Q.Chen 等^［27］將 DDA 方法應用在岩石邊坡的穩定性分析中；Y.H.Hat zor^［28］應用關鍵塊體理論和DDA方法研究了Masada山脈某邊坡的穩定性及破壞模式；周少懷等^［29］基於DDA演算法，補充和發展了DDA方法計算機程序，分析了邊坡大位移問題和地下開挖引起地面變形的工程實例，並與離散元計算結果進行了比較研究。Kim YongⅡ等（1996）^［19］將DDA方法應用在地下工程的開挖及岩體支護設計中，認為所建立的演算法可以模擬地下工程的開挖過程。首先要計算出開挖前岩體內的應力狀態，其次根據第一次開挖步來確定新產生的應力分布，新產生的應力作為下一次開挖的初始應力，開挖過程結束以前一直進行這樣的迭代計算。經過算例研究，認為岩體開挖的最終穩定性與開挖次序及相應的應力歷史有關。另外，他們還進行了噴射混凝土和混凝土襯砌方面的研究，將噴射混凝土和混凝土襯砌處理成具有一定厚度和材料性質的單元進行分析研究。鄔愛清等^［30］根據已初步開發出的DDA模型計算程序，分別就某工程試驗洞開挖和邊坡明挖問題進行了計算，並與有限元結果進行了比較，結果表明，DDA模型計算結果在岩體開挖位移形態及位移量級上與有限元及實際位移監測結果都具有較好的可比性。

Kuokai Shyu 等^［13］應用DDA方法研究了在地震作用下Bartlett 壩肩的穩定性；Shilong Zhao等^［31］應用DDA方法研究了岩體的傾倒破壞問題；Lanbo Liu^［32］應用DDA方法研究了大地構造學中的板塊運動；Takeshi Sasaki等^［33］應用有限元方法和DDA方法研究了裂隙岩體地基的穩定性，結果與解析分析極為吻合；C.J.Pearce等（1998）^［34］將DDA方法應用在混凝土破裂行為模擬中；Y.I.Kim等^［35］將DDA方法應用在混凝土壩基的穩定性分析中；S.M.Hsiung^［36］等將DDA方法應用在地震荷載對地下工程的穩定性影響中；A.Mortazavi等^［37］將DDA方法應用在礦山岩暴分析中；戴華陽等^［38］提出了急傾斜煤層開采地表非連續變形的度量方法。

DDA方法主要是針對岩石介質的，T.C.Ke 等^［39］、P.A.Thomas 等^［40］、Yuzo Ohnishi等^［41］、Kuokai Shyu 等^［42］將其應用在土力學中，給出了顆粒體介質DDA的演算法；Y.N.Oh等^［43］將DDA方法應用在海堤基礎及地基土的相互作用中；L.K.Chien^［44］等將DDA方法應用在海床的沖刷與回填穩定性分析中；張國新等^［45］採用正多邊形體代替圓形顆粒體來模擬土的應力-應變關系。

國內外學者對DDA的大量研究，使得該方法更加成熟、更加適合於岩體系統的變形分析。由於DDA方法具有完備的塊體運動學理論，且將靜力分析與動力分析統一起來，因此其具有處理結構工程、岩體力學以及材料分析等方面的能力。但也應該清晰地看到，DDA方法問世僅10餘年，在具體應用上仍然存在一些不足。我們知道，DDA方法最初是用於解決岩體不連續變形問題的，其用實際結構面所切割的岩塊作為分析單元，但目前國內外在研究與應用DDA方法中均忽略了對結構面的調查與研究，往往用假想的規則的塊體單元或者考慮了規模比較大的實際結構面所形成的塊體單元進行研究^［46］，忽略了隨機分布的較小規模的結構面，這樣的單元僅能用於驗證 DDA的有效性，而不能用於實際工程中；另外目前的研究忽略了結構面的充填厚度，實際上結構面的充填物對岩體的穩定性具有重要的影響。從工程實踐來看，結構面不論規模大小幾乎都有一定程度的充填，結構面的充填物不能像文獻［47］等那樣簡單地理解為軟弱夾層，充填的是泥土、碎石土等，事實上，在新鮮岩體內結構面的充填物具有相當高的彈性模量，且充填厚度與結構面的規模成一定比例關系^［48］。岩體變形包括結構體（塊體）變形和結構面變形，因此塊體系統的變形不僅發生在塊體本身，也包括結構面的變形，而且塊體本身的變形往往小於結構面的變形，因此要合理地描述整個塊體系統的變形，應該研究結構面的變形對整個塊體系統變形的貢獻。