**Algorithm**

Clearly, the starting point is on the line

only because the line is defined to start and end on integer coordinates (though it is entirely reasonable to want to draw a line with non-integer end points).

Keeping in mind that the slope is less-than-or-equal-to one, the problem now presents itself as to whether the next point should be at or . Perhaps intuitively, the point should be chosen based upon which is closer to the line at . If it is closer to the former then include the former point on the line, if the latter then the latter. To answer this, consider the midpoint between these two points:

If the value of this is negative then the midpoint lies above the line, and if the value of this is positive then the midpoint lies below the line. If the midpoint lies below the line then should be chosen since it is closer; otherwise should be chosen. This observation is crucial to understand! The value of the line function at this midpoint is the sole determinant of which point should be chosen.

The image to the right shows the blue point (2,2) chosen to be on the line with two candidate points in green (3,2) and (3,3). The black point (3, 2.5) is the midpoint between the two candidate points.

Alternatively, the difference between points can be used instead of evaluating f(x,y) at midpoints. The difference for the first decision is

If this difference, D, is positive then chose otherwise .

The decision for the second point can be written as

If the difference is positive then is chosen, otherwise . This decision can be generalized by accumulating the error.

All of the derivation for the algorithm is done. One performance issue is the 1/2 factor in the initial value of D. Since all of this is about the sign of the accumulated difference, then everything can be multiplied by 2 with no consequence.

This results in an algorithm that uses only integer arithmetic.

plot(x0,y0, x1,y1) dx=x1-x0 dy=y1-y0 D = 2*dy - dx plot(x0,y0) y=y0 for x from x0+1 to x1 if D > 0 y = y+1 plot(x,y) D = D + (2*dy-2*dx) else plot(x,y) D = D + (2*dy)Running this algorithm for from (0,1) to (6,4) yields the following differences with dx=6 and dy=3:

- D=2*3-6=0
**plot(0,1)**- Loop from 1 to 6
- x=1: D≤0:
**plot(1,1)**, D=6 - x=2: D>0: y=2,
**plot(2,2)**, D=6+(6-12)=0 - x=3: D≤0:
**plot(3,2)**, D=6 - x=4: D>0: y=3,
**plot(4,3)**, D=6+(6-12)=0 - x=5: D≤0:
**plot(5,3)**, D=6 - x=6: D>0: y=4,
**plot(6,4)**, D=6+(6-12)=0

- x=1: D≤0:

The result of this plot is shown to the right. The plotting can be viewed by plotting at the intersection of lines (blue circles) or filling in pixel boxes (yellow squares). Regardless, the plotting is the same.

Read more about this topic: Bresenham's Line Algorithm, Derivation

### Other articles related to "algorithm":

**Algorithm**s - 1960s

... Hoare 1962 - Ford–Fulkerson

**algorithm**developed by L ... Fulkerson 1962 - Bresenham's line

**algorithm**developed by Jack E ... Fedorenko 1965 - Cooley–Tukey

**algorithm**rediscovered by James Cooley and John Tukey 1965 - Levenshtein distance developed by Vladimir Levenshtein 1965 - Cocke–Younger–Kasami (CYK)

**algorithm**independently ...

**Algorithm**

... The Tomasulo

**algorithm**is a hardware

**algorithm**developed in 1967 by Robert Tomasulo from IBM ... This

**algorithm**differs from scoreboarding in that it utilizes register renaming ... The Tomasulo

**algorithm**also uses a common data bus (CDB) on which computed values are broadcast to all the reservation stations that may need it ...

**Algorithm**s For Barcode Decoding - Symbology Decoding

**Algorithm**

... The Symbology Decoding

**Algorithm**for barcode scanners is the first symbology-based

**algorithm**for decoding ... in the signal, whereas the traditional

**algorithm**relies on the maxima and minima ... The Symbology Decoding

**Algorithm**for Bar Code Scanners exhibited high resilience to blur and noise when tested on 1D Universal Product Codes ...

**Algorithm**- History: Development of The Notion of "

**algorithm**" - History After 1950

... toward further refinement of the definition of "

**algorithm**", and activity is on-going because of issues surrounding, in particular, foundations of mathematics (especially the Church–Turing thesis) and ... For more, see

**Algorithm**characterizations ...

**Algorithm**s

... Here are some random walk MCMC methods Metropolis–Hastings

**algorithm**Generates a random walk using a proposal density and a method for rejecting proposed moves ... A variation of the Metropolis–Hastings

**algorithm**that allows multiple trials at each point ... This allows the

**algorithm**to generally take larger steps at each iteration, which helps combat problems intrinsic to large dimensional problems ...