# Line drawing algorithm

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.

## List of line drawing algorithms

The following is a partial list of line drawing algorithms:

### 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\geq dy}$ (i.e., slope is less than or equal to 1), but if ${\displaystyle dx (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 naive 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. Algorithms such as Bresenham's line algorithm or Xiaolin Wu's line algorithm are preferred instead.

### Gupta and Sproull algorithm

The Gupta-Sproull algorithm is based on Bresenham's line algorithm but adds antialiasing.

An optimized variant of the Gupta-Sproull algorithm can be written in pseudocode as follows:

```DrawLine(x1, x2, y1, y2) {
x = x1;
y = y1;
dx = x2 − x1;
dy = y2 − y1;
d = 2 * dy − dx; // discriminator

// Euclidean distance of point (x,y) from line (signed)
D = 0;

// Euclidean distance between points (x1, y1) and (x2, y2)
length = sqrt(dx * dx + dy * dy);

sin = dx / length;
cos = dy / length;
while (x <= x2) {
IntensifyPixels(x, y − 1, D + cos);
IntensifyPixels(x, y, D);
IntensifyPixels(x, y + 1, D − cos);
x = x + 1
if (d <= 0) {
D = D + sin;
d = d + 2 * dy;
} else {
D = D + sin − cos;
d = d + 2 * (dy − dx);
y = y + 1;
}
}
}
```

The IntensifyPixels(x,y,r) function takes a radial line transformation and sets the intensity of the pixel (x,y) with the value of a cubic polynomial that depends on the pixel's distance r from the line.

## References

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