Editing Bresenham's line algorithm (section)

===Algorithm===
The starting point is on the line

:<math>f(x_0, y_0) = 0</math>

only because the line is defined to start and end on integer coordinates (though it is entirely reasonable to want to draw a line with non-integer end points).

[[File:Line 1.5x+1 -- candidates.svg|300px|thumb|Candidate point (2,2) in blue and two candidate points in green (3,2) and (3,3)]]

Keeping in mind that the slope is at most <math>1</math>, the problem now presents itself as to whether the next point should be at <math>(x_0 + 1, y_0)</math> or <math>(x_0 + 1, y_0 + 1)</math>. Perhaps intuitively, the point should be chosen based upon which is closer to the line at <math>x_0 + 1</math>.  If it is closer to the former then include the former point on the line, if the latter then the latter. To answer this, evaluate the line function at the midpoint between these two points:

:<math>f(x_0 + 1, y_0 + \tfrac 1 2)</math>

If the value of this is positive then the ideal line is below the midpoint and closer to the candidate point <math>(x_0+1,y_0+1)</math>; i.e. the y coordinate should increase.  Otherwise, the ideal line passes through or above the midpoint, and the y coordinate should stay the same; in which case the point <math>(x_0+1,y_0)</math> is chosen. The value of the line function at this midpoint is the sole determinant of which point should be chosen.

The adjacent image shows the blue point (2,2) chosen to be on the line with two candidate points in green (3,2) and (3,3).  The black point (3, 2.5) is the midpoint between the two candidate points.