Page 61 - DCAP313_LAB_ON_COMPUTER_GRAPHICS

Unit 4: Implementing Circle Algorithm

Notes
r = (x - ) h 2 + (y - ) k 2

2 ( 2 2 ) 2
(r) = (x - ) h + (y - ) k

2
r = (x - ) h 2 + (y - ) k 2
4.2 Midpoint Circle Drawing Algorithm

The midpoint circle drawing algorithm works on the same midpoint idea as the Bresenham’s line
algorithm. In the midpoint circle drawing algorithm, you decide the next pixel to be plotted based
on the position of the midpoint between the current and next successive pixel. The following
shows the current pixel (x n , y n ) and the possible next pixels, (x n + 1, y n ) and (x n + 1, y n – 1) to be
determined using the Midpoint circle drawing algorithm:

Figure 4.1: Midpoint Circle

You use the Midpoint circle drawing algorithm to determine the next pixel to be plotted
depending on the position of the midpoint D. If D is inside the circle, choose (x n + 1, y n ) as
the next pixel. If D is outside the circle, choose (x n + 1, y n – 1) as the next pixel. If D lies on the
circumference of the circle, choose either pixel.
The equation of the circle is given by g(x, y) as:
2
2
g(x, y) = x + y – R = 0
2
where R is the radius of the circle.
The g(x, y) is positive for a point outside the circle, negative for a point inside the circle, and
zero for a point on the circumference of the circle. These relations help confirm the position of
the midpoint D to determine the next pixel to be plotted on the circle.

4.2.1 Implement Midpoint Algorithm
The following steps of implementing midpoint algorithm:
1. Enter the centre of the circle, (x c , y c ), and its radius R.

2. Plot the pixel (x c , R) as the initial pixel.
3. To determine the next pixel, ensure the sign of g(D). You can determine this from the
value of g(x n + 1, y n – 1/2) denoted by p n :
P n = g(x n + 1, y n – 1/2) = (x n + 1) + (y n – ½) – R . 2
2
2

LOVELY PROFESSIONAL UNIVERSITY 55