Bresenham's Line Algorithm - Derivation - Algorithm

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


begin{align}
D & = f(x_0+1,y_0+1/2) - f(x_0,y_0) \ & = left - left \ & = A + frac{1}{2} B
end{align}

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

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":

Markov Chain Monte Carlo - Random Walk Algorithms
... 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 ...
Tomasulo 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 ...
Barcode Reader - New Algorithms For Barcode Decoding - Symbology Decoding Algorithm
... The Symbology Decoding Algorithm for barcode scanners is the first symbology-based algorithm for decoding ... detect transitions 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 ...
Timeline Of Algorithms - 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 - 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 ... For more, see Algorithm characterizations ...