Bresenham的直线生成算法和整圆生成算法完整代码

///<summary>/// Bresenham画线算法，给出两个点a,b///</summary>///PS:这里XiangSu是光栅的最小距离，因为我是在高分辨率的窗口中模拟低分辨率效果，///所以用这个XiangSu来控制模拟的光栅最小单元格的边的大小，实际运用中XiangSu=1///<param name="a"></param>///<param name="b"></param>void Bresenhamline(Point a, Point b){int x, y, dx, dy, s1, s2, p, temp, interchange, i;x = a.X;y = a.Y;dx = Math.Abs(b.X - a.X);dy = Math.Abs(b.Y - a.Y);if (b.X > a.X)s1 = XiangSu;elses1 = -XiangSu;if (b.Y > a.Y)s2 = XiangSu;elses2 = -XiangSu;if (dy > dx){temp = dx;dx = dy;dy = temp;interchange = 1;}elseinterchange = 0;p = 2 * dy - dx;for (i = 1; i <= dx; i += XiangSu){tempp.X = x;tempp.Y = y;tempP.Add(tempp);Vram[x + y * 600] = true;//把该片内存置为边界标记if (p >= 0){if (interchange == 0)y = y + s2;elsex = x + s1;p = p - 2 * dx;}if (interchange == 0)x = x + s1;elsey = y + s2;p = p + 2 * dy;}}///<summary>///定时器，用来动态呈现绘制过程///</summary>///<param name="sender"></param>///<param name="e"></param>private void timer1_Tick(object sender, EventArgs e){if (show < tempP.Count){Rectangle rect = new Rectangle(tempP[show].X - XiangSu / 2, tempP[show].Y - XiangSu / 2, XiangSu, XiangSu);g.FillEllipse(black, rect);show++;}else{timer1.Enabled=false;}}///<summary>///鼠标点击事件回调函数///用来描点、标记、存储///</summary>private void Form1_MouseClick(object sender, MouseEventArgs e){//show==0表示连线状态//show==tempP.Count表示已经连线连完，定时器关闭//show在上述两者之间表示正在连线，定时器打开if (show != 0) return;if(PortList.Enabled==true) PortList.Enabled = false;//当已经开始选择点的时候就不能修改像素点了tempp.X = e.X / XiangSu * XiangSu;//取像素的整数倍Very Importanttempp.Y = e.Y / XiangSu * XiangSu;P.Add(tempp);Rectangle rect = new Rectangle(tempp.X - XiangSu, tempp.Y - XiangSu, XiangSu * 2, XiangSu * 2); //鼠标点击要大一点2倍像素点，好看g.FillEllipse(blue, rect);g.DrawString(P.Count.ToString() + " : (" + tempp.X + "," + tempp.Y + ")", new Font("微软雅黑", 8), black, tempp);}///<summary>///新建菜单消息回调函数///用来清除已经保存的点以及刷屏///</summary>///<param name="sender"></param>///<param name="e"></param>private void新建ToolStripMenuItem_Click(object sender, EventArgs e){}///<summary>///退出菜单消息回调函数///</summary>///<param name="sender"></param>///<param name="e"></param>private void退出ToolStripMenuItem_Click(object sender, EventArgs e){}。

画圆形（Bresenham算法）下⾯先简要介绍常⽤的画圆算法（Bresenham算法），然后再具体阐述笔者对该算法的改进。

⼀个圆，如果画出了圆上的某⼀点，那么可以利⽤对称性计算余下的七段圆弧：Plot(x，y)，Plot(y，x)，Plot(y，-x)，Plot(x，-y)，Plot(-x，-y)，Plot(-y，-x)，Plot(-y，x)，Plot(-x，y)。

1、Bresenham 画圆算法。

Bresenham算法的主要思想是：以坐标原点（0，0）为圆⼼的圆可以通过0度到45°的弧计算得到，即x从0增加到半径，然后利⽤对称性计算余下的七段圆弧。

当x从0增加到时，y从R递减到。

