= Solution
By exchanging axes, reversing endpoint order and reflecting coordinate signs where necessary, reduce a general <line segment> to the first octant:
$$
\Delta x=x_1-x_0>0,\qquad 0\leq\Delta y=y_1-y_0\leq\Delta x,\qquad m=\frac{\Delta y}{\Delta x}\in[0,1].
$$
The vertical case is handled by exchanging axes. In this octant, increasing $x$ by one requires increasing $y$ by either zero or one. Thus, from the currently plotted <pixel> $(x,y)$ the candidates are $E=(x+1,y)$ and $NE=(x+1,y+1)$.
Use the <implicit equation> of the <line>
$$
f(X,Y)=\Delta y(X-x_0)-\Delta x(Y-y_0).
$$
At a fixed $X$, $f(X,Y)>0$ means that $(X,Y)$ lies below the exact <line>. The <midpoint line decision> evaluates $M=(x+1,y+1/2)$, halfway between the two candidate <pixel> centres. If $f(M)<0$, the exact <line> lies below $M$, so choose $E$; if $f(M)>0$, choose $NE$. At equality either candidate is equally near, but a fixed tie rule is essential. We choose $NE$ on a tie throughout these solutions:
$$
\boxed{f(x+1,y+1/2)<0\Rightarrow E;\qquad f(x+1,y+1/2)\geq0\Rightarrow NE.}
$$
This chooses the closest vertical-grid <pixel> centre in each column, with ties rounded upward. Since $0\leq m\leq1$, the result has one <pixel> per column and consecutive <pixels> share an edge or a corner.
Back to article page
