Which raster locations would be chosen by Bresenham's algorithm when scan…
2015
Which raster locations would be chosen by Bresenham's algorithm when scan converting a line from (1,1) to (8,5)?
- A.
\(\begin{array}{|c|c|} \hline x & y \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 3 \\ 5 & 4 \\ 6 & 4 \\ 7 & 5 \\ 8 & 6 \\ \hline \end{array}\) - B.
\(\begin{array}{|c|c|} \hline x & y \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 4 \\ 6 & 5 \\ 7 & 6 \\ 8 & 7 \\ \hline \end{array}\) - C.
\(\begin{array}{|c|c|} \hline x & y \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 3 \\ 6 & 4 \\ 7 & 4 \\ 8 & 5 \\ \hline \end{array}\) - D.
\(\begin{array}{|c|c|} \hline x & y \\ \hline 1 & 1 \\ 2 & 2 \\ 3 & 2 \\ 4 & 3 \\ 5 & 5 \\ 6 & 4 \\ 7 & 5 \\ 8 & 5 \\ \hline \end{array}\)
Attempted by 125 students.
Show answer & explanation
Correct answer: C
Key idea: use Bresenham's integer algorithm to choose which pixel row to plot as x increases. Compute dx = x2 - x1 and dy = y2 - y1, initialize the decision parameter p0 = 2*dy - dx, and at each step increment x by 1; if the decision parameter is nonnegative increment y and update p by 2*dy - 2*dx, otherwise keep y and update p by 2*dy.
Compute values: dx = 8 - 1 = 7, dy = 5 - 1 = 4. So 2*dy = 8 and 2*dx = 14.
Initialize: start at (1,1). p0 = 2*dy - dx = 8 - 7 = 1.
Step x = 1: plot (1,1). p = 1 ≥ 0, so increment y → 2 and update p → 1 - 6 = -5.
Step x = 2: plot (2,2). p = -5 < 0, so keep y = 2 and update p → -5 + 8 = 3.
Step x = 3: plot (3,2). p = 3 ≥ 0, so increment y → 3 and update p → 3 - 6 = -3.
Step x = 4: plot (4,3). p = -3 < 0, so keep y = 3 and update p → -3 + 8 = 5.
Step x = 5: plot (5,3). p = 5 ≥ 0, so increment y → 4 and update p → 5 - 6 = -1.
Step x = 6: plot (6,4). p = -1 < 0, so keep y = 4 and update p → -1 + 8 = 7.
Step x = 7: plot (7,4). p = 7 ≥ 0, so increment y → 5 and update p → 7 - 6 = 1.
Final step x = 8: plot (8,5).
Final raster points:
(1, 1)
(2, 2)
(3, 2)
(4, 3)
(5, 3)
(6, 4)
(7, 4)
(8, 5)