设圆的半径为R，则圆的⽅程为：f(x，y)＝(x+1)2+y2-R2＝0 (1)假设当前列（x=xi列）中最接近圆弧的像素已经取为P(xi，yi)，根据第⼆卦限1/8圆的⾛向，下⼀列（x=xi+1列）中最接近圆弧的像素只能在P的正右⽅点H(xi+1，yi)或右下⽅点L(xi+1，yi-1)中选择，如图1所⽰。

Bresenham画圆算法采⽤点T(x，y)到圆⼼的距离平⽅与半径平⽅之差D(T)作为选择标准，即D(T)=(x+1)2+y2-R2 (2)通过⽐较H、L两点各⾃对实圆弧上点的距离⼤⼩，即根据误差⼤⼩来选取，具有最⼩误差的点为绘制点。

根据公式(2)得：对H(xi+1，yi)点有：D(H)=(xi+1)2+yi2-R2；对L(xi+1，yi-1)点有：D(L)=(xi+1)2+(yi-1)2-R2；根据Bresenham画圆算法，则选择的标准是：如果|D(H)|<|D(L)|，那么下⼀点选取H(xi+1，yi)；如果|D(H)|>|D(L)|，那么下⼀点选取L(xi+1，yi-1)；如果|D(H)|=|D(L)|，那么下⼀点可以取L(xi+1，yi-1)，也可以选取H(xi+1，yi)，我们约定选取H(xi+1，yi)。

#include<cv.h>#include<highgui.h>#include<cxcore.h>#include<iostream>#include<vector>#include<cmath>using namespace std;using namespace cv;struct line_data{float line_k ; //直线的斜率，当state为0,1时，将k设置为0，只看b。

