Line drawing algorithm

From Wikipedia, the free encyclopedia

A line drawing algorithm is a graphical algorithm for approximating a line segment on discrete graphical media. On discrete media, such as pixel-based displays and printers, line drawing requires such an approximation (in nontrivial cases).

On continuous media, by contrast, no algorithm is necessary to draw a line. For example, oscilloscopes use natural phenomena to draw lines and curves.

[edit] A naïve line-drawing algorithm

dx = x2 - x1
dy = y2 - y1
for x from x1 to x2 {
        y = y1 + (dy) * (x - x1)/(dx)
        plot(x, y)
}

It is assumed here that the points have already been ordered so that $x 2 > x 1$ . This algorithm works just fine when $d x > = d y$ , but it is quite slow on a digital computer, as it requires floating-point calculations. If $d x < d y$ , the line becomes quite sparse, and in the limiting case of $d x = 0$ , only a single point is plotted!

[edit] List of line drawing algorithms

The following is a partial list of line drawing algorithms:

Bresenham's line algorithm — optimized to use only additions (i.e. no divisions or multiplications); it also avoids floating-point computations.
Xiaolin Wu's line algorithm — can perform anti-aliasing
EFLA line algorithm — A very fast implementation.
gatopeich's line algorithm — Fast, simple, aesthetic. Based on pure integer operations.