Midpoint Circle Algorithm

The midpoint circle algorithm is probably the most computationally simple circle drawing algorithm out there. It shares a great deal in common with the Bressenham line drawing algorithm in that it simplifies the math of drawing from calculating each point of the equation for a circle (in this case x2 + y2 = r2) into a series of repetitions where for each repetition, the coordinates are adjusted to compensate for the change from step to step. This allows circles to be drawn using nothing but addition and subtraction.

The implementation below is just a derivative of the algorithm posted on the Wikipedia entry for the Midpoint circle algorithm. So far as I know it's perfectly sound in the version which I implemented based on the one provided by Wikipedia and the adjustments made to their algorithm based on the comments they provided.

```/// Draws four points relative to the given center point.
///
/// \li xCenter + X, yCenter + Y
/// \li xCenter + X, yCenter - Y
/// \li xCenter - X, yCenter + Y
/// \li xCenter - X, yCenter - Y
///
/// \param xCenter the x coordinate of the center point
/// \param yCenter the y coordinate of the center point
/// \param deltaX the difference between the xCenter coordinate and each pixel drawn
/// \param deltaY the difference between the yCenter coordinate and each pixel drawn
/// \param color the color to draw the pixels with.
inline void RGBFrameBuffer::plotFourQuadrants(int32_t xCenter, int32_t yCenter, int32_t deltaX, int32_t deltaY, RGB color)
{
setPixel(xCenter + deltaX, yCenter + deltaY, color);      // Ist      Quadrant
setPixel(xCenter - deltaX, yCenter + deltaY, color);      // IInd     Quadrant
setPixel(xCenter - deltaX, yCenter - deltaY, color);      // IIIrd    Quadrant
setPixel(xCenter + deltaX, yCenter - deltaY, color);      // IVth     Quadrant
}

/// Draws eight points relative to the given center point.
///
/// This function simply calls : plotFourQuadrants() twice
/// with deltaX and deltaY reversed in order to draw the 90 degree
/// offset version of the initial call. This makes it possible to draw
/// a circle by only calculating 45 degrees.
///
/// \param xCenter the x coordinate of the center point
/// \param yCenter the y coordinate of the center point
/// \param deltaX the difference between the xCenter coordinate and each pixel drawn
/// \param deltaY the difference between the yCenter coordinate and each pixel drawn
/// \param color the color to draw the pixels with.
inline void RGBFrameBuffer::plotEightPoints(int32_t cx, int32_t cy, int32_t deltaX, int32_t deltaY, Color color)
{
}

/// Implements the midpoint circle drawing algorithm which is
/// a bresenham style algorithm which is a "ddf". This algorithm
/// effectively implements x^2 + y^2 = r^2 using nothing but
///
/// \param centerX the x coordinate of the center of the circle.
/// \param centerY the y coordinate of the center of the circle.
/// \param color the color to paint the circle with.
void circle(int32_t centerX, int32_t centerY, int32_t radius, Color color)
{
if(!m_pixels)
return;

{
setPixel(centerX, centerY, color);
return;
}

int32_t y = 0;

while (x > y)
{
plotEightPoints(centerX, centerY, x, y, color);

error += y;
++y;
error += y;

if (error >= 0)
{
--x;
error -= x;
error -= x;
}
}
}
```
page revision: 3, last edited: 05 Oct 2010 06:42