Bresenham畫線算法

1、以前看到Bresenham畫線算法，直接拿來用，沒有去推導它,近日,參考一些資料,特整理其算法推導過程如下。各位大蝦如果知道其細節(jié)，趕緊閃過，不用浪費時間了?；旧螧resenham畫線算法的思路如下: / 假設該線段位于第一象限內(nèi)且斜率大于0小于1,設起點為(x1,y1),終點為(x2,y2)./ 根據(jù)對稱性,可推導至全象限內(nèi)的線段.1.畫起點(x1,y1).2.準備畫下個點。x坐標增1，判斷如果達到終點，則完成。否則，由圖中可知,下個要畫的點要么為當前點的右鄰接點,要么是當前點的右上鄰接點.(即中點)3.畫點(U或者B).4.跳回第2步.5.結(jié)束.這里需要細化的是怎么判斷下個要畫的點為當前

2、點的右鄰接點還是當前點的右上鄰接點.設線段方程：ax+by+c=0(x1<x<x2,y1<y<y2)令dx=x2-x1,dy=y2-y1則：斜率-a/b = dy/dx.從第一個點開始，我們有F(x,1,y1) = a*x1+b*y1+c=0下面求線段ax+by+c=0與x=x1+1的交點:由a*(x1+1)+b*y+c = 0, 求出交點坐標y=(-c-a(x1+1)/b所以交點與M的y坐標差值Sub1 = (-c-a(x1+1)/b - (y1+0.5) = -a/b-0.5，即Sub1的初始值為-a/b-0.5。則可得條件當 Sub1 = -a/b-0.5>

3、0時候,即下個點為U.反之,下個點為B.代入a/b,則Sub1 = dy/dx-0.5.因為是個循環(huán)中都要判斷Sub,所以得求出循環(huán)下的Sub表達式,我們可以求出Sub的差值的表達式.下面求x=x1+2時的Sub，即Sub21.如果下下個點是下個點的右上鄰接點，則Sub2 = (-c-a(x1+2)/b - (y1+1.5) = -2a/b - 1.5故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 1.5 - (-a/b-0.5) = -a/b - 1.代入a/b得Dsub = dy/dx -1;2.如果下下個點是下個點的右鄰接點，Sub2 = (-c-a(x1+2)/b

4、 - (y1+0.5) = -2a/b - 0.5故Sub差值Dsub = Sub2 - Sub1 = -2a/b - 0.5 - (-a/b-0.5) = -a/b. 代入a/b得Dsub = dy/dx;于是，我們有了Sub的初始值Sub1 = -a/b-0.5 = dy/dx-0.5,又有了Sub的差值的表達式Dsub = dy/dx -1 （當Sub1 > 0）或 dy/dx（當Sub1 < 0）.細化工作完成。于是pcode可以細化如下： / Pcode for Bresenham Line/ By SoRoManx=x1;y=y1;dx = x2-x1;dy = y2-

5、y1;Sub = dy/dx-0.5; / 賦初值，下個要畫的點與中點的差值DrawPixel(x, y); / 畫起點while(x<x2) x+;  if(Sub > 0) / 下個要畫的點為當前點的右上鄰接點   Sub += dy/dx - 1; /下下個要畫的點與中點的差值  y+; / 右上鄰接點y需增1  else/ 下個要畫的點為當前點的右鄰接點   Sub += dy/dx;   / 畫下個點DrawPixel(x,y);PS:一般優(yōu)化：為避免小數(shù)轉(zhuǎn)整數(shù)以

6、及除法運算，由于Sub只是用來進行正負判斷，所以可以令Sub = 2*dx*Sub = 2dy-dx,則相應的DSub = 2dy - 2dx或2dy.思考1:如果Sub = 0時，會產(chǎn)生取兩個點都可以的問題。這個問題還沒深入。/*/*液晶屏 點陣屏 繪制直線函數(shù) 采用BresenHam算法void draw_line(uint x1,uint y1,uint x2,uint y2,uint linecolor )int temp;int x,y;int dx,dy,e;if(x1>x2)/交換坐標 保證x1始終是起點   temp=x1;x1=x2;x2=temp;

7、   temp=y1;y1=y2;x1=temp;dx=x2-x1;dy=y2-y1;x=x1;y=y1;if(dy=0)/斜率為0   for(temp=x1;temp<x2;temp+)   draw_point(temp,y1,linecolor);if(dy>0)/斜率小于0   if(dy<dx)/斜率大于-1       e=-dx;    for (temp=0; temp<dx; temp+)&#

8、160;        draw_point (x, y, linecolor);        x+;     e=e+2*dy;     if (e>=0)            y+; e=e-2*dx;         

9、60;        else /斜率小于-1       e=-dy;    for (temp=0; temp<dy; temp+)         draw_point (x, y, linecolor);        y+;      e=e+2*dx;  

10、60;  if (e>=0)            x+; e=e-2*dy;               if(dy<0)/正斜率   dy=-dy;   if(dy<dx)/斜率小于1       e=-dx;    for (temp=0; te

11、mp<dx; temp+)         draw_point (x, y, linecolor);        x+;      e=e+2*dy;     if (e>=0)            y-; e=e-2*dx;                  else       e=-dy;    for (temp=0; temp<dy; temp+)         draw_point (x, y, linecolor);        y-;