Line drawing algorithm
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 display
s and printer
s, line drawing requires such an approximation (in nontrivial cases).
On continuous media, by contrast, no algorithm is necessary to draw a line. For example, oscilloscope
s use natural phenomena to draw lines and curves.
It is assumed here that the points have already been ordered so that
.
This algorithm works just fine when
(i.e., slope is less than or equal to 1), but if 
(i.e., slope greater than 1), the line becomes quite sparse with lots of gaps, and in the limiting case of 
, only a single point is plotted.
The naïve line drawing algorithm is inefficient and thus, slow on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations. Line drawing algorithms such as Bresenham
's or Wu
's are preferred instead.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
for approximating a line segment on discrete graphical media. On discrete media, such as pixel
Pixel
In digital imaging, a pixel, or pel, is a single point in a raster image, or the smallest addressable screen element in a display device; it is the smallest unit of picture that can be represented or controlled....
-based display
Computer display
A monitor or display is an electronic visual display for computers. The monitor comprises the display device, circuitry, and an enclosure...
s and printer
Computer printer
In computing, a printer is a peripheral which produces a text or graphics of documents stored in electronic form, usually on physical print media such as paper or transparencies. Many printers are primarily used as local peripherals, and are attached by a printer cable or, in most new printers, a...
s, line drawing requires such an approximation (in nontrivial cases).
On continuous media, by contrast, no algorithm is necessary to draw a line. For example, oscilloscope
Oscilloscope
An oscilloscope is a type of electronic test instrument that allows observation of constantly varying signal voltages, usually as a two-dimensional graph of one or more electrical potential differences using the vertical or 'Y' axis, plotted as a function of time,...
s use natural phenomena to draw lines and curves.
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
.This algorithm works just fine when
(i.e., slope is less than or equal to 1), but if (i.e., slope greater than 1), the line becomes quite sparse with lots of gaps, and in the limiting case of , only a single point is plotted.The naïve line drawing algorithm is inefficient and thus, slow on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations. Line drawing algorithms such as Bresenham
Bresenham's line algorithm
The Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points...
's or Wu
Xiaolin Wu's line algorithm
Xiaolin Wu's line algorithm is an algorithm for line antialiasing, which was presented in the article An Efficient Antialiasing Technique in the July 1991 issue of Computer Graphics, as well as in the article Fast Antialiasing in the June 1992 issue of Dr. Dobb's Journal.Bresenham's algorithm draws...
's are preferred instead.
List of line drawing algorithms
The following is a partial list of line drawing algorithms:- Digital Differential Analyzer (graphics algorithm)Digital Differential Analyzer (graphics algorithm)In computer graphics, a hardware or software implementation of a digital differential analyzer is used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons...
— Similar to the naive line-drawing algorithm, with minor variations. - Bresenham's line algorithmBresenham's line algorithmThe Bresenham line algorithm is an algorithm which determines which points in an n-dimensional raster should be plotted in order to form a close approximation to a straight line between two given points...
— optimized to use only additions (i.e. no divisions or multiplications); it also avoids floating-point computations. - Xiaolin Wu's line algorithmXiaolin Wu's line algorithmXiaolin Wu's line algorithm is an algorithm for line antialiasing, which was presented in the article An Efficient Antialiasing Technique in the July 1991 issue of Computer Graphics, as well as in the article Fast Antialiasing in the June 1992 issue of Dr. Dobb's Journal.Bresenham's algorithm draws...
— can perform anti-aliasingAnti-aliasingIn digital signal processing, spatial anti-aliasing is the technique of minimizing the distortion artifacts known as aliasing when representing a high-resolution image at a lower resolution...