Consider the midpoint (or Bresenham) algorithm for rasterizing lines given below: (1) Input (x 1, y 1) and (x 2, y 2) (2) y = y 1 (3) d = f(x 1+ 1, y 1+ ½) // f is the implicit form of a line (4) for x = x 1 to x 2 (5) do (6) plot(x,y) (7) if(d<0) (8) then (9) y = y + 1 (10) d = d + (y 1- y 2) + (x 2- x 1) (11) else (12) d = d + (y 1- y 2) (13) end (14) end Which statements are true? P: For a line with slope m>1, we should change the outer loop in line (4) to be over y. Q: Lines (10) and (12) update the decision variable d through an incremental evaluation of the line equation f. R: The algorithm fails if d is ever 0.
P and Q only
P is true: for slope m > 1, y is the major axis, so the algorithm iterates over y and correspondingly exchanges the roles of x and y. Q is true: writing the implicit line as \(f(x,y)=Ax+By+C\) with A=y1−y2 and B=x2−x1, an east step changes d by A and a northeast step changes it by A+B.
R is false. If d=0, the midpoint lies on the line and either neighboring pixel is a valid tie choice. The given code chooses the else branch. Therefore P and Q only are true.
Important Questions from Two Dimensional Geometric
Which of the following algorithms is not used for line clipping?