float line_b ; //直线的与y轴的焦点int line_state ; //表示是否直线的状态竖线为0，横线为1，其他的线均为2 Point2i point_one ; //直线的一个端点Point2i point_two ; //直线的另外一个端点line_data(float k , float b , int state , Point2i one , Point2i two){line_k = k ;line_b = b ;line_state = state ;point_one = one ;point_two = two ;}};vector<Point2i> point;Mat wimg = imread("F:/白底.jpg");void on_mouse(int event, int x, int y, int flages, void * ustc){if(event == CV_EVENT_LBUTTONDOWN)point.push_back(Point2i(x,y));}//Bresenham算法void Bresenham(Point2i p1 , Point2i p2){int x1 = p1.x , y1 = p1.y , x2 = p2.x , y2 = p2.y ; //用于记录当前的点的位置float dx = x2 - x1 , dy = y2 - y1 ;if(0 < dy/dx && dy/dx <= 1){cout<<dy/dx<<endl;if(x1>x2 && y1>y2){int temp_x = x1 , temp_y = y1;x1 = x2;y1 = y2;x2 = temp_x;y2 = temp_y;}dx = x2 - x1;dy = y2 - y1;int num = abs(x2 - x1) ;vector<Point2i> temppos ;int p = 2*abs(dy)-abs(dx);for(int i = 1; i < num ; i++){if(p < 0){x1++;temppos.push_back(Point2i(x1,y1));p = p + 2*abs(dy);}else{x1++;y1++;temppos.push_back(Point2i(x1,y1));p = p + 2*(abs(dy)-abs(dx));}}for(int j = 0 ; j < temppos.size(); j++)circle(wimg,temppos[j],0.5,CV_RGB(0,0,0)); }if(dy/dx > 1){vector<Point2i> temppos ;if(x1>x2 && y1>y2){int temp_x = x1 , temp_y = y1;x1 = x2;y1 = y2;x2 = temp_x;y2 = temp_y;}dx = x2 - x1;dy = y2 - y1;int num = abs(y2 - y1) ;int p = 2*dx-dy;for(int i = 1; i < num ; i++){if(p < 0){y1++;temppos.push_back(Point2i(x1,y1));p = p + 2*dx;}else{x1++;y1++;temppos.push_back(Point2i(x1,y1));p = p + 2*(dx-dy);}}for(int j = 0 ; j < temppos.size(); j++)cout<<temppos[j].x<<" "<<temppos[j].y<<endl;for(int j = 0 ; j < temppos.size(); j++)circle(wimg,temppos[j],0.5,CV_RGB(0,0,0));}if(-1 <= dy/dx && dy/dx < 0){if(x1>x2 && y1<y2){int temp_x = x1 , temp_y = y1;x1 = x2;y1 = y2;x2 = temp_x;y2 = temp_y;}dx = x2 - x1;dy = y2 - y1;vector<Point2i> temppos ;int num = abs(x2 - x1) ;int p = 2*(-dy)-dx;for(int i = 1; i < num ; i++){if(p < 0){x1++;temppos.push_back(Point2i(x1,y1));p = p + 2*(-dy);}else{x1++;y1--;temppos.push_back(Point2i(x1,y1));p = p + 2*((-dy)-dx);}}for(int j = 0 ; j < temppos.size(); j++)circle(wimg,temppos[j],0.5,CV_RGB(0,0,0)); }if(dy/dx < -1){vector<Point2i> temppos ;if(x1>x2 && y1<y2){int temp_x = x1 , temp_y = y1;x1 = x2;y1 = y2;x2 = temp_x;y2 = temp_y;}dx = x2 - x1;dy = y2 - y1;int num = y1 - y2 ;int p = 2*dx-(-dy);for(int i = 1; i < num ; i++){if(p < 0){y1--;temppos.push_back(Point2i(x1,y1));p = p + 2*dx;}else{x1++;y1--;temppos.push_back(Point2i(x1,y1));p = p + 2*(dx-(-dy));}}for(int j = 0 ; j < temppos.size(); j++)cout<<temppos[j].x<<" "<<temppos[j].y<<endl;for(int j = 0 ; j < temppos.size(); j++)circle(wimg,temppos[j],0.5,CV_RGB(0,0,0));}if(p1.x == p2.x){vector<Point2i> temppos ;if(p1.y>p2.y){int temp = p1.y ;p1.y = p2.y;p2.y = temp;}for(int i = 1 ; i < p2.y-p1.y ; i++)temppos.push_back(Point2i(p1.x,p1.y+i));for(int j = 0 ; j < temppos.size(); j++)circle(wimg,temppos[j],0.5,CV_RGB(0,0,0));}if(p1.y == p2.y){vector<Point2i> temppos ;if(p1.x>p2.x){int temp = p1.x ;p1.x = p2.x;p2.x = temp;}for(int i = 1 ; i < p2.x-p1.x ; i++)temppos.push_back(Point2i(p1.x+i,p1.y));for(int j = 0 ; j < temppos.size(); j++)circle(wimg,temppos[j],0.5,CV_RGB(0,0,0));}}void gety_minmax(int &max , int &min ,const vector<Point2i> pos){ max = pos[0].y ;min = pos[0].y ;for(int i = 0 ; i<pos.size() ; i++){if(max < pos[i].y)max = pos[i].y;if(min > pos[i].y)min = pos[i].y ;}}//求直线的方程void getLinefc(vector<Point2i> pos , vector<line_data> &lines){ for(int i = 0 ;i < pos.size() ; i++){if(i == pos.size()-1){if(pos[i].x == pos[0].x)lines.push_back(line_data(0,pos[0].x,0,pos[i],pos[0]));else if(pos[i].y == pos[0].y)lines.push_back(line_data(0,pos[0].y,1,pos[i],pos[0]));elselines.push_back(line_data((float)(pos[i].y-pos[0].y)/(pos[i].x-pos[0].x),(float)(pos[0].y*pos[i].x-pos[0].x*pos[i].y)/(pos[i].x-pos[0].x),2,pos[i],pos[0]));}else{if(pos[i].x == pos[i+1].x)lines.push_back(line_data(0,pos[i].x,0,pos[i],pos[i+1]));else if(pos[i].y == pos[i+1].y)lines.push_back(line_data(0,pos[i].y,1,pos[i],pos[i+1]));elselines.push_back(line_data((float)(pos[i].y-pos[i+1].y)/(pos[i].x-pos[i+1].x),(float)(pos[i+1].y*pos[i].x-pos[i+1].x*pos[i].y)/(pos[i].x-pos[i+1].x),2,pos[i],pos[i+1]));}}}//将输入的X进行排序void paixv(vector<float> &x){for(int i = 0 ; i < x.size()-1 ; i++)for(int j = i+1 ; j < x.size() ; j++){if(x[i] > x[j]){float temp = x[i];x[i] = x[j];x[j] = temp;}}}int main(){int y_min , y_max ; //求y的最大值和最小值vector<line_data> lines ;cvNamedWindow("IMG",CV_WINDOW_AUTOSIZE);setMouseCallback("IMG",on_mouse,0);cout<<"请使用鼠标左键进行坐标点的选取,点击ESC则开始画直线！"<<endl;while(1){char ch = waitKey(100);for(int i = 0 ; i < point.size() ; i++){cout<<point[i].x<<" "<<point[i].y<<endl;circle(wimg,point[i],0.5,CV_RGB(0,0,0));}imshow("IMG",wimg);waitKey(30);if(ch == 27)break;}cout<<"开始画直线!"<<endl;//for(int i = 0 ; i < point.size() ; i++){// circle(wimg,point[i],0.5,CV_RGB(0,0,0));// for(int j = 0 ; j < 20 ; j++)// circle(wimg,Point2f(point[i].x+j,point[i].y+j),0.5,CV_RGB(0,0,0));//}//imshow("IMG",wimg);//Bresenham(Point2i(305,251),Point2i(304,317));//Bresenham(Point2i(243,117),Point2i(173,115));//Bresenham(Point2i(173,115),Point2i(195,81));for(int i = 0 ; i < point.size() ; i++){if(i == point.size()-1)Bresenham(point[i],point[0]);elseBresenham(point[i],point[i+1]);}//cvSmooth(&(IplImage)wimg,&(IplImage)wimg);imshow("IMG",wimg);cvSaveImage( "F:\\作业题\\Bresenham直线段扫描转换\\图片\\直线.jpg",&(IplImage) wimg);waitKey(3000);//获取y的最大最小值gety_minmax(y_max,y_min,point);getLinefc(point,lines);//开始填充for(int i = y_min + 1 ; i < y_max ; i++){vector<float> X ;for(int j = 0 ; j < lines.size() ; j++){if((i>=lines[j].point_one.y &&i<=lines[j].point_two.y)||(i<=lines[j].point_one.y && i>=lines[j].point_two.y)){if(lines[j].line_state == 0)X.push_back(lines[j].line_b);else if(lines[j].line_state == 1){X.push_back(lines[j].point_one.x);X.push_back(lines[j].point_two.x);}elseX.push_back((float)(i-lines[j].line_b)/lines[j].line_k);}}paixv(X);if(X.size()%2 == 0){for(int k = 0 ; k < (X.size()/2) ; k++){for(int l = (int)X[2*k] + 1 ; l < (int)X[2*k+1] ; l++)circle(wimg,Point2i(l,i),0.5,CV_RGB(255,0,0));}}else{vector<float> X2;for(int i = 0 ; i < X.size()-1 ; i++)if((X[i+1]-X[i]>1))X2.push_back(X[i]);X2.push_back(X[X.size()-1]);for(int k = 0 ; k < (X2.size()/2) ; k++){for(int l = (int)X2[2*k] + 1 ; l < (int)X2[2*k+1] ; l++)circle(wimg,Point2i(l,i),0.5,CV_RGB(255,0,0));}X2.clear();}X.clear();}imshow("IMG",wimg);cvSaveImage("F:\\作业题\\Bresenham直线段扫描转换\\图片\\填充.jpg",&(IplImage)wimg);waitKey(0);}。

