欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2024-03-16 20:16:10
...

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

相关标签: cg