UGC NET CSE | December 2015 | Part 3 | Question: 69

Question

Which raster locations would be chosen by Bresenham's algorithm when scan converting a line from $(1,1)$ to $(8,5)$?

• A. $\begin{array}{|c|c|} \hline x & y \\ \hline  1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 3 \\ 5 & 4 \\ 6 & 4 \\ 7 &  5 \\ 8 & 6 \\ \hline \end{array}$
• B. $\begin{array}{|c|c|} \hline x & y \\ \hline  1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 5 \\ 7 &  6 \\ 8 & 7 \\ \hline \end{array}$
• C. $\begin{array}{|c|c|} \hline x & y \\ \hline  1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 3 \\ 6 & 4 \\ 7 &  4 \\ 8 & 5 \\ \hline \end{array}$
• D. $\begin{array}{|c|c|} \hline x & y \\ \hline  1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 5 \\ 6 & 4 \\ 7 &  5 \\ 8 & 5 \\ \hline \end{array}$

Answer 1

ans must be C 

short cut method  since line has to be drawn from (1,1) to (8,5)   choice A,B are out as they are ending up with 8,6 and 8,7

now in choice D after point 4,3 it is 5,5 i.e increment of 2 in y which is not as per rule of line drawing 

so we can safely say ans is C (because such unusual pattern is not seen in this)

for proper method bresenham's algo is

Step 1 − Input the two end-points of line, storing the left end-point in (x0,y0).

Step 2 − Plot the point (x0,y0).

Step 3 − Calculate the constants dx, dy, 2dy, and (2dy – 2dx) and get the first value for the decision parameter as    p0=2dy−dx

Step 4 − At each Xk along the line, starting at k = 0, perform the following test 

If pk < 0, the next point to plot is (xk +1,yk) and update value of parameter p as

pk+1=pk+2dy

Otherwise,

next point to plot is (xk+1 ,yk+1) and update value of parameter p as

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 Pk will be very similar, just the x and y in the equation gets interchanged.