课程名称计算机图形学实验名称DDA、Bresenham、Midpoint算法画直线一、实验目的及要求（1）理解窗口到视区的变换（2）理解MFC创建工程实现动画的原理(3) 学习MFC类库的概念与结构（4）学习使用VC++编写Win32应用的方法（单文档，多文档，对话框）（5）学习使用MFC的图形编程软件环境：Microsoft studio visual C++ 6.0 MFC硬件：计算机二、实验内容（1）添加代码实现DDA算法画直线（2）添加代码实现Bresenham算法画直线（3）添加代码实现Midpointline画直线(4) 添加代码实现画圆三、实验步骤选择工作环境添加工程名选择程序类型前几步省略全选默认值选择resource-Menu添加不同函数画直线和圆为每个函数建立类向导在fileview中打开source filesview.cpp输入各函数代码并编译运行无误四、实验源码// 直线和圆View.cpp : implementation of the CMyView class//#include "stdafx.h"#include "直线和圆.h"#include "直线和圆Doc.h"#include "直线和圆View.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE[] = __FILE__;#endif///////////////////////////////////////////////////////////////////////////// // CMyViewIMPLEMENT_DYNCREATE(CMyView, CView)BEGIN_MESSAGE_MAP(CMyView, CView)//{{AFX_MSG_MAP(CMyView)ON_COMMAND(ID_DDALINE, OnDdaline)ON_COMMAND(ID_MIDPOINTLINE, OnMidpointline)ON_COMMAND(ID_BRESENHAMLINE, OnBresenhamline)ON_COMMAND(ID_MIDPOINTCIRCLE, OnMidpointcircle)//}}AFX_MSG_MAP// Standard printing commandsON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)END_MESSAGE_MAP()///////////////////////////////////////////////////////////////////////////// // CMyView construction/destructionCMyView::CMyView(){// TODO: add construction code here}CMyView::~CMyView(){}BOOL CMyView::PreCreateWindow(CREATESTRUCT& cs){// TODO: Modify the Window class or styles here by modifying// the CREATESTRUCT csreturn CView::PreCreateWindow(cs);}///////////////////////////////////////////////////////////////////////////// // CMyView drawingvoid CirclePoints(int x,int y,int color ,CDC* pDC ){pDC->SetPixel(x,y,color);pDC->SetPixel(y,x,color);pDC->SetPixel(-x,y,color);pDC->SetPixel(y,-x,color);pDC->SetPixel(x,-y,color);pDC->SetPixel(-y,x,color);pDC->SetPixel(-x,-y,color);pDC->SetPixel(-y,-x,color);}void Midpointcircle(int r,int color,CDC* pDC){int x,y;float d;x=0;y=r;d=1.25-r;CirclePoints(x,y,color,pDC);pDC->SetViewportOrg(200,100);while(x<=y){if(d<0)d+=2*x+3;else{d+=2*(x-y)+5; y--;}x++;CirclePoints(x,y,color,pDC);}}void DDA(int x0,int y0,int x1,int y1,int color,CDC* pDC){int x;float dx,dy,y,k;dx=x1-x0;dy=y1=y0;k=dy/dx;y=y0;for(x=x0;x<=x1;x++){pDC->SetPixel(x,int (y+0.5), color);y=y+k;}}void Bresenhamline(int x0,int y0,int x1,int y1,int color,CDC* pDC) {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(int i=0;i<=dx;i++){pDC->SetPixel(x,y,color);x=x+1;e=e+k;if(e>=0){y++;e=e-1;}}}void Midpointline(int x0,int y0,int x1,int y1,int color,CDC* pDC) {int a,b,d1,d2,d,x,y;a=y0-y1;b=x1-x0;d=2*a+b;d1=2*a;d2=2*(a+b);x=x0;y=y0;pDC->SetPixel(x,y,color);while (x<x1){if(d<0){x++;y++;d+=d2;}else{x++;d+=d1;}pDC->SetPixel(x,y,color);}}void CMyView::OnDraw(CDC* pDC){CMyDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);Midpointcircle(100,RGB(0,168,168),pDC) ;DDA(0,0, 250,300,RGB (255,0,255),pDC);Midpointline(0,0, 500,200,RGB (255,255,0),pDC);Bresenhamline(0,0, 150,600,RGB (168,200,168),pDC);// TODO: add draw code for native data here}///////////////////////////////////////////////////////////////////////////// // CMyView printingBOOL CMyView::OnPreparePrinting(CPrintInfo* pInfo){// default preparationreturn DoPreparePrinting(pInfo);}void CMyView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/){// TODO: add extra initialization before printing}void CMyView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/){// TODO: add cleanup after printing}///////////////////////////////////////////////////////////////////////////// // CMyView diagnostics#ifdef _DEBUGvoid CMyView::AssertValid() const{CView::AssertValid();}void CMyView::Dump(CDumpContext& dc) const{CView::Dump(dc);}CMyDoc* CMyView::GetDocument() // non-debug version is inline{ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CMyDoc)));return (CMyDoc*)m_pDocument;}#endif //_DEBUG///////////////////////////////////////////////////////////////////////////// // CMyView message handlersvoid CMyView::OnDdaline(){// TODO: Add your command handler code here}void CMyView::OnMidpointline(){// TODO: Add your command handler code here}void CMyView::OnBresenhamline(){// TODO: Add your command handler code here}void CMyView::OnMidpointcircle(){// TODO: Add your command handler code here}五.实验结果六. 实验总结分析通过做这个实验学会了使用这个软件，也了解到指针的用法，在做之初由于对指针用法的不熟悉，所以遇到很多问题，从提示中弹出的CDC类，通过对它的学习，我将源码中的drawpixel改写成调用CDC类的pDC指针的用法，再插入pDC->SetViewportOrg(200,100);实现了圆心的移动，实现了对直线的绘制，现在对它的操作已基本掌握了。

