Consider the Breshenham’s line generation algorithm for a line with gradient…
2016
Consider the Breshenham’s line generation algorithm for a line with gradient greater than one, current point \((𝑥_𝑖,𝑦_𝑖)\) and decision parameter, \(𝑑_𝑖\). The next point to be plotted \( (𝑥_𝑖+1,𝑦_𝑖+1) \) and updated decision parameter, \(𝑑_𝑖\) +1, for \(𝑑_𝑖<0\) are given as _______.
- A.
\(x_{ i+1} = x _{i +1} \\ y_{i+1} = y_{i} \\ d_{i+1} = d_{i} + 2 dy\) - B.
\(x _{i+1} = x _{i} \\ y_{i+1} = y_{i + 1} \\ d_{i+1} = d_{i} + 2 dx\) - C.
\(x _{i+1} = x_{ i} \\ y_{i+1} = y_{i + 1} \\ d_{i+1} = d_{i} + 2 (dx – dy)\) - D.
\(x_{ i+1} = x_{ i + 1} \\ y_{i+1} = y_{i + 1} \\ d_{i+1} = d_{i} + 2 (dy – dx)\)
Attempted by 146 students.
Show answer & explanation
Correct answer: B
Key idea: For a line with slope greater than 1 (steep line), we step in y at each iteration and decide whether to increment x as well.
Decision parameter: initialize d = 2*dx - dy, where dx = x2 - x1 and dy = y2 - y1.
If current decision parameter d < 0: next point is (xi, yi+1). Update the decision parameter by d = d + 2*dx.
If current decision parameter d >= 0: next point is (xi+1, yi+1). Update the decision parameter by d = d + 2*(dx - dy).
Therefore, for the case d < 0 the next plotted point and updated parameter are: (xi, yi+1) and d + 2*dx.