bresenham直線演算法

⑴ 直線的生成演算法有哪些

第一種演算法：DDA直線生成演算法是一種使用微分方程生成直線的演算法，又稱作數值微分法。該演算法的基本思想是：根據斜率確定增量最大的方向，每次迭代時均在該方向上走一步，然後根據直線方程計算出另一方向上的值，對其四捨五入後得到像素坐標。第二種演算法：Bresenham直線生成演算法與DDA演算法類似，每次迭代時均在增量最大方向上走一步，並計算決策參數，根據決策參數確定像素坐標。演算法的巧妙之處在於採用了增量計算，使得對於每一列，只要檢查誤差量的符號，就可以確定該下一列的像素坐標。

⑵ 直線掃描演算法（個人總結，僅供參考）

直線掃描演算法主要包含三種演算法，DDA演算法、中點畫線演算法、Bresenham直線演算法。

這三種演算法都要事先要確定兩個端點（起點和終點），從起點開始每次走一步，每走一步畫一個點，直至到達終點。

這個前提也比較好理解，因為如果朝斜率大的方向走，可能沒走幾步就走完了，那畫出來的直線就是離散的。

以下我們只討論朝x方向移動的情況。（y方向的情況是一樣的）

DDA演算法實際上是根據 斜截式直線方程 來畫的。

但這么做實際上是比較消耗性能的，因為斜截式方程， 它涉及到了乘法運算 。因此我們需要通過 增量思想 對它進行優化。

這樣轉換後，我們就可以根據當前的位置來找到下一步的位置，且每次計算只需要進行一次 浮點的加法運算 ，一次四捨五入取整即可。

中點畫線演算法實際上是根據 一般式直線方程 來畫的。它是通過判斷中點在直線的下方還是上方，來決定下一步的坐標位置。

但這樣也是非常消耗性能的，把中點帶入F(x, y)中，會涉及到2個乘法，4個加法。我們依然可以通過增量的方式來對它進行優化。

這樣我們就優化到每次只需要一次 整數加法 即可，且還不需要四捨五入。因此它要更優於DDA演算法。

Breseham演算法是通過比較d(交點與交點下方最近的點的距離)來進行選擇的。d每次按照k的大小增加。

但這么做依舊和DDA演算法一樣，會涉及到浮點數k的加法。我們可以通過 換元的方式 對它進行下優化。

這樣就能使得每次進行一次或兩次的 整數加法運算 ，不需要四捨五入。效率高於DDA，低於中點畫線演算法。

但Bresenham演算法不依賴直線方程，使得它能有更寬泛的適用范圍。

⑶ Bresenham畫線演算法