Bresenham快速画3D直线算法--------yangzhengyun一、简述前段时间一个学弟正在做一个LED立方，说想做了送给女友。

但他说在画直线，球，波浪等图案时，总是找不到一个很好的算法，导致显示刷屏很慢甚至出现闪屏的现象，问我有没有什么好的算法。

刚好前段时间我也在弄这个，刚开始的时候，我竟然也被“如何画一条3D直线”难倒了，有的人说——画直线还不简单啊，两个点确定一条直线，那是高中数学里面最简单不过的方程式了。

没错，如果是运用高中的方程式来编程，确实很简单，但是……我们先来看一下直线的方程式吧：如我们知道了两个坐标点：A（x1,y1,z1）,B(x2,y2,z2)。

那么直线的方程是：K=(x-x1)/(x2-x1)＝(y-y1)/(y2-y1)＝(z-z1)/(z2-z1)这就不化简了，但是你们有木有发现一个问题。

对，那就是都是进行浮点运算。

我们试想想，如果是用8位的单片机来做的话，速度不知道将会慢到什么程度了。

且，画直线函数基本可以说是底层的驱动函数，如果一个驱动函数都占据了很多的运行时间的话，上层的代码写的再好也是无用的。

为此我们必须找到一个好的办法，避开浮点运算。

