Editing Line drawing algorithm (section)

== Single color line drawing algorithms ==
[[File:Xiaolin Wu lines.png|thumb|Lines using Xiaolin Wu's algorithm, showing "ropey" appearance]]
Single color line drawing algorithms involve drawing lines in a single foreground color onto a background. They are well-suited for usage with monochromatic displays.

The starting point and end point of the desired line are usually given in integer coordinates, so that they lie directly on the points considered by the algorithm. Because of this, most algorithms are formulated only for such starting points and end points.

=== Simple Methods ===
The simplest method of drawing a line involves directly calculating pixel positions from a line equation. Given a starting point <math>(x_1, y_1)</math> and an end point <math>(x_2, y_2)</math>, points on the line fulfill the equation <math>y = m(x-x_1) + y_1</math>, with <math>\textstyle m = \frac{\Delta y}{\Delta x} = \frac{y_2-y_1}{x_2-x_1}</math> being the [[slope]] of the line. The line can then be drawn by evaluating this
equation via a simple loop, as shown in the following pseudocode:

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

Here, the points have already been ordered so that <math>x_2 > x_1</math>.

This algorithm is unnecessarily slow because the loop involves a multiplication, which is significantly slower than addition or subtraction on most devices. A faster method can be achieved by viewing the Difference between two consecutive steps:

:{|
|-
| <math>y_{i+1} - y_i \!</math>
| <math>= (m(x_{i+1}-x_1) + y_1) - (m(x_i-x_1) + y_1) \!</math>
|-
|  || <math>= m(x_{i+1}-x_i) \!</math>
|-
|  || <math>= m \!</math>.
|}

Therefore, it is enough to simply start at the point <math>(x_1, y_1)</math> and then increase <math> y </math> by <math> m </math> once on every iteration of the loop. This algorithm is known as a [[Digital differential analyzer (graphics algorithm) | Digital differential analyzer]].

Because rounding <math> y </math> to the nearest whole number is equivalent to rounding <math> y+0.5 </math> down, rounding can be avoided by using an additional control variable that is initialized with the value 0.5. <math> m </math> is added to this variable on every iteration. Then, if this variable exceeds 1.0, <math> y </math> is incremented by 1 and the control variable is decremented by 1. This allows the algorithm to avoid rounding and only use integer operations. However, for short lines, this faster loop does not make up for the expensive division <math>\textstyle m = \frac{\Delta y}{\Delta x} = \frac{y_2-y_1}{x_2-x_1}</math>, which is still necessary at the beginning.

These algorithm works just fine when <math>dx \geq dy</math> (i.e., slope is less than or equal to 1), but if <math>dx < dy</math> (i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of <math>dx = 0</math>, a division by zero exception will occur.

=== Issues ===
In certain situations, single color line drawing algorithms run into issues:

==== Inconsistent brightness ====
When drawing lines of the same length with differing slopes, different numbers of pixels are drawn. This leads to steeper lines being made up of fewer pixels than flatter lines of the same length, which leads to the steeper line appearing brighter than the flat line. This problem is unavoidable on monochromatic devices.

==== Clipping ====
[[Clipping_(computer_graphics)|Clipping]] is an operation that limits rasterisation to a limited, usually rectangular, area. This is done by moving the start- and end points of the given line to the borders of this area if they lie outside of it. Generally, this leads to the coordinates of these points no longer being integer numbers. If these coordinates are simply rounded, the resulting line will have a different slope than intended. For this issue to be avoided, additional tests are necessary after clipping.