精华内容
下载资源
问答
  • 直线DDA算法思想;直线DDA算法实现;直线DDA算法特点;Bresenham算法;Bresenham算法? 记直线与它垂直方向最近的下光栅点的误差为d有d=(y+k)yi且 ? 0d1 ? 当d下一个象素应取右光栅点(xi+1,yi) ? 当d0.5下一个象素应取右...
  • DDA算法和Bresenham算法

    万次阅读 多人点赞 2017-09-04 10:54:02
    DDA算法和Bresenham算法本文结构如下: 1、DDA算法 2、Bresenham算法 3、代码实现核心部分 1、DDA算法DDA算法是计算机图形学中最简单的绘制直线算法。其主要思想是由直线公式y = kx + b推导出来的。 我们已知直线段...

    DDA算法和Bresenham算法

    本文结构如下:

    • 1、DDA算法
    • 2、Bresenham算法
    • 3、代码实现核心部分


    1、DDA算法

    DDA算法是计算机图形学中最简单的绘制直线算法。其主要思想是由直线公式y = kx + b推导出来的。
    我们已知直线段两个端点P0(x0,y0)和P1(x1,y1),就能求出 k 和 b 。

    在k,b均求出的条件下,只要知道一个x值,我们就能计算出一个y值。如果x的步进为1(x每次加1,即x = x +1),那么y的步进就为k+b;同样知道一个y值也能计算出x值,此时y的步进为1,x的步进为(1-b)/k。根据计算出的x值和y值,向下取整,得到坐标(x’,y’),并在(x’,y’)处绘制直线段上的一点。

    为进一步简化计算,通常可令b取0,将起点看作(0,0)。设当前点为(xi, yi)则用DDA算法求解(xi+1,yi+1)的计算公式可以概括为:

    • xi+1 = xi + xStep (1)
    • yi+1 = yi + yStep (2)

    我们一般通过计算 Δx 和 Δy 来确定xStep和yStep:

    • 如果 Δx > Δy ,说明x轴的最大差值大于y轴的最大差值,x轴方向为步进的主方向,xStep = 1,yStep = k;
    • 如果 Δy> Δx,说明y轴的最大差值大于x轴的最大差值,y轴方向为步进的主方向,yStep = 1,xStep = 1 / k。

    根据这个公式,就能通过(xi,yi)迭代计算出(xi+1、yi+1),然后在坐标系中绘制计算出的(x,y)坐标点。


    2、Bresenham算法

    Bresenham算法也是一种计算机图形学中常见的绘制直线的算法,其本质思想也是步进的思想,但由于避免了浮点运算,相当于DDA算法的一种改进算法。

    设直线的斜率为k,当|k| <=1时,x方向为主步进方向;当|k| >1时,y方向为主步进方向。现以|k| <1时为例,推导Bresenham算法的原理。

    这里写图片描述

    Bresenham算法直线绘制示意图
    图片来自:http://st251256589.blog.163.com/blog/static/16487644920114112817666/

    图中绘制了一条直线,蓝色点表示该直线上的点,红色点表示光栅下绘制的点。
    假设当前点是(xi,yi)
    - 如果int(yi+0.5) = yi,则在点(xi, round(yi))处绘制.
    - 如果int(yi+0.5) = yi + 1,则在点(xi, round(yi)+1)处绘制。

    上述逻辑可简述为:当x方向是主要步进方向时,以每一小格的中点为界,如果当前的yi在中点(图中红色短线)下方,则y取round(yi); 如果当前的yi在中点上方,则y取rund(yi)+1。

    引用部分:现考虑这种方法的误差,因为直线的起始点在像素中心,所以误差项d的初值d0=0。x下标每增加1,d的值相应递增。直线的斜率值k,即d=d+k。一旦d≥1,就把它减去1,这样保证d在0、1之间。当d≥0.5时,最接近于当前像素的右上方像素(x+1,y+1)而当d<0.5时,更接近于右方像素(x+1,y)为方便计算,令e=d-0.5,e的初值为-0.5,增量为k。当e≥0时,取当前像素(xi,yi)的右上方像素(x+1,y+1),而当e<0时,更接近于右方像素(x+1,y)可以改用整数以避免除法。由于算法中只用到误差项的符号,因此可作如下替换:
    e1 = 2e * Δx。

    参考:
    http://blog.csdn.net/xdg_blog/article/details/52848891
    http://www.cnblogs.com/weiweishuo/archive/2013/03/11/2954443.html


    3、代码实现

    1、DDA算法

    void CGView::DrawDDALine(int startx,int starty, int endx, int endy)  
    {   
        CDC* pDC = GetDC();
        DrawStandLine(pDC);//绘制标准直线
        int x0 = startx; 
        int y0 = starty ;
        int x1 = endx; 
        int y1 = endy; 
        int color=RGB(255,0,0);
        int x; 
        float dx,dy,y,k;
        dx = x1-x0, dy = y1-y0;
        k = dy / dx,y = y0;
        int x2 = startx; 
        int y2 = endx;
        for(x = x0;x <= x1;x++)
        {   //(20,360)是坐标轴的起点
            x2 = 20 + x * 30; //30是坐标轴的单位刻度
            pDC->Ellipse( x2 - 5, y2 - 5, x2 + 5, y2 + 5 );
            y = k * x + k;
            y = (int)(y+0.5);
            y2 = 360 - y * 30;
        }
    }
    

    2、Bresenham算法

    void CGView::DrawBresenham(int startx,int starty, int endx, int endy)
    {
        CDC* pDC = GetDC();
        DrawStandLine(pDC);//绘制标准直线
        int x0, y0, x1, y1;
        x0 = startx; 
        y0 =starty;
        x1 = endx; 
        y1 = endy;
        int x, y, dx, dy;  
        dx = x1-x0, dy = y1- y0; 
        x = x0;
        y = y0;
        double k = dy / dx;
        //如果 >1,则y方向是主要步进方向,需要转换坐标系方向
        if(abs(k)>1){
           Swap(startx,starty,endx,endy);
        }
        int e = -dx; int x2 = 20, y2 = 360; //(20,360)是坐标轴的起点
        for (int x=x0; x<=x1; x++)
        { 
            pDC->Ellipse( x2 - 5, y2 - 5, x2 + 5, y2 + 5 );
            x2 += 30;
            e += 2 * dy;
            if (e > 0)
            { 
                y++;
                y2 -= 30; //30是坐标轴的单位刻度
                e -= 2*dx;
            }
        }
    }
    

    两种算法的运行结果情况如下图所示,从图中可已看出,两种算法都能绘制出直线段,但是在细节稍有不同,当x=4时,DDA算法的y值为3,而Bresenham的算法y为2。在不过从效率上看,由于Bresenham避免了浮点运算,所以效率更高。

    这里写图片描述

    本文参考了网上的资料,包括图片、文字等。在文中均给出了链接。时间太久了,代码已经找不到出处了。如有疏漏,请指出。

    这里写图片描述

    展开全文
  • 2、 依据算法思想,绘制程序流程图; 3、 设计程序界面,要求操作方便; 4、 用C/C++语言编写源程序并调试、执行; 5、 分析实验结果 6、 对程序设计过程中出现的问题进行分析与总结; 7、 打印源程序或把源程序以...
  • 通过EasyX实现DDA算法

    2020-04-20 18:30:09
    DDA算法 DDA算法是计算机图形学中最简单的绘制直线算法。其主要思想是由直线公式y = kx + b推导出来的。 我们已知直线段两个端点P0(x0,y0)和P1(x1,y1),就能求出 k 和 b 。 在k,b均求出的条件下,只要知道一个x值...

    DDA算法

    DDA算法是计算机图形学中最简单的绘制直线算法。其主要思想是由直线公式y = kx + b推导出来的。
    我们已知直线段两个端点P0(x0,y0)和P1(x1,y1),就能求出 k 和 b 。

    在k,b均求出的条件下,只要知道一个x值,我们就能计算出一个y值。如果x的步进为1(x每次加1,即x = x +1),那么y的步进就为k+b;同样知道一个y值也能计算出x值,此时y的步进为1,x的步进为(1-b)/k。根据计算出的x值和y值,向下取整,得到坐标(x’,y’),并在(x’,y’)处绘制直线段上的一点。

    为进一步简化计算,通常可令b取0,将起点看作(0,0)。设当前点为(xi, yi)则用DDA算法求解(xi+1,yi+1)的计算公式可以概括为:

    • xi+1 = xi + xStep (1)
    • yi+1 = yi + yStep (2)

    我们一般通过计算 Δx 和 Δy 来确定xStep和yStep:

    • 如果 Δx > Δy ,说明x轴的最大差值大于y轴的最大差值,x轴方向为步进的主方向,xStep = 1,yStep = k;
    • 如果 Δy> Δx,说明y轴的最大差值大于x轴的最大差值,y轴方向为步进的主方向,yStep = 1,xStep = 1 / k。

    根据这个公式,就能通过(xi,yi)迭代计算出(xi+1、yi+1),然后在坐标系中绘制计算出的(x,y)坐标点。

    代码实现

    通过EasyX图形库实现,代码如下:

    #include <graphics.h>
    #include <conio.h>
    
    // 四舍五入
    int Round(float x)
    {
    	return (int)(x < 0 ? x - 0.5 : x + 0.5);
    }
    
    // 使用 DDA 算法画任意斜率的直线(包括起始点,不包括终止点)
    void Line_DDA(int x1, int y1, int x2, int y2, int color)
    {
    	float x, y;		// 当前坐标点
    	float cx, cy;	// x、y 方向上的增量
    
    	int steps = abs(x2 - x1) > abs(y2 - y1) ? abs(x2 - x1) : abs(y2 - y1);
    
    	x = (float)x1;
    	y = (float)y1;
    	cx = (float)(x2 - x1) / steps;
    	cy = (float)(y2 - y1) / steps;
    
    	for (int i = 0; i < steps; i++)
    	{
    		putpixel(Round(x), Round(y), color);	// 在坐标 (x, y) 处画一个 color 颜色的点
    		x += cx;
    		y += cy;
    	}
    }
    
    // 主函数
    int main()
    {
    	initgraph(640, 480);
    
    	// 测试画线
    	Line_DDA(100, 1, 1, 478, GREEN);
    	Line_DDA(1, 478, 638, 1, GREEN);
    
    	// 按任意键退出
    	_getch();
    	closegraph();
            return 0;
    }

    结果:

     

     

    参考资料:

    https://blog.csdn.net/u010429424/article/details/77834046

    https://codebus.cn/yangw/a/dda-line-algorithm

     

     

    展开全文
  • 基于Bresenham和DDA算法画线段

    千次阅读 2013-08-15 17:13:13
    直线:y=kx+b 为了将他在显示屏上显示出来,我们需要为相应的点赋值,那么考虑到计算机...DDA算法思想是 1.判断直线是近x轴线段,还是近y轴线段 2.求出delt_x,delt_y ,以较大值为总步长,每次以此为标准,步进,然

    直线:y=kx+b 为了将他在显示屏上显示出来,我们需要为相应的点赋值,那么考虑到计算机的乘法执行效率,我们肯定不会选择用Y=kx+b这个表达式求值,然后进行画线段。

    我们应当是将它转化为加法运算。

    下面提供两种常见的算法:

    方法1:DDA算法

    DDA算法的思想是

    1.判断直线是近x轴线段,还是近y轴线段

    2.求出delt_x,delt_y ,以较大值为总步长,每次以此为标准,步进,然后求另一个值的增长值.

    实现:

    void LCD_DrawLine(u16 x1, u16 y1, u16 x2, u16 y2)
    {
        u16 t; 
    	int xerr=0,yerr=0,delta_x,delta_y,distance; 
    	int incx,incy,uRow,uCol; 
    
    	delta_x=x2-x1; //计算坐标增量 
    	delta_y=y2-y1; 
    	uRow=x1; 
    	uCol=y1; 
    	if(delta_x>0)incx=1; //设置单步方向 
    	else if(delta_x==0)incx=0;//垂直线 
    	else {incx=-1;delta_x=-delta_x;} 
    	if(delta_y>0)incy=1; 
    	else if(delta_y==0)incy=0;//水平线 
    	else{incy=-1;delta_y=-delta_y;} 
    	
    	if( delta_x>delta_y)distance=delta_x; //选取基本增量坐标轴 
    	else distance=delta_y; 
    	for(t=0;t<=distance+1;t++ )//画线输出 
    	{  
    		LCD_DrawPoint(uRow,uCol);//画点 
    		xerr+=delta_x ; 
    		yerr+=delta_y ; 
    		if(xerr>distance) 
    		{ 
    			xerr-=distance; 
    			uRow+=incx; 
    		} 
    		if(yerr>distance) 
    		{ 
    			yerr-=distance; 
    			uCol+=incy; 
    		} 
    	}  
    } 

    方法二:Bresenham算法实现

    算法思想:

    dBresenham算法只要求做加法和乘二运算

    1.      核心要解决的是下个点选用y+1,还是y

    2.      基本要求不能有乘法运算

    3.      表达式为   y=mx+b;起始点为(x,y)

    4.      y(k+1)=m(x+1)+b;  d1=y(k+1)-y=m(x+1)+b-y  ;d2=y+1- y(k+1)=y+1-m(x+1)-b;
    所以判断下个点y的坐标就演变成求d1,d2的差值

    d1-d2>0 --------------à(x+1,y+1)

    d1-d2<0-------------à(x+1,y)

    d1-d2= 2m(x+1)-2y+2b-1

    delt(x)=x2-x1>0

     还是含有乘法运算,所以继续化简

     p=delt(x)*(d1-d2)=2delt(y)*(x+1)-2delt(x)*y-(2b-1)*delt(x)=2*delt(y)*x-2delt(x)*y+c【c=2*delt(y)+delt(x)(2b-1)】

    p(X(i+1))-p(X(i))=2delt(y)-2delt(x)(Y(i+1)-Y(i))  


    p(i)>0 Y(i+1)-Y(i)=1; else =0;

    最后得到p1=2delt(y)-delt(x);

    p(X(i+1))= p(X(i))+2delt(y)-2delt(x)(Y(i+1)-Y(i))

    这样就求出了p的值

    代码实现:

    void LCD_DrawLine(u16 x1, u16 y1,u16 x2,u16 y2)
    {
    int delta_x,delta_y,x,y,inc1,inc2;
    u8 p;
    
    delta_x=fabs(x1-x2);
    delta_y=fabs(y1-y2);
    p=2*delta_y-delta_x;
    inc1=2*(delta_y-delta_x);
    inc2=2*delta_y;
    //判断方向
    if(x10)
    {
    p+=inc1;
    y++;
    }
    else
    p+=inc2;
    LCD_DrawPoint(x,y);
    }
    }


    说明:上述代码实现均是基于stm32处理器,tftLCD2.8寸屏上实现的


    展开全文
  •  这是我今天在图像处理学习中遇到的问题,霍夫变换采用的概率霍夫变换,所以拟合得到的直线信息其实是直线的两个端点的坐标,这样一个比较直接的思路就是利用DDA算法来获取. 一.算法简介  DDA算法是计算机图形学中...

    图片霍夫变换拟合得到直线后,怎样获得直线上的像素点坐标?

      这是我今天在图像处理学习中遇到的问题,霍夫变换采用的概率霍夫变换,所以拟合得到的直线信息其实是直线的两个端点的坐标,这样一个比较直接的思路就是利用DDA算法来获取.

    一.算法简介

      DDA算法是计算机图形学中最简单的绘制直线算法。其主要思想是由直线公式y = kx + b推导出来的。 
      我们已知直线段两个端点P0(x0,y0)和P1(x1,y1),就能求出 k 和 b 。

      在k,b均求出的条件下,只要知道一个x值,我们就能计算出一个y值。如果x的步进为1(x每次加1,即x = x +1),那么y的步进就为k+b;同样知道一个y值也能计算出x值,此时y的步进为1,x的步进为(1-b)/k。根据计算出的x值和y值,向下取整,得到坐标(x’,y’),并在(x’,y’)处绘制直线段上的一点。

      为进一步简化计算,通常可令b取0,将起点看作(0,0)。设当前点为(xi, yi)则用DDA算法求解(xi+1,yi+1)的计算公式可以概括为:

        xi+1 = xi + xStep (1)
        yi+1 = yi + yStep (2)
      我们一般通过计算 Δx 和 Δy 来确定xStep和yStep:

      如果 Δx > Δy,说明x轴的最大差值大于y轴的最大差值,x轴方向为步进的主方向,xStep = 1,yStep = k;
      如果 Δy > Δx,说明y轴的最大差值大于x轴的最大差值,y轴方向为步进的主方向,yStep = 1,xStep = 1 / k。
      根据这个公式,就能通过(xi,yi)迭代计算出(xi+1、yi+1),然后在坐标系中绘制计算出的(x,y)坐标点。

    二.代码展示

      下面是代码,假设(x1, y1),(x2, y2)为直线的两个端点坐标:

    xDis = x2 - x1  #x的增量
    yDis = y2 - y1  #y的增量
    if(abs(xDis) > abs(yDis)):
        maxstep = abs(xDis)
    else:
        maxstep = abs(yDis)
    xUnitstep = xDis/maxstep  #x每步骤增量
    yUnitstep = yDis/maxstep  #y的每步增量
    x = x1
    y = y1
    for k in range(maxstep):
        x = x + xUnitstep
        y = y + yUnitstep
        print("x: %d, y:%d" % (x, y))

     

    展开全文
  • DDA(数值微分法)基于直线微分方程生成直线。 点xi,yi满足直线方程yi=kxi+b...算法基本思想: 选择平缓的一端(即x2-x1和y2-y1的较大者)作为自变量,每次增加一个单位,计算因变量的值。 具体代码如下: void ...
  • 算法思想 DDA 设直线两端点为:起点A(x0,y0);终点为B(x1,y1)。 则直线的斜率和方程为: 下面分为两种情况考虑:当斜率小于等于1的时候,x每次增加1,y最多增加1。 而当斜率大于1的时候,让y每次递增1,x每次递增...
  • VC实现生成BMP文件(DDA算法画直线)

    千次阅读 2006-03-15 20:33:00
    最近老师布置一道作业,用DDA算法画出直线,本人... 实验内容用DDA算法思想画出一条线段.本程序开发于VC.Net平台,基于MFC框架,实现了根据起始坐标(有平面坐标)来画出线段、并且能保存客户区图片位未压缩BMP文件. 二.
  • 基本思想: 已知过端点P0(x0,y0),P1(x1,y1)的直线段L:y=kx+b;斜率为K=(y1-y0)/(x1-x0);从x=x0开始,步长=1(个像素),计算相应的坐标y=kx+b;取像素点(x,round(y))作为当前点的坐标。(round()为取整函数...
  •  这是我今天在图像处理学习中遇到的问题,霍夫变换采用的概率霍夫变换,所以拟合得到的直线信息其实是直线的两个端点的坐标,这样一个比较直接的思路就是利用DDA算法来获取. 一.算法简介  DDA算法是计算机图形学中...
  • 说白了就是在黑色的背景下画出一条白色的线,当然画出一条线应该说方法有很多,今天说一下DDA算法吧。(PS:上网查找资料看到了各种版本的思想,代码,今天可以总结一下了) 实验环境: WINDOWS系统,VC6.0++及...
  • 小白谈计算机图形学(一)如何划线引言如何画线基本思想数值微分法(DDA算法)数值微分基本思路数值微分改进中点画线法中点画线引言中点画线改进Bresenham画线法Bresenham基本思路Bresenham画线改进小结 引言 大家好...
  • 数值微分算法(DDA画线算法)

    千次阅读 2012-10-29 11:27:23
    基本思想  已知过端点 P0 (x0 ,y0 ),P1 (x1 ,y1 ) 的直线段L:y=kx+b  直线斜率为 k=(y1-y0)/(x1-x0)  从x的左端点x0开始,向x右端点步进。步长=1(个象素),计算相应的y坐标 y=kx+b;取象素点(x, ...
  • 1.DDA算法 DDA(Digital Differential Analyer):数字微分法 DDA算法思想:增量思想 公式推导: 效率:采用了浮点加法和浮点显示是需要取整 代码: void lineDDA(int x0, int y0, int x1, int y1, int ...
  • 直线生成算法

    2012-03-26 20:48:07
    直线生成算法:在光栅系统中绘制直线段,需要采用直线生成算法,常用的有DDA算法、Bresenham算法等。 Ø DDA直线生成算法是一种使用微分方程生成直线的算法,又称作数值微分法。该算法的基本思想是:根据斜率确定...
  • 直线、圆环绘制算法

    2020-11-29 15:58:55
    DDA算法主要是利用了增量的思想,通过同时对x和y各增加一个小增量,计算下一步的x和y值。 根据上式可知△x=1时,x每递增1,y就递增k,所以只需要对x和y不断递增就可以得到下一点的函数值,这样避免了对每一个像素都...
  • 图形学各种算法代码

    千次阅读 2015-01-31 21:31:14
    1. DDA算法算法思想参考百度百科: http://baike.baidu.com/link?url=bKEk1Bmu6YO7gdPuQpXokbS2eDV8-X5UQaObYeg1NWyHvLS82d5RBZWfdr-tkHrVKfQWgdbciVf_BLNGh6jsFK 2. 各种算法实现: 2.1 画直线算
  • 计算机图形学DDA

    2020-06-25 09:50:52
    DDA算法是一个经典的画直线算法,也是直线生成算法中最简单的一种。它的原理比较简单,是一种数值微分的方法,这也是本系统中第一个接触增量思想的算法。它是利用直线最基本的格式,斜截式:y=kx+b来实现的。我们都...
  • 中点画线法的建立基础是数值微分画线法(DDA),其作为改进算法,沿用了DDA算法的增量思想,针对影响DDA算法效率的两点:(1)采用了浮点加法(2)浮点数在显示输出时需要取整;进行了改进,即中点画线法直接采用了...
  • Bresenham算法

    千次阅读 2015-11-21 23:08:44
    算法核心思想:已知当前点坐标及曲(直)线方程,递推下一个(x+1)点的y坐标(或者(y+1)点的x坐标)。抛弃使用三角函数计算坐标,提高数据重用率。1.DDA画线算法 核心:直线方程y=k*x+b; 前一个坐标和下一个...
  • Bresenham算法也是一种计算机图形学中常见的绘制直线的算法,其本质思想也是步进的思想,但由于避免了浮点运算,相当于DDA算法的一种改进算法。 源代码展示: #include #include #include<math.h> #...
  • 采用增量思想DDA算法,直观、易实现,每计算一个象素坐标,只需计算一个加法。 (1)改进效率。这个算法每步只做一个加法,能否再提高效率? 一般情况下k与y都是小数,而且每一步运算都要对y进行四舍五入后取整...
  • 图形学算法--Bresenham画直线

    千次阅读 2012-03-12 21:43:26
    上次写了一下DDA直线算法的过程和实现,但DDA算法也有一些缺点:  主要它涉及到了实数的除法运算,效率不太高。  今天,我介绍另外一种画直线的算法:Bresenham算法(中点画线)  Bresenham算法的基本思想就是...
  • 一、功能要求 实现一个图形函数库,具有绘制直线段、任意...绘制直线使用的是DDA算法(数字微分分析法),该算法的核心思想是依据直线的微分方程依次确定描述直线的各个像素点。 例如,已知直线的两个端点为(x1,y1...
  • 直线的生成的两种算法

    千次阅读 2018-04-10 00:38:33
    1 DDA算法(数字微分分析法):1.1算法思想:从直线段的起点像素出发,依据直线的微分方程确定描述直线的各个像素点1.2 算法原理:直线的起点(xs,ys)终点:(xe,ye)变化量为cx=xe-xs,cy=ye-ys;我们将变化时间设为ct.则有: x...

空空如也

空空如也

1 2 3
收藏数 50
精华内容 20
关键字:

dda算法算法思想