中点画线算法

2.1 直线段的扫描转换算法

  中点画线法

    假定直线斜率k在0~1之间，当前象素点为（x_p,y_p），则下一个象素点有两种可选择点P₁（x_p+1,y_p）或P₂（x_p+1,y_p+1）。若P₁与P₂的中点（x_p+1,y_p+0.5）称为M，Q为理想直线与x=x_p+1垂线的交点。当M在Q的下方时，则取P₂应为下一个象素点；当M在Q的上方时，则取P₁为下一个象素点。这就是中点画线法的基本原理。

  图2.1.2 中点画线法每步迭代涉及的象素和中点示意图

     下面讨论中点画线法的实现。过点(x₀,y₀)、(x_1, y₁)的直线段L的方程式为F(x, y)=ax+by+c=0，其中，a=y₀-y₁, b=x₁-x₀, c=x₀y₁-x₁y₀，欲判断中点M在Q点的上方还是下方，只要把M代入F（x，y），并判断它的符号即可。为此，我们构造判别式:

d=F(M)=F(x_p+1, y_p+0.5)=a(x_p+1)+b(y_p+0.5)+c

     当d<0时，M在L(Q点)下方，取P₂为下一个象素；

     当d>0时，M在L(Q点)上方，取P₁为下一个象素；

     当d=0时，选P₁或P₂均可，约定取P₁为下一个象素；

注意到d是x_p, y_p的线性函数，可采用增量计算，提高运算效率。

    若当前象素处于d30情况，则取正右方象素P₁(x_p+1, y_p),要判下一个象素位置，应计算 d₁=F(x_p+2, y_p+0.5)=a(x_p+2)+b(y_p+0.5)=d+a，增量为a。

    若d<0时，则取右上方象素P₂(x_p+1, y_p+1)。要判断再下一象素，则要计算d₂= F(x_p+2, y_p+1.5)=a(x_p+2)+b(y_p+1.5)+c=d+a+b ，增量为a＋b。画线从(x₀, y₀)开始，d的初值 d₀=F(x₀+1, y₀+0.5)=F(x₀, y₀)+a+0.5b，因  F(x₀, y₀)=0，所以d₀=a+0.5b。

    由于我们使用的只是d的符号，而且d的增量都是整数，只是初始值包含小数。因此，我们可以用2d代替d来摆脱小数，写出仅包含整数运算的算法程序。

中点画线算法程序：

void Midpoint Line (int x0,int y0,int x1, int y1,int color)

{ int a, b, d1, d2, d, x, y；

  a=y0-y1； b=x1-x0；d=2*a+b；

  d1=2*a；d2=2* (a+b)；

  x=x0；y=y0；

  drawpixel(x, y, color);

  while (x<x1)

  { if (d<0)   {x++；y++； d+=d2; }

    else      {x++； d+=d1;}

    drawpixel (x, y, color);

  } /* while */

} /* mid PointLine */

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

a=y0-y1=-2; b=x1-x0=5; d0=2*a+b=1;d1=2*a=-4;d2=2*(a+b)=6 ,

x y   d

0 0   1

1 0   -3

2 1   3

3 1   -1        

4 2    5                                    图2.1.3 中点画线法

5 2   15

问题1：若上述算法往下取二步(Di=2)，则算法和象素的取法将变成怎样？

问题2：与DDA法相比，中点法的优点是什么？

页首

动画演示：中点画线算法