Thursday, February 24, 2011

Midpoint circle algorithm (explanation)

The midpoint circle algorithm is an algorithm used to determine the points needed for drawing a circle. The algorithm is a variant of  Bresenham's line algorithm, and is thus sometimes known as Bresenham's circle algorithm, although not actually invented by Bresenham.

The midpoint method is used for deriving efficient scan-conversion algorithms to draw geometric curves on raster displays.
The method is general and is used to transform the nonparametric equation f(x,y) = 0, which describes the curve, into an algorithms that draws the curve.

-time consumption is high
-the distance between the pixels is not equal so we wont get smooth circle.

The algorithm starts accordingly with the circle equation x2 + y2 = r2. So, the center of the circle is located at (0,0). We consider first only the first octant and draw a curve which starts at point (r,0) and proceeds upwards and to the left, reaching the angle of 45°.
The "fast" direction here is the y direction. The algorithm always does a step in the positive y direction (upwards), and every now and then also has to do a step in the "slow" direction, the negative x direction.

refer : http://en.wikipedia.org/wiki/Midpoint_circle_algorithm