Bresenham's line algorithm
The Bresenham line algorithm is an algorithm which determines which order to form a close approximation to a straight line between two given points. It is commonly used to draw lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures.
Algorithm:
editIn the following pseudocode sample plot(x,y)
plots a point and abs
returns absolute value:
function line(x0, x1, y0, y1) int deltax := x1 - x0 int deltay := y1 - y0 real error := 0 real deltaerr := abs (deltay / deltax) // Assume deltax != 0 (line is not vertical), // note that this division needs to be done in a way that preserves the fractional part int y := y0 for x from x0 to x1 plot(x,y) error := error + deltaerr if error ≥ 0.5 then y := y + 1 error := error - 1.0