bresenham演算法c
❶ C++語言通過Bresenham演算法畫直線怎麼寫，求代碼高人，謝謝了！
Bresenham畫線演算法程序/簡帶/偽代碼棗悄
void Bresenhamline (int x0,int y0,int x1, int y1,int color)
{ int x, y, dx, dy; float k, e;
dx = x1-x0;dy = y1- y0; k=dy/dx;
凳咐渣 e=-0.5;x=x0;y=y0;
for (i=0; i<=dx; i++)
{ Putpixel (x, y, color);
x=x+1; e=e+k;
if (e>= 0) { y++, e=e-1;}
}
}
❷ C語言用Bresenham演算法畫圓，哪位高手教教，主要是演算法里的內容，謝謝！
的確哈，關鍵在於對delta的理解
可以看到，都是delta=2*(1-radius)這樣的，起作用應該是判斷要畫的點x、y坐標的變化趨勢，先把我注釋了的代碼貼下，加了getch();可以看到畫的過程
-----------------------------------------------------------------
#include<graphics.h>
#include<stdio.h>
void BresenhemCircle(int centerx, int centery, int radius, int color, int type);
void main()
{
int drive=DETECT,mode;
int i,j;
initgraph(&drive,&mode,"");
BresenhemCircle(300,200,100,15,0);
getch();
}
void BresenhemCircle(int centerx, int centery, int radius, int color, int type)
{
int x =type = 0;/*初始橫坐標為原點*/
int y = radius; /*初始縱坐標遠離原點*/
int delta = 2*(1-radius);
int direction;
while (y >= 0)
{
getch();
if (!type)/*執行*/
{
/*在上半圓畫兩點*/
putpixel(centerx+x, centery+y, color);
putpixel(centerx-x, centery+y, color);
/*在下半圓畫兩點*/
putpixel(centerx-x, centery-y, color);
putpixel(centerx+x, centery-y, color);
getch();
}
else/*不執行*/
{
line(centerx+x, centery+y, centerx+x, centery-y);
line(centerx-x, centery+y, centerx-x, centery-y);
getch();
}
/*以下代碼設置下次四點的位置，圓是對稱的，且此方法相當於同時畫四個圓弧
觀察右上方圓弧可知，前一半是x增的要快些，後一半是y減的快些*/
if (delta < 0)
{
if ((2*(delta+y)-1) < 0)
direction = 1; /*選擇橫向加*/
else
direction = 2;
}
else if(delta > 0)
{
if ((2*(delta-x)-1) > 0)
direction = 3; /*選擇縱向減*/
else
direction = 2;
}
else
direction=2;
switch(direction)
{
case 1:
x++;/*只橫坐標遠離原點*/
delta += (2*x+1); /*小執行到這，所以加*/
break;
case 2:
x++;
y--;/*橫向遠離，同時縱向靠近*/
delta += 2*(x-y+1); /*即(2*x+1)+(-2*y+1)*/
break;
case 3:
y--;/*只縱坐標靠近原點*/
delta += (-2*y+1); /*大執行到這，所以減*/
break;
}
}
}
❸ bresenham演算法的Bresenham改進演算法
原理:
上述bresenham 演算法在計算直線斜率與誤差項時用到了小數與除法，可以改用整數以避免除法。由於演算法中用到談旅好誤差含鉛項的符號，因此可以做如下替換：e'=2*e*dx.
以下是C++語言方式描述的，在MFC下的鎮兄核心繪圖代碼（畫圓的演算法）
{
CDC* pDC=GetDC();
int p,r,x,y,c,i;
r=50;
p=3-2*r;
c=RGB(0,0,0);
x=0;
y=r;
i=100;
for(;x<=y;)
{
pDC->SetPixel(x+i,y+i,c);
pDC->SetPixel(-x+i,-y+i,c);
pDC->SetPixel(-x+i,y+i,c);
pDC->SetPixel(x+i,-y+i,c);
pDC->SetPixel(y+i,x+i,c);
pDC->SetPixel(-y+i,x+i,c);
pDC->SetPixel(-y+i,-x+i,c);
pDC->SetPixel(y+i,-x+i,c);
if(p<0)p=p+4*x+6;
else {y--;p=p+4*(x-y)+10;}
x++;
}
}
❹ 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時，會產生取兩個點都可以的問題。這個問題還沒深入。
❺ 用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演算法是計算機圖形學領域使用最廣泛的直線掃描轉換方法。
其原理是：
過各行、各列像素中心構造一組虛擬網格線，按直線從起點到終點的
順序計算直線各垂直網格線的交點，然後確定該列像素中與此交點最近
的像素。
該演算法的優點在於可以採用增量計算，使得對於每一列，只要檢查一個誤差項
的符號，就可以確定該列所求的像素。
❼ 求一用C語言畫直線的程序
不調用畫圖 API，用C 或 C++ 如何實現畫一條線？
Milo Yip：如何開始用 C++ 寫一個光柵化渲染器？
我嘗試用不同技術實現畫直線的方法（完整源代碼在 miloyip/line），此文簡單介紹個中思路。本文的代碼採用 C 語言、標准庫及極簡的 PNG 編碼函數 svpng()，沒有使用其他 API。
1. Bresenham 演算法
Bresenham直線演算法 [1] 是最簡單的直線光柵化（rasterization）演算法。
Bresenham 直線
如果像上圖，直線的高度小於寬度，那麼 Bresenham 直線演算法會為 軸每個坐標填入一個像素，繪畫每個像素時按斜率判斷 是否需要調整。整個演算法可以避開浮點數運算，只用整數運算實現。以下是一個簡單實現：
// Modified from https://rosettacode.org/wiki/Bitmap/Bresenham%27s_line_algorithm#C
void bresenham(int x0, int y0, int x1, int y1) {
int dx = abs(x1 - x0), sx = x0 < x1 ? 1 : -1;
int dy = abs(y1 - y0), sy = y0 < y1 ? 1 : -1;
int err = (dx > dy ? dx : -dy) / 2;
while (setpixel(x0, y0), x0 != x1 || y0 != y1) {
int e2 = err;
if (e2 > -dx) { err -= dy; x0 += sx; }
if (e2 < dy) { err += dx; y0 += sy; }
}
}
為了測試不同角度，我做了一個測試用例：
int main() {
memset(img, 255, sizeof(img));
float cx = w * 0.5f - 0.5f, cy = h * 0.5f - 0.5f;
for (int j = 0; j < 5; j++) {
float r1 = fminf(W, H) * (j + 0.5f) * 0.085f;
float r2 = fminf(W, H) * (j + 1.5f) * 0.085f;
float t = j * PI / 64.0f;
for (int i = 1; i <= 64; i++, t += 2.0f * PI / 64.0f) {
float ct = cosf(t), st = sinf(t);
bresenham((int)(cx + r1 * ct), (int)(cy - r1 * st), (int)(cx + r2 * ct), (int)(cy - r2 * st));
}
}
svpng(fopen("line_bresenham.png", "wb"), W, H, img, 0);
}
完整代碼 line_bresenham.c
渲染結果及中間局部放大：
2. 采樣方法
Bresenham 直線演算法有 3 個問題：
不能控制直線寬度；
坐標為整數；
只能對像素寫入一個顏色，只用單色會有嚴重的鋸齒效果。
在圖形學中，除了以逐個圖元（如直線）方式渲染，我們還可以通過對每個像素進行采樣（sampling），換句話說，我們可對整個圖像逐像素詢問：「這個像素的顏色是什麼？」
用采樣方式畫直線時，我們可以用一個具有面積的形狀去表示「直線」，例如是長方形。但在本文中，我們使用膠囊體（capsule）去表示直線。這樣就能解決上面前兩個問題：(1) 可用膠囊體半徑設置直線的寬度；(2) 坐標可以為浮點數。不過，用最簡單的采樣方式，我們需要在每像素查詢所有圖元是否佔有該像素，效率很低。
❽ bresenham演算法的介紹
bresenham演算法是計算機圖形學中為了「顯示器（屏幕或列印機）系由像素構成」的這個特性而設計出來的演算法，使得在求直線各點的過程中全部以整數來運算，因而大幅度提升計算速度。
❾ 用C++如何實現bresenham畫線演算法計算機圖形學上面有個drawpixel的函數。不知道怎麼用。
drawpixel()函數這就是VC畫點的，不同的平台由不同的函數來畫點，這個是API函數不管什麼平台歸結到底都是調用這個函數來畫點。
COLORREF SetPixel(
HDC hdc, // handle to DC
int X, // x-coordinate of pixel
int Y, // y-coordinate of pixel
COLORREF crColor // pixel color
);
❿ 關於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();
}
運行效果：