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:

• calculate the middle point $M:=(x+1,\bar{y}+\frac12)$.
• If the intersection point $Q$ of the line with the vertical line connecting $E$ and $NE$ is below $M$, take $E$ as next pixel.
• Otherwise take $NE$ as next pixel.

Figure: Midpoint line algorithm

In oder to check this condition we consider the implicit equation

$$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

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

$$= (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

$$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

$$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]:

• Endpoint order: This procedure is not independent from which side of the line we are starting from (in case the line hits some middle point). It is not a good idea to sort the endpoints first in case of line-styles like dashing, since a polygon should be drawn in succession.

  E.g., the following line from $(0,0)$ to $(4,3)$:

  Figure: Dependency on order of endpoints

  

• Starting at the clipping edge:

  Do not clip (see (2.5) below) and then scan-convert if line hits the left boundary of the clipping rectangle.

  Figure: Clipping at left boundary

  

  In case of a horizontal boundary we may miss some points at the beginning. In oder to avoid this we should start at the intersection point with the line $y=y_{\min}-\frac12$ below the horizontal lower boundary $y=y_{\min}$

  Figure: Clipping at the lower boundary

  

• Varying Intensity:

  The number of pixel per length depends on the slope. It will be 1 for horizontal lines and $1/\sqrt{2}$ for slope 1.

  Figure: Dependency of intensity on slope of line

  

  So one could modify the intensity of pixels drawn. Another (and even better method) is anti-aliasing as discussed below.