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

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