Midpoint Circle Generation Algorithm  

Just as a line drawing algorithm approximates infinite number of points on a line segment by only a finite number of pixels, a circle drawing algorithm approximates continuous circle by appropriately choosing a discrete set of points close to the circular arc.  One of the well known algorithms for circle generation is midpoint circle generation algorithm. The algorithm is a variant of Bresenham's line generation algorithm and uses a decision parameter to find out the closest pixel with the actual circle at each incremental step. Implicit equation of the circle given by 

(x - x_c)² + (y-y_c)² = r²

is used to define the decision parameter.  Here r is the radius and (x_c,y_c) is the centre of the circle.  Symmetry of the circle is fully exploited for its scan conversion.  Actually, we need to approximate the circle only in one octant, points in other seven octants similarly get approximated due to symmetry, as shown in Figure on the next page.  The decision parameter helps in deciding which pixels are closest to the circle boundary.  The algorithm is iterative in nature.  Next pixel position and decision parameter are computed iteratively.  Just as in Bresenham line drawing algorithm, one only needs to check the sign of the decision parameter to find out next pixel position.  This makes the implementation of the algorithm very easy.