原创 Bresenham算法在液晶屏画图中的应用

<?xml:namespace prefix = v ns = "urn:schemas-microsoft-com:vml" /><?xml:namespace prefix = o ns = "urn:schemas-microsoft-com:office:office" />Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法。仍然假定直线斜率在0~1之间，该方法类似于中点法，由一个误差项符号决定下一个象素点。

    算法原理如下：过各行各列象素中心构造一组虚拟网格线。按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列象素中与此交点最近的象素。该算法的巧妙之处在于采用增量计算，使得对于每一列，只要检查一个误差项的符号，就可以确定该列的所求象素。

     设直线方程为yi+1=yi+k(xi+1-xi)+k。假设列坐标象素已经确定为xi，其行坐标为yi。那么下一个象素的列坐标为xi＋1，而行坐标要么为yi，要么递增1为yi＋1。是否增1取决于误差项d的值。误差项d的初值d0＝0，x坐标每增加1，d的值相应递增直线的斜率值k，即d＝d＋k。一旦  d≥1，就把它减去1，这样保证d在0、1之间。当d≥0.5时，直线与垂线x=xi＋1交点最接近于当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当d<0.5时，更接近于右方象素(xi＋1，yi)。为方便计算，令e＝d－0.5，e的初值为－0.5，增量为k。当e≥0时，取当前象素(xi，yi)的右上方象素(xi＋1，yi＋1)；而当e<0时，取(xi，yi)右方象素(xi＋1，yi)。

//Bresenham画线算法程序：

void Bresenhamline (int x0,int y0,int x1, int y1,int color)

{  

    int x, y, dx, dy；

    float k, e;

    dx = x1-x0；dy = y1- y0；k=dy/dx；

//dx,dy是直线总的增量。k是实数的斜率e="-0".5； x="x0"；y=y0；

//x,y为起点。e是调整数，以使问题成为〉=0，还是<0的问题。
/*--------------------------------------------------------------------
为方便计算，令e0=－0.5，e i+1＝di+1－0.5，增量为k。当ei+1≥0时，取当前像素（xi，yi）的右上方像素（xi＋1， yi＋1）；而当e i+1<0时，更接近于右方像素（xi＋1，yi）。
--------------------------------------------------------------------*/
//这里，我们利用了k=dy/dx这个斜率，而不是利用上面的逐个比较的方法。
//实数yi的值>=0.5,则用y（整数）+1的像素，<0.5则y轴仍用上一个像素的y坐标。
//一旦，用y+1，则我们的yi这个y轴的实数增量就会多出1这个增量。所以，一旦y++,就要yi--。
//这里，为了使我们不是判断是否>=0.5，而是改为判断是否>=0，我们需要对所有的yi-0.5。
//这实际上只需yi-0.5一次即可。因为yi是连续的增量----+k。
//这里我们用float e表示yi,并且赋e=-0.5,以后e=e+k,这样实际上就实现了给e-0.5的目的。

  for (i=0

      drawpixel (x, y, color);

      x="x"+1；e=e+k;

      if (e>=0)

     {

         y++；

         e="e-1";

     }

  }

}

 /*---------------------------------------------------------------

举例：用Bresenham方法扫描转换连接两点P0（0,0）和P1（5,2）的直线段。

 i x y e
0
 --  0 0 -0.5
    1     -0.1
      
   1 0 -0.1

   2 1 -0.7

   3 1 -0.3

   4 2 -0.9                                   

   5 2 -0.5  

    上述Bresenham算法在计算直线斜率与误差项时用到小数与除法。可以改用整数以避免除法。
    由于算法中只用到误差项的符号，因此可作如下替换：2*e*dx。 

 -------------------------------------------------------------------*/

{
    int x, y, dx, dy；

    int k, e;
    dx = x1-x0；dy = y1- y0；e=-dx;

    x="x0"；
    y="y0";

    for (i=0; i<dx; i++)

    {

        drawpixel (x, y, color);

        x++；

        e="e"+2*dy;

        if (e>=0)

       {

          y++;

          e="e-2"*dx;

       }

   }

}

我们用e=k-0.5 ， e的初值是-0.5。
现在我们将其变形， e=dy/dx-0.5 , 两边同乘2， 
得 2e=2dy/dx-1 , 再同乘 dx
得 2edx=2dy-dx,  令e'=2edx,  到了e'=2dy-dx, 
再令e'的初值为-dx，则每次递增 为 2dy，
因此有 程序中的 e=e+2*dy !
同时还有一处 e=e-2*dx 。 之前 我们用的是e=e-1,
现在，我们两边同乘2dx,
得 2edx=2edx-2dx,  因为e'=2edx , 
则有 e'=e'-2dx !

BresenHam算法适用于斜率小于1的情况 当斜率大于1时 可以交换x,y坐标实现.

当斜率为负数时~   自己想办法解决  O(∩_∩)O~