2.2.2 Midpoint Line Algorithm

Cf. [FvDFH90, 3.2.2]

The midpoint line algorithm is due to Bresenham [Bre65] and was modified by Pitteway [Pit67] and Van Aken [VA84]. It works as follows: Let the slope of the line be $ 0\leq k\leq 1$. Suppose one approximate point $ P=(x,\bar{y})$ is already determined. We have only two choices for the next point, namely $ E:=(x+1,\bar{y})$ and $ NE:=(x+1,\bar{y}+1)$ and we should choose the one which is closer to $ k(x+1)+d$. To determine the appropriate choice we proceed as follows:

Figure: Midpoint line algorithm
\begin{figure}\begin{picture}(4,4)
\put(1,1){\circle*{0.2}}
\put(1,1){\makebox(0...
...xt{st}}$}}
\put(3,0.5){\makebox(0,0){$2^{\text{nd}}$}}
\end{picture}\end{figure}

In oder to check this condition we consider the implicit equation

$\displaystyle f(x,y):=a\,x+b\,y+c:=(y_1-y_0)\,x - (x_1-x_0)\,y + (x_1\,y_0-y_1\,x_0)
$

where we may assume that $ a>0$. Note that $ f(x,y)=0$ if and only if $ (x,y)$ lies on the line. And $ f(x,y)>0$ if and only if $ (x,y)$ lies below the line. So in the first step we have to test

$\displaystyle f\left(x+1,\bar{y}+\frac12\right)$ $\displaystyle = a\,(x+1)+b\,\left(\bar{y}+\frac12\right)+c$    
  $\displaystyle = (a\,x + b\,\bar{y} + c)+\left(a+b\,\frac12\right) = f(x,\bar{y})+a+\frac{b}2.$    

In case we choose $ E$ we have to test for the next ( $ 2^{\text{nd}}$) column

$\displaystyle f\left(x+2,\bar{y}+\frac12\right)=f\left(x+1,\bar{y}+\frac12\right)+a.
$

In case we choose $ NE$ we have to test

$\displaystyle f\left(x+2,\bar{y}+1+\frac12\right)=f\left(x+1,\bar{y}+\frac12\right)+a+b.
$

Thus the test for the next column can be easily obtained from that for the previous one by adding $ a$ or $ a+b$ accordingly.

Lines with other slopes can be obtained by mirroring.

Some issues concerning this algorithm have to be taken into account, cf. [FvDFH90, 3.2.3]:

Andreas Kriegl 2003-07-23