A line connects two points. It is a basic element in graphics. To draw a line, you need two points between which you can draw a line. In the following three algorithms, we refer the one point of line as
<span class="MathJax" id="MathJax-Element-1-Frame" tabindex="0" data-mathml="X0,Y0″ role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>X0,Y0 and the second point of line as <span class="MathJax" id="MathJax-Element-2-Frame" tabindex="0" data-mathml="X1,Y1″ role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>X1,Y1 .
DDA Algorithm
Digital Differential Analyzer (DDA) algorithm is the simple line generation algorithm which is explained step by step here.
Step 1 − Get the input of two end points <span class="MathJax" id="MathJax-Element-3-Frame" tabindex="0" data-mathml="(X0,Y0)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(X0,Y0) and <span class="MathJax" id="MathJax-Element-4-Frame" tabindex="0" data-mathml="(X1,Y1)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(X1,Y1) .
Step 2 − Calculate the difference between two end points.
dx = X1 - X0 dy = Y1 - Y0
Step 3 − Based on the calculated difference in step-2, you need to identify the number of steps to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y coordinate.
if (absolute(dx) > absolute(dy)) Steps = absolute(dx); else Steps = absolute(dy);
Step 4 − Calculate the increment in x coordinate and y coordinate.
Xincrement = dx / (float) steps; Yincrement = dy / (float) steps;
Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and complete the drawing of the line.
for(int v=0; v < Steps; v++) { x = x + Xincrement; y = y + Yincrement; putpixel(Round(x), Round(y)); }
Bresenham’s Line Generation
The Bresenham algorithm is another incremental scan conversion algorithm. The big advantage of this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and at each step choose between two different y coordinates.
For example, as shown in the following illustration, from position (2, 3) you need to choose between (3, 3) and (3, 4). You would like the point that is closer to the original line.
At sample position <span class="MathJax" id="MathJax-Element-5-Frame" tabindex="0" data-mathml="Xk+1,” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Xk+1, the vertical separations from the mathematical line are labelled as <span class="MathJax" id="MathJax-Element-6-Frame" tabindex="0" data-mathml="dupper” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dupper and <span class="MathJax" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="dlower” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dlower .d
<span class="MathJax" id="MathJax-Element-7-Frame" tabindex="0" data-mathml="dlower” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>lower .
From the above illustration, the y coordinate on the mathematical line at <span class="MathJax" id="MathJax-Element-8-Frame" tabindex="0" data-mathml="xk+1″ role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>xk+1 is −
Y = m(<span class="MathJax" id="MathJax-Element-9-Frame" tabindex="0" data-mathml="Xk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Xk +1) + b
So, <span class="MathJax" id="MathJax-Element-10-Frame" tabindex="0" data-mathml="dupper” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dupper and <span class="MathJax" id="MathJax-Element-11-Frame" tabindex="0" data-mathml="dlower” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dlower are given as follows −
<span class="MathJax" id="MathJax-Element-12-Frame" tabindex="0" data-mathml="dlower=y−yk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dlower=y−yk
<span class="MathJax" id="MathJax-Element-13-Frame" tabindex="0" data-mathml="=m(Xk+1)+b−Yk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>=m(Xk+1)+b−Yk
and
<span class="MathJax" id="MathJax-Element-14-Frame" tabindex="0" data-mathml="dupper=(yk+1)−y” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dupper=(yk+1)−y
<span class="MathJax" id="MathJax-Element-15-Frame" tabindex="0" data-mathml="=Yk+1−m(Xk+1)−b” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>=Yk+1−m(Xk+1)−b
You can use these to make a simple decision about which pixel is closer to the mathematical line. This simple decision is based on the difference between the two pixel positions.
<span class="MathJax MathJax_FullWidth" id="MathJax-Element-16-Frame" tabindex="0" data-mathml="dlower−dupper=2m(xk+1)−2yk+2b−1″ role=”presentation” style=”box-sizing: border-box; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; display: table-cell !important; width: 10000em !important;”>dlower−dupper=2m(xk+1)−2yk+2b−1
Let us substitute m with dy/dx where dx and dy are the differences between the end-points.
<span class="MathJax MathJax_FullWidth" id="MathJax-Element-17-Frame" tabindex="0" data-mathml="dx(dlower−dupper)=dx(2dydx(xk+1)−2yk+2b−1)” role=”presentation” style=”box-sizing: border-box; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; display: table-cell !important; width: 10000em !important;”>dx(dlower−dupper)=dx(2dydx(xk+1)−2yk+2b−1)
<span class="MathJax MathJax_FullWidth" id="MathJax-Element-18-Frame" tabindex="0" data-mathml="=2dy.xk−2dx.yk+2dy+2dx(2b−1)” role=”presentation” style=”box-sizing: border-box; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; display: table-cell !important; width: 10000em !important;”>=2dy.xk−2dx.yk+2dy+2dx(2b−1)
<span class="MathJax" id="MathJax-Element-19-Frame" tabindex="0" data-mathml="=2dy.xk−2dx.yk+C” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>=2dy.xk−2dx.yk+C
So, a decision parameter <span class="MathJax" id="MathJax-Element-20-Frame" tabindex="0" data-mathml="Pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Pk for the kth step along a line is given by −
<span class="MathJax" id="MathJax-Element-21-Frame" tabindex="0" data-mathml="pk=dx(dlower−dupper)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk=dx(dlower−dupper)
<span class="MathJax" id="MathJax-Element-22-Frame" tabindex="0" data-mathml="=2dy.xk−2dx.yk+C” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>=2dy.xk−2dx.yk+C
The sign of the decision parameter <span class="MathJax" id="MathJax-Element-23-Frame" tabindex="0" data-mathml="Pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Pk is the same as that of <span class="MathJax" id="MathJax-Element-24-Frame" tabindex="0" data-mathml="dlower−dupper” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>dlower−dupper .
If <span class="MathJax" id="MathJax-Element-25-Frame" tabindex="0" data-mathml="pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk is negative, then choose the lower pixel, otherwise choose the upper pixel.
Remember, the coordinate changes occur along the x axis in unit steps, so you can do everything with integer calculations. At step k+1, the decision parameter is given as −
<span class="MathJax" id="MathJax-Element-26-Frame" tabindex="0" data-mathml="pk+1=2dy.xk+1−2dx.yk+1+C” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk+1=2dy.xk+1−2dx.yk+1+C
Subtracting <span class="MathJax" id="MathJax-Element-27-Frame" tabindex="0" data-mathml="pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk from this we get −
<span class="MathJax MathJax_FullWidth" id="MathJax-Element-28-Frame" tabindex="0" data-mathml="pk+1−pk=2dy(xk+1−xk)−2dx(yk+1−yk)” role=”presentation” style=”box-sizing: border-box; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative; display: table-cell !important; width: 10000em !important;”>pk+1−pk=2dy(xk+1−xk)−2dx(yk+1−yk)
But, <span class="MathJax" id="MathJax-Element-29-Frame" tabindex="0" data-mathml="xk+1″ role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>xk+1 is the same as <span class="MathJax" id="MathJax-Element-30-Frame" tabindex="0" data-mathml="(xk)+1″ role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(xk)+1 . So −
<span class="MathJax" id="MathJax-Element-31-Frame" tabindex="0" data-mathml="pk+1=pk+2dy−2dx(yk+1−yk)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk+1=pk+2dy−2dx(yk+1−yk)
Where, <span class="MathJax" id="MathJax-Element-32-Frame" tabindex="0" data-mathml="Yk+1–Yk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Yk+1–Yk is either 0 or 1 depending on the sign of <span class="MathJax" id="MathJax-Element-33-Frame" tabindex="0" data-mathml="Pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Pk .
The first decision parameter <span class="MathJax" id="MathJax-Element-34-Frame" tabindex="0" data-mathml="p0″ role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>p0 is evaluated at <span class="MathJax" id="MathJax-Element-35-Frame" tabindex="0" data-mathml="(x0,y0)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(x0,y0) is given as −
<span class="MathJax" id="MathJax-Element-36-Frame" tabindex="0" data-mathml="p0=2dy−dx” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>p0=2dy−dx
Now, keeping in mind all the above points and calculations, here is the Bresenham algorithm for slope m < 1 −
Step 1 − Input the two end-points of line, storing the left end-point in <span class="MathJax" id="MathJax-Element-37-Frame" tabindex="0" data-mathml="(x0,y0)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(x0,y0) .
Step 2 − Plot the point <span class="MathJax" id="MathJax-Element-38-Frame" tabindex="0" data-mathml="(x0,y0)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(x0,y0) .
Step 3 − Calculate the constants dx, dy, 2dy, and (2dy – 2dx) and get the first value for the decision parameter as −
<span class="MathJax" id="MathJax-Element-39-Frame" tabindex="0" data-mathml="p0=2dy−dx” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>p0=2dy−dx
Step 4 − At each <span class="MathJax" id="MathJax-Element-40-Frame" tabindex="0" data-mathml="Xk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Xk along the line, starting at k = 0, perform the following test −
If <span class="MathJax" id="MathJax-Element-41-Frame" tabindex="0" data-mathml="pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk < 0, the next point to plot is <span class="MathJax" id="MathJax-Element-42-Frame" tabindex="0" data-mathml="(xk+1,yk)” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>(xk+1,yk) and
<span class="MathJax" id="MathJax-Element-43-Frame" tabindex="0" data-mathml="pk+1=pk+2dy” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk+1=pk+2dy
Otherwise,
<span class="MathJax" id="MathJax-Element-44-Frame" tabindex="0" data-mathml="pk+1=pk+2dy−2dx” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; font-size: 15px; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>pk+1=pk+2dy−2dx
Step 5 − Repeat step 4 (dx – 1) times.
For m > 1, find out whether you need to increment x while incrementing y each time.
After solving, the equation for decision parameter <span class="MathJax" id="MathJax-Element-45-Frame" tabindex="0" data-mathml="Pk” role=”presentation” style=”box-sizing: border-box; display: inline; line-height: normal; text-align: left; word-spacing: normal; word-wrap: normal; white-space: nowrap; float: none; direction: ltr; max-width: none; max-height: none; min-width: 0px; min-height: 0px; border: 0px; padding: 0px; margin: 0px; position: relative;”>Pk will be very similar, just the x and y in the equation gets interchanged.