Which of the following statements is correct about the pixels generated for…
2022
Which of the following statements is correct about the pixels generated for the line segment (20, 10) to (25, 14) using Bresenham's line drawing algorithm?
- A.
There should be a total of seven pixels including both end points.
- B.
There should be a total of five pixels including both end points.
- C.
The pixel (23, 12) should be generated by this algorithm for this line segment.
- D.
The initial value of the decision variable d = 6.
Attempted by 19 students.
Show answer & explanation
Correct answer: C
Bresenham's line-drawing algorithm plots a raster line using only integer arithmetic. For a segment whose slope lies between 0 and 1 (here dx = x2 - x1 is greater than or equal to dy = y2 - y1, both positive), it advances x by exactly one pixel at every step and uses an integer decision parameter p to decide whether y also advances. Starting from p0 = 2*dy - dx: if p is negative, y is held at its current value and p is updated as p = p + 2*dy; if p is zero or positive, y is incremented by 1 and p is updated as p = p + 2*dy - 2*dx.
Compute dx = 25 - 20 = 5 and dy = 14 - 10 = 4, so the initial decision parameter is p0 = 2*dy - dx = 2(4) - 5 = 3.
Starting pixel: x = 20, y = 10 (the segment's first endpoint), with p0 = 3.
x = 21: since p0 = 3 is >= 0, y increments to 11, giving pixel (21, 11); update p1 = p0 + 2*dy - 2*dx = 3 + 8 - 10 = 1.
x = 22: since p1 = 1 is >= 0, y increments to 12, giving pixel (22, 12); update p2 = p1 + 2*dy - 2*dx = 1 + 8 - 10 = -1.
x = 23: since p2 = -1 is < 0, y stays at 12, giving pixel (23, 12); update p3 = p2 + 2*dy = -1 + 8 = 7.
x = 24: since p3 = 7 is >= 0, y increments to 13, giving pixel (24, 13); update p4 = p3 + 2*dy - 2*dx = 7 + 8 - 10 = 5.
x = 25: since p4 = 5 is >= 0, y increments to 14, giving pixel (25, 14), the segment's second endpoint.
Since dx >= dy, exactly one pixel is plotted per unit increase in x, so this segment must contain exactly dx + 1 = 6 pixels in total: (20,10), (21,11), (22,12), (23,12), (24,13), (25,14). This matches the trace above, rules out totals of seven or five, and confirms the true initial decision parameter is 2*dy - dx = 3, not 6.
The statement that holds for this segment is that the pixel (23, 12) is generated by the algorithm - confirmed directly at the x = 23 step of the trace above, where the decision parameter is negative and y is held at 12.