您的当前位置:首页正文

中点画线算法-原理及实现

2024-11-28 来源:个人技术集锦

在编写的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;
    }
}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

显示全文