Line drawing algorithm

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.

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 dx >= dy, but it is quite slow on a digital computer, as it requires floating-point calculations. If dx < dy, the line becomes quite sparse, and in the limiting case of dx = 0, only a single point is plotted!

List of line drawing algorithms

The following is a partial list of line drawing algorithms:
*Bresenham's line algorithm &mdash; optimized to use only additions (i.e. no divisions or multiplications); it also avoids floating-point computations.
*Xiaolin Wu's line algorithm &mdash; can perform anti-aliasing
* [http://www.edepot.com/algorithm.html EFLA line algorithm] &mdash; A very fast implementation.
* [http://gatopeichs.pbwiki.com/gatopeich%27s-Graphic-Algorithms#LineDrawingbyIntegerOperations gatopeich's line algorithm] &mdash; Fast, simple, aesthetic. Based on pure integer operations.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Line drawing — Line drawings may mean:*Line art, a style of two dimensional art featuring only two, unshaded, contrasting colors; or *a line drawing algorithm in computer graphics.See also: *Box drawing characters for specific characters, also known as line… …   Wikipedia

  • Line (geometry) — Three lines the red and blue lines have the same slope, while the red and green ones have same y intercept …   Wikipedia

  • Bresenham's line algorithm — The Bresenham line algorithm is an algorithm that 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. It is commonly used to draw lines on a… …   Wikipedia

  • 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… …   Wikipedia

  • Digital Differential Analyzer (graphics algorithm) — In Computer graphics, an hard or software implementation of a Digital Differential Analyzer (DDA) is used for linear interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and… …   Wikipedia

  • Hidden line removal — is an extension of wireframe rendering where lines (or segments of lines) covered by surfaces are not drawn.This is not the same as hidden face removal since this involves depth and occlusion while the other involves normals.A commonly used… …   Wikipedia

  • Midpoint circle algorithm — In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle. The algorithm is a variant of Bresenham s line algorithm, and is thus sometimes known as Bresenham s circle algorithm,… …   Wikipedia

  • Maze generation algorithm — Maze generation algorithms are automated methods for the creation of mazes. This maze generated by modified version of Prim s algorithm, below. Contents 1 Graph theory based methods …   Wikipedia

  • Maze solving algorithm — There are a number of different maze solving algorithms, that is, automated methods for the solving of mazes. A few important maze solving algorithms are explained below. The random mouse, wall follower, Pledge, and Trémaux algorithms are… …   Wikipedia

  • Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.