Derive the decision equations init and the two directions us

Derive the decision equation(s) (init, and the two directions) used in the Bresenham algorithm when the slope m<-1

Solution

To find the best \"next pixel\", first we must find the distances to the two available choices from the ideal location (of the real line). Distance between pixel-to-right and ideal pixel is: d1 = y - y(k) and the distance between pixel-to-right-and-up and ideal pixel is: d2 = (y(k)+1) - y. So we can simply choose subsequent pixels based on the following:
if (d1<=d2) then choose pixel-to-right: ( x(k)+1, y(k) )
if (d1>d2) then choose pixel-to-right-and-up: ( x(k)+1, y(k)+1 )
In order to develop a fast way of doing this, we will not be comparing these values in such a manner; instead we will create a decision variable that can be used to quickly determine which point to use.

Instead of comparing the two values to each other, we can simply evaluate d1-d2 and test the sign to determine which to choose. If d1 > d2 then d1-d2 will be strictly positive, and if d1-d2 is strictly positive, we will choose pixel-to-right-and-up. If d1-d2 is negative or zero, we will choose pixel-to-right. In addition to this optimization, Bresenham Algorithm suggests to optimize more. If we evaluate d1-d2 as follows:
d1-d2 = y - y(k) - ( (y(k)+1) - y ) = y - y(k) - (y(k)+1) + y and now substitute using y = m*(x(k)+1) + b, we get
d1-d2 = m*(x(k)+1) + b - y(k) - (y(k)+1) + m*(x(k)+1) + b = 2*m*(x(k)+1) - 2*y(k) + 2*b - 1
The last equation can be reduced by the slope m and substituting as follows:
m = dY/dX where dY = abs(By - Ay) and dX = abs(Bx - Ax), so now we have
d1-d2 = 2*(dY/dX)*(x(k)+1) - 2*y(k) + 2*b - 1 or if we expand the first term (multiply), then:
d1-d2 = 2*(dY/dX)*x(k) + 2*(dY/dX) - 2*y(k) + 2*b - 1

This last equation can be simplified by creating a new decision variable P(k) = dX * (d1-d2). This will remove the divisions (all integer operations for faster and efficient computing) and will still keep the same sign for the decision because dX variable is always positive (dX = abs(Bx - Ax) - absolute value).
If we now evaluate a new decision variable P(k), we get:
P(k) = dX * ( 2*(dY/dX)*x(k) + 2*(dY/dX) - 2*y(k) + 2*b - 1 ) or further:
P(k) = 2*dY*x(k) + 2*dY - 2*dX*y(k) + 2*dX*b - dX
If we now rearrange the terms in the last equation, we get:
P(k) = 2*dY*x(k) - 2*dX*y(k) + 2*dY + 2*dX*b - dX or
P(k) = 2*dY*x(k) - 2*dX*y(k) + c where c is always constant value (it depends only on the input endpoints) and is equal to 2*dY + dX*(2*b - 1)

Using described approach, decision variable can be computed very efficiently, but it still requires evaluation of P(k) for each point (pixel) along a line. Since line entity is linear in its nature, P(k) change will be linear as well, therefore we can evaluate subsequent P(k) values incrementally by finding a constant change in P(k) for each subsequent pixel. By evaluating an incremental change of the decision function P = dP = P(k+1) - P(k) we can evaluate by substitution dP as follows:
P(k+1) - P(k) = 2*dY*x(k+1) - 2*dX*y(k+1) + c - 2*dY*x(k) + 2*dX*y(k) - c
= 2*dY*x(k+1) - 2*dY*x(k) - 2*dX*y(k+1) + 2*dX*y(k)
= 2*dY*(x(k+1) - x(k)) - 2*dX*(y(k+1) - y(k))
Since we are processing pixel one by one in the x direction, the change in the x direction is (x(k+1) - x(k)) = 1, so if we substitute this into our dP derivation, we get:
dP = 2*dY - 2*dX*(y(k+1) - y(k))
For the y direction, there are two possibilities; the term (y(k+1) - y(k)) can be only 0 or 1, depending on if we choose pixel-to-right or pixel-to-right-and-up, so now our dP derivation looks like:
dP = 2*dY - 2*dX*(0) = 2*dY if pixel-to-right is chosen
dP = 2*dY - 2*dX*(1) = 2*dY - 2*dX if pixel-to-right-and-up is chosen

The only remaining thing is to decide what is the initial value of P(0). This can be decided by evaluating equation P(k) = 2*dY*x(k) - 2*dX*y(k) + 2*dY + dX*(2*b - 1), so for zero, we get:
P(0) = 2*dY*x(0) - 2*dX*y(0) + 2*dY + dX*(2*b - 1)
From line equation at the starting pixel y(0) = m*x(0) + b we get term for b intercept b = y - m*x(0). Substituting b and slope m = dY/dX into equation P(0) we get:
P(0) = 2*dY*x(0) - 2*dX*y(0) + 2*dY + dX*(2*(y(0) - (dY/dX)*x(0)) - 1)
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + 2*dX*(y(0) - (dY/dX)*x(0)) - dX
= 2*dY*x(0) - 2*dX*y(0) + 2*dY + 2*dX*y(0) - 2*dY*x(0) - dX
P(0) = 2*dY - dX