/linedrawing

Algorithm A (fast)

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
i = 0
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.

Algorithm B (exact)

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
while true do
	draw_point(x1,y1)
	if 2×err ≥ -dy then
		if x1 = x2 break
		err = err - dy
		x1 = x1 + sx
	end
	if 2×err ≤ dx then
		if y1 = y2 break
		err = err + dx
		y1 = y1 + sy
	end
done
draw_point(x1,y1)

The main benefit of this algorithm, as compared to other line drawing algorithms, is that it always produces an exact line between two points, and only uses whole integers.

---