Line drawing algorithm

This article may be expanded with text translated from the corresponding article in German. (December 2009) Click [show] for important translation instructions. View a machine-translated version of the German article. Machine translation like DeepL or Google Translate is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Wikipedia. Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article. You must provide copyright attribution in the edit summary accompanying your translation by providing an interlanguage link to the source of your translation. A model attribution edit summary is Content in this edit is translated from the existing German Wikipedia article at [[:de:Rasterung von Linien]]; see its history for attribution. You should also add the template {{Translated|de|Rasterung von Linien}} to the talk page. For more guidance, see Wikipedia:Translation.

Two rasterized lines. The colored pixels are shown as circles. Above: monochrome screening; below: Gupta-Sproull anti-aliasing; the ideal line is considered here as a surface.

In computer graphics, a line drawing algorithm is an algorithm for approximating a line segment on discrete graphical media, such as pixel-based displays and printers. On such media, line drawing requires an approximation (in nontrivial cases). Basic algorithms rasterize lines in one color. A better representation with multiple color gradations requires an advanced process, spatial anti-aliasing.

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

The Cartesian slope-intercept equation for a straight line is ${\displaystyle Y=mx+b}$ With m representing the slope of the line and b as the y-intercept. Given that the two endpoints of the line segment are specified at positions ${\displaystyle (x1,y1)}$ and ${\displaystyle (x2,y2)}$, we can determine values for the slope m and y-intercept b with the following calculations: ${\displaystyle m=(y2-y1)/(x2-x1)}$ so, ${\displaystyle b=y1-m*x1}$.

List of line drawing algorithms[]

Lines using Xiaolin Wu's algorithm, showing "ropey" appearance.

The following is a partial list of line drawing algorithms:

• naive algorithm
• Digital Differential Analyzer (graphics algorithm) — Similar to the naive line-drawing algorithm, with minor variations.
• 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 spatial anti-aliasing, appears "ropey" from brightness varying along the length of the line, though this effect may be greatly reduced by pre-compensating the pixel values for the target display's gamma curve, e.g. out = in ^ (1/2.4).^{[original research?]}

A naive line-drawing algorithm[]

The simplest method of screening is the direct drawing of the equation defining the line.

dx = x2 − x1
dy = y2 − y1

for x from x1 to x2 do
    y = y1 + dy × (x − x1) / dx
    plot(x, y)

It is here that the points have already been ordered so that ${\displaystyle x_{2}>x_{1}}$. This algorithm works just fine when ${\displaystyle dx>=dy}$ (i.e., slope is less than or equal to 1), but if ${\displaystyle dx<dy}$ (i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of ${\displaystyle dx=0}$, a division by zero exception will occur.

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.

References[]

Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by Peter Shirley