即把浮点数据转换成整形数据进行运算，这样速度可以得到很大的提升。

为此，我们首选的就是Bresenham算法了，它引入了一个误差常量e(即后面用到的ey,ez)，e的值为-1/2；在这个运算思路中，我们还是要用到上面的直线方程做为基础。

所以，在看这个代码的时候，你必须先有这点数学的基本知识才行，不然你看的就云里雾里，两眼冒金星了。

下面帖出的是本人经过上网预览大量资料后，写出的三维基于Bresenham算法的画直线函数，二维的就不贴出了，因为二维的在网上有大把的源码，但是三维现成源码就不多了，当然资料还是有的。

里面的算法，和二维算法的思路是一样的，具体的各位学弟们自己去网上查吧，百度一下“Bresenham算法”够你看了，要有多详细有多详细。

Bresenham直线算法与画圆算法（转）在我们内部开发使用的一个工具中，我们需要几乎从0 开始实现一个高效的二维图像渲染引擎。

比较幸运的是，我们只需要画直线、圆以及矩形，其中比较复杂的是画直线和圆。

画直线和圆已经有非常多的成熟的算法了，我们用的是Bresenham的算法。

计算机是如何画直线的？简单来说，如下图所示，真实的直线是连续的，但我们的计算机显示的精度有限，不可能真正显示连续的直线，于是我们用一系列离散化后的点（像素）来近似表现这条直线。

（上图来自于互联网络，《计算机图形学的概念与方法》柳朝阳，郑州大学数学系）接下来的问题就是如何尽可能高效地找到这些离散的点，Bresenham直线算法就是一个非常不错的算法。