基本上Bresenham畫線演算法的思路如下:
//
假設該線段位於第一象限內且斜率大於0小於1,設起點為(x1,y1),終點為(x2,y2).
//
根據對稱性,可推導至全象限內的線段.
1.畫起點(x1,y1).
2.准備畫下個點。x坐標增1，判斷如果達到終點，則完成。否則，由圖中可知,下個要畫的點要麼為當前點的右鄰接點,要麼是當前點的右上鄰接點.
2.1.如果線段ax+by+c=0與x=x1+1的交點的y坐標大於M點的y坐標的話,下個點為U(x1+1,y1+1)
2.2.否則,下個點為B(x1+1,y1+1)
3.畫點(U或者B).
4.跳回第2步.
5.結束.
這里需要細化的是怎麼判斷下個要畫的點為當前點的右鄰接點還是當前點的右上鄰接點.
設線段方程：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>0時候,即下個點為U.
反之,下個點為B.
代入a/b,則Sub1
=
dy/dx-0.5.
因為是個循環中都要判斷Sub,所以得求出循環下的Sub表達式,我們可以求出Sub的差值的表達式.下面求x=x1+2時的Sub，即Sub2
1.如果下下個點是下個點的右上鄰接點，則
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
-
(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
SoRoMan
x=x1;
y=y1;
dx
=
x2-x1;
dy
=
y2-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:一般優化：
為避免小數轉整數以及除法運算，由於Sub只是用來進行正負判斷，所以可以令Sub
=
2*dx*Sub
=
2dy-dx,則
相應的DSub
=
2dy
-
2dx或2dy.
思考1:如果Sub
=
0時，會產生取兩個點都可以的問題。這個問題還沒深入。

⑷ 關於Bresenham演算法的求助

今天一下子遇到三個類似的問題，所以我這篇東西就連續復制粘貼了三遍：

（下面的坐標本來是有下標的，但復制過來就變沒了，你可能看的有點暈）

Bresenham演算法是Bresenham提出的一種光柵線生成演算法！

DDA演算法表面上看起來很有效，並且代碼也比較容易實現，但是顯示每個像素都需要進行一次浮點數加法運算，而Bresenham演算法的最大優點是不需要進行浮點數運算！這是一種精確而有效的光柵線生成演算法，該演算法僅使用增量整數計算，計算速度比DDA要快，另外，Bresenham演算法還可用於顯示圓和其他曲線，這里暫時只顯示直線！

與DDA一樣，我們假設線段的兩個端點坐標是整數值（x0,y0）（xEnd,yEnd）,且斜率m滿足0<=m>=1!坐標軸的垂直軸表示掃描線位置，水平軸標識像素列，假設以單位x間隔取樣，需要確定下一個每次取樣時兩個可能的像素位置中的哪一個更接近於線路徑！

從給定線段的左端點（x0,y0）開始,逐步處理每個後繼列（x位置），並在其掃描線y值最接近線段的像素處描出一點，假如已經確定要顯示的像素在（xk,yk），那麼下一步就要確定在列xk+1=xk+1上繪制哪個像素，是在位置(xk+1,yk)還是在(xk+1,yk+1)

在取樣位置xk+1，我們使用dlower和pper來標識兩個像素與數學上線路徑的垂直偏移（就是通過這兩個值來比較哪個點離線上的點最近，以下推導過程你可能看得有點暈，但都是為了推出後續的點而已，你可以結合下面例子程序中的Bresenham函數來看），在像素列xk+1處的直線上的y坐標根據直線方程可計算得：

y=m(xk+1)+b

那麼可求得：

dlower=y-yk=m(xk+1)+b-yk

pper=(yk+1)-y=yk+1-m(xk+1)-b

令斜率m=dy/dx,引入決策參數Pk，定義為：

Pk=dx(dlower-pper)

=2dx*xk-2dy*yk+c

C是一個常數，值為2dx+dx(2b-1)

由此可以計算得到

pk+1=Pk+2dy-2dx(yk+1-yk)

其中yk+1-yk取0還是取1取決於參數Pk的符號，Pk為負時取0，Pk非負時取1！

而Pk為負時，下一個要繪制的點就是（xk+1,yk）且pk+1=Pk+2dy

Pk為非負時則下一個要繪制的點就是（xk+1,yk+1）且pk+1=Pk+2dy-2dx

至此，Bresenham演算法介紹完畢，以下為某個示例：

#include<gl/glut.h>

#include<math.h>

#include<stdio.h>

voiddraw_pixel(intix,intiy)

{

glBegin(GL_POINTS);

glVertex2i(ix,iy);

glEnd();

}

voidBresenham(intx1,inty1,intxEnd,intyEnd)

{

intdx=abs(xEnd-x1),dy=abs(yEnd-y1);

intp=2*dy-dx;

inttwoDy=2*dy,twoDyMinusDx=2*dy-2*dx;

intx,y;

if(x1>xEnd)

{

x=xEnd;y=yEnd;

xEnd=x1;

}

else

{

x=x1;

y=y1;

}

draw_pixel(x,y);

while(x<xEnd)

{

x++;

if(p<0)

p+=twoDy;

else

{

y++;

p+=twoDyMinusDx;

draw_pixel(x,y);

}

}

}

voiddisplay()

{

glClear(GL_COLOR_BUFFER_BIT);

Bresenham(0,0,400,400);

glFlush();

}

voidmyinit()

{

glClearColor(0.8,1.0,1.0,1.0);

glColor3f(0.0,0.0,1.0);

glPointSize(1.0);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D(0.0,500.0,0.0,500.0);

}

voidmain(intargc,char**argv)

{

glutInit(&argc,argv);

glutInitDisplayMode(GLUT_SINGLE|GLUT_RGB);

glutInitWindowSize(500,500);

glutInitWindowPosition(200.0,200.0);

glutCreateWindow("CG_test_Bresenham_Lineexample");

glutDisplayFunc(display);

myinit();

glutMainLoop();

}

運行效果：

⑸ Bresenham直線演演算法的演算方法

Bresenham直線演算法描繪的直線。假設我們需要由 (x0, y0) 這一點，繪畫一直線至右下角的另一點(x1, y1)，x,y分別代表其水平及垂直坐標，並且 x1 - x0 > y1 - y0。在此我們使用電腦系統常用的坐標系，即x坐標值沿x軸向右增長，y坐標值沿y軸向下增長。
因此x及y之值分別向右及向下增加，而兩點之水平距離為x1 − x0且垂直距離為y1-y0。由此得之，該線的斜率必定介乎於1至0之間。而此演算法之目的，就是找出在x0與x1之間，第x行相對應的第y列，從而得出一像素點，使得該像素點的位置最接近原本的線。
對於由(x0, y0)及(x1, y1)兩點所組成之直線，公式如下：
因此，對於每一點的x，其y的值是
因為x及y皆為整數，但並非每一點x所對應的y皆為整數，故此沒有必要去計算每一點x所對應之y值。反之由於此線之斜率介乎於1至0之間，故此我們只需要找出當x到達那一個數值時，會使y上升1，若x尚未到此值，則y不變。至於如何找出相關的x值，則需依靠斜率。斜率之計算方法為m = (y1 − y0) / (x1 − x0)。由於此值不變，故可於運算前預先計算，減少運算次數。
要實行此演算法，我們需計算每一像素點與該線之間的誤差。於上述例子中，誤差應為每一點x中，其相對的像素點之y值與該線實際之y值的差距。每當x的值增加1，誤差的值就會增加m。每當誤差的值超出0.5，線就會比較靠近下一個映像點，因此y的值便會加1，且誤差減1。
下列偽代碼是這演算法的簡單表達（其中的plot(x,y)繪畫該點，abs返回的是絕對值）。雖然用了代價較高的浮點運算，但很容易就可以改用整數運算（詳見最佳化一節）：
function line(x0, x1, y0, y1)
int deltax := x1 - x0
int deltay := y1 - y0
real error := 0
real deltaerr := deltay / deltax // 假設 deltax != 0 （非垂直線），
// 注意：需保留除法運算結果的小數部分
int y := y0
for x from x0 to x1
plot(x,y)
error := error + deltaerr
if abs(error) ≥ 0.5 then
y := y + 1
error := error - 1.0

⑹ 分別解釋直線生成演算法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：過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近的像素。該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項的符號，就可以確定該列所求的像素。

大概就是這樣，預知詳細，可以參考圖形學的書籍

⑺ 用C實現Bresenham演算法生成直線和圓的程序(要求具體步驟有必要解述)

Bresenham演算法生成直線
假定直線從(x1,y1)到(x2,y2)，
令dx=x2-x1，dy=y2-y1
不妨設(dx,dy)在第一象限,並且直線的斜率不大於1

畫線過程中有三個循環變數
x,y,d
初值
x=x1,y=y1,d=2*dy-dx

循環，直到x==x2為止
{
如果d>=0,y++,d+=2*(dy-dx)
如果d<0 ,x++,d+=2*dy
}

如果(dx,dy)不在第一象限，要做變換，即先把第一象限的畫出來
如果斜率大於1，x,y交換

非常簡單的，很容易實現
圓的演算法：

int Bres(int x0,int y0,double r,int color)

{
int x,y,d;
x=0;
y=(int)r;
d=(int)(3-2*r);
while(x<y)
{
cirpot(x0,y0,x,y,color);
if(d<0)
d+=4*x+6;
else
{
d+=4*(x-y)+10;
y--;
}
x++;
}
if(x==y)
cirpot(x0,y0,x,y,color);
return(0);
}
int cirpot(int x0,int y0,int x,int y,int color)
{
setcolor(color);
putxicl((x0+x),(y0+y));
putxicl((x0+y),(y0+x));
putxicl((x0+y),(y0-x));
putxicl((x0+x),(y0-y));
putxicl((x0-x),(y0-y));
putxicl((x0-y),(y0-x));
putxicl((x0-y),(y0+x));
putxicl((x0-x),(y0+y));
setcolor(color);
return(0);
}

這是圓的演算法，你若要整個程序，把你的電郵給我，我給你發過去、
運行環境是Turboc 2.0
int Bresline(int x1,inty1,int x2,int y2,int color)
{
int color,itag;
int dx,dy,tx,ty,inc1,inc2,d,curx,cury;
setcolor(color);
putxicl(x1,y1);
if(x1==x2&&y1==y2)
{
setcolor(color);
return(1);
}
itag=0;
dx=abs(x2-x1);
dy=abs(y2-y1);
if(dx<dy)
{
itag=1;]
iswap(&x1,&y1);
iswap(&x2,&y2);
iswap(&dx,&dy);
}
tx=(x2-x1)>0? 1:-1;
ty=(y2-y1)>0? 1:-1;
curx=x1;
cury=y1;
inc1=2*dy;
inc2=2*(dy-dx);
d=inc1-dx;
while(curx!x2)
{
if(d<0)
{
d+=inc1;
}
else
{
cury+=ty;
d+=inc2;
}
if(itag)
setpixel(cury,curx);
else
setpixel(curx,cury);
curxd+=tx;
}
setcolor(color);
return(0);
}
iswap(int*a,int*b)
{
int tmp;
tmp=*a;
*a=*b;
*b=tmp;
}

這是直線的演算法：和圓的差不多，你可以參考一下：）

⑻ bresenham演算法的原理

Bresenham演算法是計算機圖形學領域使用最廣泛的直線掃描轉換方法。
其原理是：
過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的
順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近
的像素。
該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項
的符號，就可以確定該列所求的像素。