中点画线算法_中点画线算法例题 - CSDN
精华内容
参与话题
  • 中点画线算法(计算机图形学)

    万次阅读 2016-01-25 16:53:49
    中点bresenham画线算法基本思路 //假设该线段位于第一象限内,且斜率为0~1之间(决定了主方向为x),设起点为(x0,y0),终点为(xend,yend) //根据对称性,可推导致全象限内线段 //线段为y=kx+1 //相邻的下一点...

    0.画线算法

    0.DDA(digital differential analyzer)

    A.基本原理

    画线时,会给出两个端点(x0,y0),(xend,yend)据此计算出斜率m,然后


    从(x0,y0)开始x方向按1递增,y值按上计算,直至xi=xend。这里之所以使用上式,而不直接使用y=m*x+b计算,应该是因为上式少一次乘法运算速度更快吧。计算得到的y若不是整数,则四舍五入处理。

    另外:

    当m小于1时,x为主变量,x加1递增,y按上式计算;当m大于1时,y为主变量,y加1递增,x按上式计算。不知道为什么要这么做,应该是为了统一规则吧。

    B.伪码

    void lineDDA(int x0,int y0,int xend,int yend)
    {
    	int dx=xend-x0;
    	int dy=yend-y0;
    	int x=x0;
    	int y=y0;
    	int step=abs(dx)>abs(dy)?abs(dx):abs(dy);
    	float incrementx=(float)dx/step;
    	float incrementy=(float)dy/step;
    	SetPixel(round(x),round(y));
    	for(int i=0;i<step;i++)
    	{
    		x+=incrementx;
    	 	y+=incrementy;
    		SetPixel(round(x),round(y));
    	}
    }

    C.缺陷

    由于上一个点的坐标值会影响到下一个点的坐标值,不断的对坐标值取整(即使是四舍五入)也会使得整条线偏离理想直线(这个误差是积累的)。另外四舍五入取整比较耗时(这个不知如何证明)。

    1.中点bresenham

    相对于DDA而言:同样取值是四舍五入(理想直线点大于中点取大的,小于中点取小的),不同的是决策的式子不再是round函数,这样计算耗时相对较小;还有就是中点bresenham的每个点是理想直线点与中点比较取得近似值,它的误差不会积累,而DDA上点的值会影响到下点的值,误差会积累。

    A.基本原理

    B.中点bresenham画线算法基本思路

    //假设该线段位于第一象限内,且斜率为0~1之间(决定了主方向为x),设起点为(x0,y0),终点为(xend,yend) 
    //根据对称性,可推导致全象限内线段
    //线段为y=kx+1 
    //相邻的下一点坐标不是(xi+1,yi+1),就是(xi+1,yi) 
    1.画起点(x0,y0).
    2.准备画下一个点。横坐标增1,判断如果到达终点,则完成。否则: 
    	2.1直线(y=kx+1) 与直线(x=xi+1)的交点A (xi+1,k*(xi+1)+1)的纵坐标大于M (xi+1,yi+0.5)的纵坐标,则下一点为(xi+1,yi+1)
    	2.2否则下一点为(xi+1,yi) 
    3.画点
    4.跳回第2步
    5.结束 
    
    

    C.递推

    D.伪码

    void Bresenham(Node vstart,Node vend)
    {
    	double k=(vend.y-vstart.y)/(vend.x-vstart.x);
    	double d=k-0.5;//赋初值
    	int x=vstart.x;
    	int y=vstart.y;
    	DrawPixel(x,y);//画点 
    	while(x!=vend.x)
    	{
    		x++;
    		if(d>=0)//A-M>0,交点距离上面的点更近,A-M=0时,当然希望更快的接近终点,故选上面的点 
    		{
    			y++;//选择上面的点
    			d=d+k-1//下下个要画的判断依据。点A与终点M的差距 
    		} 
    		else//A-M<0,交点距离下面的点更近 
    		{
    			d=d+k;
    		} 
    		DrawPixel(x,y);
    	}
    }
    
    
    2.并行画线算法

    np个处理器,将原本的直线分成np段,每段执行bresenham画线算法。其中每段的段长(除却最后一段):(xend-x0+(np-1))/np,此处之所以要加上(np-1),是为了保证,除完之后的  段长 * 段数 <= xend - x0。根据段长计算出每段的起终点,然后就可以按照bresenham算法画线了。

    1.圆生成算法

    0.基本画法

    绘制等距点,等距点之间以线段链接,逼近正圆。通常会使用圆的对称性来减少三角函数的使用,用以加快绘制速度。

    1.中点画圆算法

    与基本画法的区别:可以采用增量方式判断和求得点坐标,无需使用三角函数和四舍五入的round函数,增加了计算速度。

    A.基本思路

    B.步骤

    //输入半径r和圆心(xc,yc),并得到圆周上的第一个点(x0,y0)=(0,r)(先计算圆心为0,0的八分之一的圆弧的点,再利用对称性计算其他八点,再移过去)
    //计算决策参数初始值为 p0=5/4-r
    //在每一个xk为止,从k=0开始测试,
    //若pk<0,则圆心在0,0的圆的下一个点为(x[k+1],y[k]),p[k+1]=p[k]+2x[k+1]+1
    //否则,下一个点为(x[k+1],y[k]-1),并且p[k+1]=p[k]+2x[k+1]+1-2y[k+1],其中x[k+1]=x[k]+1,y[k+1]=y[k]-1
    //利用计算其他八个圆弧的对称点
    //移到圆心(xc,yc)的圆上
    //重复循环,直至x>=y 
    C.各项证明

    2.椭圆生成算法

    A.椭圆特性


    B.基本原理

    基本原理跟生成圆一样,都是想要生成一个可以增量的决策式,希望通过迭代加减乘除来代替三角运算或者开根号等复杂运算,同时希望这个加减乘除又不会积累误差,导致图形严重偏离理想椭圆

    中点的画法,本质还是四舍五入,做法和生成圆一样,生成函数判别式f,通过f的值的符号判断取哪个点,自增1的那个变量由斜率k来判断(其实只要同一形式就行?)。

    C.并行曲线画法

    和并行直线画法相似,不再赘述

    3..以上画线算法学习心得

    1.以斜率k为判断决定一边自增1的变量(x或y)。

    2.寻找可以叠加的判断式(决策式)用以代替四舍五入函数来选择点(增加运算速度)。一般  f  = 现实点(x(或y)自增1,y(或x)先维持不动)-  理想点,或其的其他变形(如椭圆和圆的决策式)。

    3.得出位置。


    展开全文
  • 在编写的FDGK/GUI决定采用中点画线算法绘制直线。故先研究了一下算法。 中点画线算法的原则是:如下图所示,但斜率K<1时,选定一个点之后,再计算中点M。如果M>0,这线更靠近E点,下一点选择为E点。反之选择NE...

    在编写的FDGK/GUI决定采用中点画线算法绘制直线。故先研究了一下算法。

    中点画线算法的原则是:如下图所示,但斜率K<1时,选定一个点之后,再计算中点M。如果M>0,这线更靠近E点,下一点选择为E点。反之选择NE点。

    首先:f(x,y) = ax+by+c=0,
    且  y = dy/dx *x + B, 
    so : f(x,y) = dy*x-dx*y+Bdx =0
    so: a = dy, b = -dx, c = Bdx.
     
    假设,已经选定P点,应用中点法则选择下一点是,我们只要计算f(x+1,y+1/2),并考察是正数还是负数。
    我们定义d=f(x+1,y+1/2)=a(x+1)+b(y+1/2)+c.这样,对于d>0,d<0,我们只要选择NE点和E点就可以了。
    这边假设选定为E点,那么中点M的位置怎么变化和d的值如何变化呢?显然M就沿着x轴递增一步。
    此时:d1 = f(x+2,y+1/2)
    从d1中减去d,可以得到一个增量差。d1= a = dy。
    同理:如果选定下一点为NE点,d2 = a+b = dy-dx。
     
    基于上面的讨论,增量的中点技术可以概括为:在每一步,我们根据上一步所得到的增量的符号去选择下一个像素点。然后根据说选择的像素,判定变量增加相应的增量差d1或d2。
    对于初始值,我们选择第一个端点为(x0,y0)。则M为(x0+1,y+1/2).
    f(x0+1,y0+1/2) = f(x0,y0)+a+b/2. 
    故: d0 = a+b/2 = dy - dx/2
    为去掉d0中的小数,我们对d0进行放大。(在方程两边同乘于2)
    d0 = 2*dy - dx
    d1 = 2*dy
    d2 = 2*(dy-dx)
     
    所以,在斜率小于1的情况下,中点画线的算法实现如下:
    void GUI_DrawLine(uint16 x0,uint16 y0,uint16 x1,uint16 y1,uint16 color)
    {
        uint16 dx,dy,incrE,incrNE,x,y,d;
        
        dx = x1 - x0;
        dy = y1 - y0;
        d = (dy<<1) - dx;
        incrE = dy<<1;
        incrNE = (dy - dx)<<1;
        
        x = x0;
        y = y0;
        GUI_DrawPoint(x,y,color);
        while(x<x1)
        {
            if(d > 0)
            {
                d += incrNE;
                x++;
                y++;
            }
            else
            {
                d += incrE;
                x++;
            }
            
            GUI_DrawPoint(x,y,color);
        }
    }
    
    以上只是在K<1的情况下即在(1)中成立。那其他情况怎么办呢?
    我的处理方法是这样的:
    1、把3,4,5,6情况下的两个端点调换,把它变换成1,2,7,8的情况,这样我们要考虑的情况就少一半。
    2、1和8,2和7关于x轴对称。1和2关于y=x对称。这样,我们就可以把1情况下的算法,移植到其他情况下。
     
    改进后的算法如下:
    
    void swap(uint16 *x0,uint16 *y0,uint16 *x1,uint16 *y1)
    {
        uint16 x,y;
            
        x = *x1;
        *x1 = *x0;
        *x0 = x;
            
        y = *y1;
        *y1 = *y0;
        *y0 = y;    
    }
     
    void GUI_DrawLine(uint16 x0,uint16 y0,uint16 x1,uint16 y1,uint16 color)
    {
        int16 dx,dy,d;
        uint16 x,y;
        
        if( x0 > x1)               /* 保证x0<x1,即x0为x1左边的点。*/
        {
            swap(&x0,&y0,&x1,&y1);  
        }
        
        dx = x1 - x0;
        dy = y1 - y0;
        
        if( dx == 0)                /* 斜率为无穷大,画直竖线 */
        {
            LCD_DrawVLine(x0,y0,y1,color);
            return;
        }
        if( dy == 0)                /*斜率为零,画水平线 */
        {
            LCD_DrawHLine(x0,y0,x1,color);
            return;
        }
        
        x = x0;
        y = y0;
        GUI_DrawPoint(x,y,color);
        
        if((dx>=dy)&&(dy>0))           /* when 0<k<=1 */
        {
            d = (dy*2) - dx;
            while(x<x1)
            {
                if(d > 0)
                {
                    d += (dy - dx)*2;       /* 选择NE点 */
                    x++;
                    y++;
                }
                else
                {
                    d += dy*2;        /* 选择N点 */
                    x++;
                }
            
                GUI_DrawPoint(x,y,color);
            }
            return;
        }
        
        if( (dy>dx)&&(dy>0))           /* when k>1 */
        {
            d = dy - (dx*2);
            while(y<y1)
            {
                if(d < 0)
                {
                    d += (dy - dx)*2; /* 选择 NE 点 */
                    x++;
                    y++;
                }
                else
                {
                    d += (-dx)*2;     /* 选择N点 */
                    y++;
                }
            
                GUI_DrawPoint(x,y,color);
            }
            return;
        }
        
        if((dx>=ABS(dy))&&(dy<0))           /* when -1=<k<0 */
        {
            d = (dy*2) + dx;           /* d = 2a-b */
            while(x<x1)
            {
                if(d < 0)
                {
                    d += (dy+dx) * 2;   /* 选择SE点 */
                    x++;
                    y--;
                }
                else
                {
                    d += dy*2;          /* 选择S点 */
                    x++;
                }
            
                GUI_DrawPoint(x,y,color);
            }
            return;
        }
        
        if( (ABS(dy)>dx)&&(dy<0))           /* when k<-1 */
        {
            d = dy + (dx*2);          /* d = a - 2b */
            while(y>y1)
            {
                if(d > 0)
                {
                    d += (dy + dx)*2; /* 选择 SE 点 */
                    x++;
                    y--;
                }
                else
                {
                    d += (dx)*2;     /* 选择S点 */
                    y--;
                }
            
                GUI_DrawPoint(x,y,color);
            }
            return;
        }
    }
    

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    展开全文
  • 图形学--(中点画线法+Bresenham画线算法)  原文地址:https://www.cnblogs.com/llsq/p/7506597.html  编程环境:codeblocks+EGE库  用到的函数:putpixel(int x1,int y1,int color) 用某种颜色打亮一个坐标...
    
    

       原文地址:https://www.cnblogs.com/llsq/p/7506597.html

         编程环境:codeblocks+EGE库

         用到的函数:putpixel(int x1,int y1,int color)  用某种颜色打亮一个坐标点。

     这俩种算法都是用来在计算机上画一条直线的,那么我们为什么不直接用直线方程分别带点再打亮呢,这是因为,计算机中每个坐标点都是整数,而直线是由一个个像素点组合而成的,那么,直接将坐标点再进行四舍五入整数化就好了啊,的确,这是一种方法,但计算机中进行浮点数的四舍五入会使运算效率变差,因此真正画直线时是用到上边这俩种方法的。

    1、中点画线法

      只考虑当直线的斜率|k|<1时的情况,假设现在有一条直线(x1,y1,x2,y2),那么第一个点一定是(x1,y1)无疑,下一个点的x坐标为x1+1,y坐标要么为y1要么为y1+。关键在于每次取下一个点时,是取前一个的y1呢,还是y1+1,这时一定是取直线上点最靠近的那个了,而判断取哪个点就用到了中点,我们将中点代入直线中 d=F(x1+1,y1+0.5)=a*(x1+1)+b*(y1+0.5)+c。

        (1)如果直线d>=0,则取下边的点也就是(x1+1,y1)。 (2)如果直线d<0,则取上边的点也就是(x1+1,y1+1)。

      它的实际过程就是这样每次根据前边的点判断下一个点在哪,然后进行打亮,但这样每次判断的时候都得代入直线方程计算太麻烦了,我们将这俩种情况分别代入直线方程中可以找出规律:

        (1)当直线>=0时,经过化解得d1=d+a;

       (2)当直线<0时,经过化解得d2=d+a+b;

        (3)初始值d0=a+0.5b。

    也就是说每次的增量要么为a,要么为a+b,那么这样判断的时候就简单多了,因为我们每次只是判断它的正负。所以给等式同时乘2,将其中浮点数0.5化为整数,这样硬件操作时无疑更快了。

    代码:

    复制代码
     1 #include <iostream>
     2 #include <graphics.h>
     3 using namespace std;
     4 //中点画线法
     5 void line1(int x1,int y1,int x2,int y2){
     6 
     7      int x,y,d0,d1,d2,a,b;
     8      y=y1;             
     9      a=y1-y2;          //直线方程中的a的算法
    10      b=x2-x1;          //直线方程中的b的算法
    11      d0=2*a+b;         //增量初始值
    12      d1=2*a;           //当>=0时的增量
    13      d2=2*(a+b);       //当<0时的增量
    14      for(x=x1;x<=x2;x++){
    15             putpixel(x,y,GREEN);   //打亮
    16         if(d0<0){
    17             y++;            
    18             d0+=d2;
    19         }else{
    20 
    21         d0+=d1;
    22         }
    23 
    24      }
    25 }
    26 //Bresenham画线算法
    27 void line2(int x1,int y1,int x2,int y2){
    28 
    29    int x,y,dx,dy,d;
    30    y=y1;               
    31    dx=x2-x1;         
    32    dy=y2-y1;     
    33    d=2*dy-dx;        //增量d的初始值
    34    for(x=x1;x<=x2;x++){
    35     putpixel(x,y,GREEN);   //打亮
    36     if(d<0){
    37         d+=2*dy;
    38     }else{
    39       y++;
    40       d+=2*dy-2*dx;
    41     }
    42 
    43 
    44 
    45    }
    46 
    47 }
    48 int main()
    49 {
    50     initgraph(640,480);       //打开EGE初始化
    51     line1(200,160,400,400);   //画线
    52     getch();                  //等待用户操作
    53     closegraph();             //关闭图形
    54     return 0;
    55 }
    复制代码

    2、Bresenham画线算法

      这种画线算法的思想和中点画线的一致,只是在判断取哪个点时,不是看它位于中点的上边还是下边,而是将这俩个点到直线上那个点的距离相减,判断其正负,如果下边的点到直线实际点距离远则的d1-d2>=0那么取上边的点y1+1,同样也是代入直线化解可以得出下面结论:

      (1)当d1-d2<0时,d=d+2*dy.

      (2)当d1-d2>=0时,d=d+2*dy-2*dx.

      (3)d的初始值为  d=2*dy-dx.

     其代码如上所示。运行截图如下:

     

    分享为学习带来乐趣, 加油,加油!
          支持原创哦。
    展开全文
  • 之前我们使用DDA来画线, 这种算法每步只...中点画线算法 利用直线的一般方程 Ax + By + C = 0 对于一般直线方程, 对于直线上的点, 那么 Ax + By + C = 0 对于直线上方的点, 那么 Ax + By + C > 0 对于直线下方的...

    之前我们使用DDA来画线, 这种算法每步只进行一个加法运算,那么加法运算李里边有浮点数, 我们是否还可以再提高效率 也就是把浮点运算变成整数加法, 或者改变直线方程类型

    中点画线算法

    利用直线的一般方程 Ax + By + C = 0
    在这里插入图片描述
    对于一般直线方程,
    对于直线的点, 那么 Ax + By + C = 0
    对于直线上方的点, 那么 Ax + By + C > 0
    对于直线下方的点, 那么 Ax + By + C < 0

    每次在最大位移方向走一步, 另一个方向走还是不走,取决于中点误差的判断

    假设 0 <= |k| <= 1. 因此,每次在x方向+1, y方向 是否加一需要作出判断
    在这里插入图片描述
    对于该直线, xi的位置则是 取pi, 因为交点在 yi 到y (i+1) 的中点的下方, 下一个点则是取 pu 这个点, 因为交点在中点上方

    至于如何判断中点是在直线的上方还是下方
    我们就把中点坐标带入到直线方程判断是否大于零, 假设中点坐标是m, 那么就是判断
    di = Amx + Bmy +C 的大小, 也就是

    di = A(xi + 1) + B (yi + 0.5) + C
    在这里插入图片描述

    中点画线算法需要 四个加法,两个乘法,似乎效率也并没有多高

    增量计算

    1. d < 0

    在这里插入图片描述
    在这里插入图片描述
    推导可得, d1 = d0 + A + B

    2. d >= 0

    在这里插入图片描述
    推导 d1 = d0 + A

    3. 计算初始值d0

    在这里插入图片描述
    在这里插入图片描述
    d0 = A + 0.5B
    由于这里还是有0.5这个计算, 而且我们只需要判断d的正负号, 所以我们可以用2d来代替d计算
    也就是2d0 = 2A + B这样就全都是整数了.

    展开全文
  • 中点画线算法源码,可定义起点和终点,计算机图形学实验一
  • 中点画线算法

    2019-09-30 20:43:54
    中点画线算法(Midpoint Line Drawing Algorithm)是通过在每列像素中确定与理想直线最靠近的像素来进行扫描转换的。 步骤实现 斜率: 0<=k<=1 直线端点:(x1,y1),(x2,y2) 1) 初始化。令 a=y1-y2, b=x2-x1,...
  • 中点画线算法 为了方便阅读算法代码的人,现在这贴上算法核心代码: 算法过程: 注意:本过程只针对,斜率绝对值小于1的情况。 void DDADrawLine::MPDrawLine(int x0, int y0, int x1, int y1) { int a, b, ...
  • 相比于Breanham算法,中点画线算法更加直接。 中点算法的重要假设是,我们能绘出没有间隔的最细的直线。两对角像素之间的连接是没有间隔的。 一、中点画线算法原理 设线段端点为:(x1, y1),(x2, y2),∆x和∆y为...
  • 中点画线算法(任意斜率)

    万次阅读 2019-09-29 08:56:22
    直线段的过程中,当前像素点为(xp ,yp ),下一个像素点有两种可选择点P1(xp +1,yp )或P2(xp +1,yp +1)。若M=(xp +1,yp +0.5)为P1与P2之中点,Q为P理想直线与x=xp +1垂线的交点。当M在Q的下方,则P2应为下一个...
  • 中点画线算法详解

    2020-03-10 23:47:50
    中点画线算法 一、原理 已知直线的一般式方程: ​ F(x,y)=0F(x,y)=0F(x,y)=0, 即Ax+By+C=0Ax+By+C=0Ax+By+C=0 其中: A=−(Δy)A=-(\Delta y)A=−(Δy) B=(Δx)B=(\Delta x)B=(Δx) C=−B(Δx)C=-B(\Delta x)C=−...
  • 前言本笔记基于 http://www.icourse163.org/learn/CAU-45006?tid=1001746004#/learn/announce感谢中国农大 赵明老师的分享~现在我要为我自己走向游戏编程打下基石~1 计算机图形学概论1.1 计算机图形学课程简介...
  • // 使用中点算法画任意斜率的直线 void MidpointLine(int x0, int y0, int x1, int y1, int color) { int a,b,delta1,delta2,d,x,y; a=y0-y1; b=x1-x0; d=2*a+b; delta1=2*a; delta2=2*(a+b)
  • 用OpenGL实现 中点划线法

    千次阅读 2013-11-01 20:17:24
    #include "GL/glut.h" #include "stdio.h" #include "math.h" int xs, ys, xe, ye; void MidpointLine(int x0, int y0, int x1, int y1) { if((x0 != x1) && (y0 !... int a, b, deltal, delta2, d, x, y
  • 中点画线法(计算机图形学)

    万次阅读 2016-08-30 09:40:54
    // 使用中点算法画任意斜率的直线(包括起始点,不包括终止点) void Line_Midpoint(int x1, int y1, int x2, int y2, int color) { int x = x1, y = y1; int a = y1 - y2, b = x2 - x1; int cx = (b >= 0 ? 1
  • 任意斜率的中点画线算法

    千次阅读 2017-03-17 22:59:50
    一、中点画线算法的基本原理 在画直线的过程中,当前像素点P(xp,yp),则下一个点与直线最接近的像素只能是P1或者P2,即P点的正右方或者右上角的点。设M(xp+1,yp+0.5)为P1与P2的中点,Q为与理想直线与x=xp+1线相交的...
  • 计算机图形学算法演示程序(c#开源)

    千次阅读 2006-09-30 23:50:00
    演示了:画直线的 DDA法,中点画线法,Bresenham算法画圆的 中点画线法多边形的 扫描线算法,区域填充扫描线算法线段裁剪的 Cohen-Sutherland算法,中点分割算法,粱友栋-Barskey算法Beizer曲线的 定义画法和递推画法可以...
  • 求助各位大神,利用中点算法并考虑对称性,对抛物线x = y2在区间-10进行扫描转换,并绘制该曲线,用c++,谁会写这个代码啊
  • (4)直线的生成之中点画线

    千次阅读 2016-12-30 19:14:52
    基本原理: 假定直线斜率0 ...这种以中点M作为判别标志的方法即为中点画线法。 假设直线段的起点为(x1, y1),终点为(x2, y2)。设直线方程为:F (x, y)= ax + by + c =0 其中:a = y
  • Bresenham算法画直线

    万次阅读 2018-10-22 19:36:48
    title: 图形学-直线的扫描转换 date: 2018-10-22 20:31:06 updated: 2018-10-22 20:31:06 description: Bresenham算法画直线 categories: 必修 ...完成中点Bresenham画线,要求如下 创建名称为学号***...
  • 中点bresenham算法画线

    千次阅读 2017-10-21 13:28:51
    画线需要鼠标响应,所以在view类中添加OnLButtonUp和OnLButtonDown来进行鼠标消息的处理 方法:鼠标右击视图类(如CmyMouseView),选择“add windows message handler…”,弹出事件处理函数列表窗口 从左边
1 2 3 4 5 ... 20
收藏数 3,655
精华内容 1,462
关键字:

中点画线算法