This is a line drawing algorithm based on the square distance (aka the Chebyshev distance) between two points. To draw a line between the points (x1, y1) and (x2, y2),
d = max(abs(x2-x1), abs(y2-y1)) + 1
dx = (x2-x1) / d
dy = (y2-y1) / d
while i ≤ d do
draw_point(x1, y1)
x1 = x1 + dx
y1 = y1 + dy
i = i + 1
done
The advantage that this algorithm has is that it is fast, though it has the disadvantage of being possible for rounding errors to occur, regardless of whether dx and dy are stored as floating point or fixed point.
The following algorithm is a variant of Bresenham's line drawing algorithm breifly described Alois Zingl's paper A Rasterizing Algorithm for Drawing Curves on page 13.
dx = abs(x2-x1)
dy = abs(y2-y1)
sx = sign(x2-x1)
sy = sign(y2-y1)
err = dx - dy
draw_point(x1,y1);
while x1 ≠ x2 and y1 ≠ y2 do
draw_point(x1,y1)
if 2×err ≥ dy then
err = err - dy
x1 = x1 + sx
end
if 2×err ≤ dx then
err = err + dx
y1 = y1 + sy
end
done
The main benefit of this algorithm, as compared to other line drawing algorithms, is that it produces an exact line between two points, and only uses