Bresenham直线算法是用来描绘由两点所决定的直线的算法，它会算出一条线段在n维光栅上最接近的点。

这个算法只会用到较为快速的整数加法、减法和位元移位，常用于绘制电脑画面中的直线。

是计算机图形学中最先发展出来的算法。

(引自wiki 百科布雷森漢姆直線演算法)这个算法的流程图如下：可以看到，算法其实只考虑了斜率在 0 ~ 1 之间的直线，也就是与 x 轴夹角在 0 度到 45 度的直线。

只要解决了这类直线的画法，其它角度的直线的绘制全部可以通过简单的坐标变换来实现。

下面是一个C 语言实现版本。

1 2 3 4 5 // 交换整数 a 、b 的值inline void swap_int(int *a, int *b) {*a ^= *b;*b ^= *a;*a ^= *b;6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 }// Bresenham's line algorithmvoid draw_line(IMAGE *img, int x1, int y1, int x2, int y2, unsigned long c) {// 参数 c 为颜色值int dx = abs(x2 - x1),dy = abs(y2 - y1),yy = 0;if (dx < dy) {yy = 1;swap_int(&x1, &y1);swap_int(&x2, &y2);swap_int(&dx, &dy);}int ix = (x2 - x1) > 0 ? 1 : -1,iy = (y2 - y1) > 0 ? 1 : -1,cx = x1,cy = y1,n2dy = dy * 2,n2dydx = (dy - dx) * 2,d = dy * 2 - dx;if (yy) { // 如果直线与 x 轴的夹角大于 45 度while (cx != x2) {if (d < 0) {d += n2dy;} else {cy += iy;d += n2dydx;}putpixel(img, cy, cx, c);cx += ix;}} else { // 如果直线与 x 轴的夹角小于 45 度while (cx != x2) {if (d < 0) {d += n2dy;} else {cy += iy;d += n2dydx;}50515253putpixel(img, cx, cy, c);cx += ix;}}}可以看到，在画线的循环中，这个算法只用到了整数的加法，所以可以非常的高效。

易懂的Bresenham布雷森汉姆算法画圆的原理与Python编程实现教程Bresenham 布雷森汉姆算法画圆的原理与编程实现教程注意：Bresenham的圆算法只是中点画圆算法的优化版本。

区别在于Bresenham的算法只使⽤整数算术，⽽中点画圆法仍需要浮点数。

注意：不要因为我提到了中点画圆法你就去先看完再看Bresenham算法，这样是浪费时间。

中点画圆法和Bresenham画圆法只是思想⼀样，但是思路并没有很⼤关联。

所以直接看Bresenham算法就可以。

看下⾯这个图，这就是⼀个像素⼀个像素的画出来的。

我们平常的圆也是⼀个像素⼀个像素的画出来的，你可以试试在“画图”这个软件⾥⾯画⼀个圆然后放⼤很多倍，你会发现就是⼀些像素堆积起来的。

我们看出来圆它是⼀个上下左右都对称，⽽且也是中⼼对称的。

所以我们只⽤画好⼋分之⼀圆弧就可以，其他地⽅通过对称复制过去就好。

看下⾯这幅图，绿线夹住的那部分就是⼋分之⼀圆弧。

注意我们是逆时针画圆的（即从⽔平那个地⽅即(r,0)开始画因为⼀开始我们只知道⽔平位置的像素点该放哪其他地⽅我们都不知道）。

Bresenham 算法画完⼀个点(x,y)后注意x,y都是整数。

他们代表的是x,y⽅向上的第⼏个像素。

，它下⼀步有两个选择(x,y+1),(x-1,y+1)。

也就是说y⼀定增加,但是x要么保持不变要么减⼀（你也可以让x⼀定增加y要么不变要么加⼀，其实差不多的）。

当程序画到粉红⾊那个像素点的时候，程序选择下⼀步要绘制的点为(x-1，y+1)。

当程序画到黄⾊的那个像素点时候，程序选择下⼀步要绘制的点为(x,y+1)。

我们看看粉⾊的那个点的下⼀步是如何抉择的。

