Consider the Breshenham’s circle generation algorithm for plotting a circle…
2016
Consider the Breshenham’s circle generation algorithm for plotting a circle with centre (0, 0) and radius \(‘r’\) units in first quadrant. If the current point is \((x_i , y_i )\) and decision parameter is \(p_i\) then what will be the next point \((x_i + 1, y_i + 1)\) and updated decision parameter \(p_i + 1\) for \(p_i ≥ 0\) ?
- A.
\(x_{i+1}=x_i+1; \\ y_{i+1}=y_i; \\ p_{i+1}=p_i+4x_i+6\) - B.
\(x_{i+1}=x_i+1; \\ y_{i+1}=y_i-1; \\ p_{i+1}=p_i+4(x_i-y_i)+10\) - C.
\(x_{i+1}=x_i; \\ y_{i+1}=y_i-1; \\ p_{i+1}=p_i+4(x_i-y_i)+6\) - D.
\(x_{i+1}=x_i-1; \\ y_{i+1}=y_i; \\ p_{i+1}=p_i+4x_i+10\)
Attempted by 94 students.
Show answer & explanation
Correct answer: B
Answer: Next point is (x_{i+1} = x_i + 1, y_{i+1} = y_i - 1) and the updated decision parameter is p_{i+1} = p_i + 4(x_i - y_i) + 10.
Explanation:
When p_i ≥ 0 the midpoint test indicates the midpoint is on or outside the circle boundary, so the pixel choice moves diagonally: increment x by 1 and decrement y by 1.
Compute the change in the decision function for that move. The incremental change Δp = f(x_i+1, y_i-1) - f(x_i, y_i) evaluates to 4(x_i - y_i) + 10, so p_{i+1} = p_i + 4(x_i - y_i) + 10.
For completeness, if p_i < 0 the algorithm instead chooses (x_i+1, y_i) and updates p_{i+1} = p_i + 4x_i + 6.
Therefore, for p_i ≥ 0 the correct next pixel and update are (x_i+1, y_i-1) and p_i + 4(x_i - y_i) + 10.