Question

Consider the midpoint (or Bresenham) algorithm for rasterizing lines given below:

(1) Input (x₁, y₁) and (x₂, y₂)
(2) y = y₁
(3) d = f(x₁ + 1, y₁ + ½) // 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₁ - y₂) + (x₂ - x₁)
(11) else
(12) d = d + (y₁ - y₂)
(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.


A. Q and R only
B. P only
C. P and Q only
D. P, Q and R

Answer 1

The correct statements are P, which suggests iterating over y for lines with a slope greater than 1, and Q, which discusses the incremental evaluation of the decision variable. Statement R is false, as the algorithm can handle a decision variable of 0.The correct answer is C, statements P and Q only are true

Step-by-step explanation:

When considering the midpoint (or Bresenham) algorithm for rasterizing lines, three statements are made.

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.

Statement P is true because for lines with a slope greater than 1, it's more efficient to iterate over y to minimize the number of points that need to be plotted. Statement Q is also true as lines (10) and (12) provide incremental updates to the decision variable, which reflect the implicit line equation f. However, statement R is false because the algorithm does not fail if d is 0; in fact, the decision variable d being 0 is a valid state within the algorithm that signifies the next point to plot is exactly on the line, so no adjustment is needed.

The correct answer is C, statements P and Q only are true