Bresenham是根据待选的两个点哪个离圆弧近就下⼀步选哪个。

那它是怎么判断的呢？这两个点⼀定有⼀个在圆弧内⼀个在圆弧外。

到底选哪个？Bresenham的⽅法就是直接计算两个点离圆弧之间的距离，然后判断哪个更近就选哪个。

1.中点Bresenham 算法的原理圆心在原点、半径为R 的圆方程的隐函数表达式为：圆将平面划分成三个区域：对于圆上的点，F(x ，y)＝0；对于圆外的点，F （x ，y ）＞0；对于圆内的点，F （x ，y ）＜0。

事实上，考虑到圆在第一象限内的对称性，本算法可以进一步简化。

用四条对称轴x ＝0，y ＝0， x ＝y,x ＝－y 把圆分成8等份。

只要绘制出第一象限内的1/8圆弧，根据对称性就可绘制出整圆，这称为八分法画圆算法。

假定第一象限内的任意点为P （x,y ），可以顺时针确定另外7个点：P （y ，x ）,P （y ，－x ）,P （x,－ y ）,P （－x ，－y ），P （－y ，－x ），P （－y ，x ），P （－x ，y ）。

2.构造中点偏差判别式从P （xi ，yi ）开始，为了进行下一像素点的选取，需将Pu 和Pd 的中点M （x i+1，y i-0.5）代入隐函数，构造中点偏差判别式：⑴当d<0时，下一步的中点坐标为：M （xi ＋2，yi －0.5）。

下一步中点偏差判别式为：⑵当d ≥0时，下一步的中点坐标为：M （xi ＋2，yi －1.5）。

),(222=-+=R y x y xF )5.0,1(),(-+==i i M M y x F y x F d ⎩⎨⎧≥<=+)0( 1-)0(1d y d y y i i i 2221)5.0()2()5.0,2(R y x y x F d i i i i i --++=-+=+3232)5.0()1(222++=++--++=i i i i i x d x R yx2221)5.1()2()5.1,2(R y x y x F d i i i i i --++=-+=+。

2。

1。

1 生成直线的DDA算法数值微分法即DDA法(Digital Differential Analyzer），是一种基于直线的微分方程来生成直线的方法.一、直线DDA算法描述：设(x1，y1）和(x2，y2）分别为所求直线的起点和终点坐标，由直线的微分方程得= m =直线的斜率(2－1）可通过计算由x方向的增量△x引起y的改变来生成直线:x i+1=x i+△x （2－2）y i+1=y i+△y=y i+△x·m (2－3) 也可通过计算由y方向的增量△y引起x的改变来生成直线：y i+1=y i+△y （2－4）x i+1=x i+△x=x i+△y/m （2－5) 式（2－2）至（2－5）是递推的.二、直线DDA算法思想：选定x2－x1和y2－y1中较大者作为步进方向(假设x2－x1较大），取该方向上的增量为一个象素单位(△x=1)，然后利用式（2－1）计算另一个方向的增量(△y=△x·m=m)。

通过递推公式(2－2）至(2－5），把每次计算出的(x i+1，y i+1)经取整后送到显示器输出，则得到扫描转换后的直线。

之所以取x2－x1和y2－y1中较大者作为步进方向，是考虑沿着线段分布的象素应均匀，这在下图中可看出。

另外，算法实现中还应注意直线的生成方向，以决定Δx及Δy是取正值还是负值。

三、直线DDA算法实现：1、已知直线的两端点坐标：(x1，y1)，（x2，y2)2、已知画线的颜色：color3、计算两个方向的变化量：dx=x2－x1dy=y2－y14、求出两个方向最大变化量的绝对值：steps=max(|dx|，|dy｜)5、计算两个方向的增量（考虑了生成方向)：xin=dx/stepsyin=dy/steps6、设置初始象素坐标：x=x1,y=y17、用循环实现直线的绘制:for(i=1；i〈=steps；i++)｛putpixel(x,y,color)；/＊在（x，y)处,以color色画点＊/x=x+xin;y=y+yin；}五、直线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)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，即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 - (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）.细化工作完成。