UGC NET CSE | June 2016 | Part 3 | Question: 13

Question

Consider the Breshenman's circle generation algorithm for plotting a circle with centre (0,0) and radius 'r' unit 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 updates decision parameter $p_{i+1}$ for $p \geq 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$

Answer 1

ans is B 

 

below  D is the decision parameter (given as  Pi ,Pi+1 in the question )

another link 

Bresenham’s Algorithm

We cannot display a continuous arc on the raster display. Instead, we have to choose the nearest pixel position to complete the arc.

From the following illustration, you can see that we have put the pixel at (X, Y) location and now need to decide where to put the next pixel − at N (X+1, Y) or at S (X+1, Y-1).

This can be decided by the decision parameter d.

• If d <= 0, then N(X+1, Y) is to be chosen as next pixel.
• If d > 0, then S(X+1, Y-1) is to be chosen as the next pixel.

Algorithm

Step 1 − Get the coordinates of the center of the circle and radius, and store them in x, y, and R respectively. Set P=0 and Q=R.

Step 2 − Set decision parameter D = 3 – 2R.

Step 3 − Repeat through step-8 while X < Y.

Step 4 − Call Draw Circle (X, Y, P, Q).

Step 5 − Increment the value of P.

Step 6 − If D < 0 then D = D + 4x + 6.

Step 7 − Else Set Y = Y - 1, D = D + 4(X-Y) + 10.

Step 8 − Call Draw Circle (X, Y, P, Q).