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();
}
运行效果：