2.1k views

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

1.  x y 1 2 3 4 5 6 7 8 1 2 3 3 4 4 5 6
2.  x y 1 2 3 4 5 6 7 8 1 2 2 3 4 5 6 7
3.  x y 1 2 3 4 5 6 7 8 1 2 2 3 3 4 4 5
4.  x y 1 2 3 4 5 6 7 8 1 2 2 3 5 4 5 5

recategorized | 2.1k views

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.

by Boss
edited