Midpoint circle drawing algorithm | Code in C++ and Python

 In the previous post, we discuss Bresenham's circle drawing algorithm. Another incremental circle drawing algorithm, quite similar to Bresenham's technique, will be presented in this post. It uses the following function to check the spatial connection between an arbitrary point (x, y) and a circle of radius r centered at the origin. For the basics of a circle drawing algorithm, we have to know the general equation set of a circle. The functional equation is given below which is also helpful to find the distance variable of each pixel.

Advantages and Disadvantages of Midpoint circle drawing algorithm

The advantages and disadvantages of the midpoint circle drawing algorithm are quite similar to the advantages and disadvantages of Bresenham's circle drawing algorithm. Please read the Advantages and Disadvantages of Bresenham's circle drawing algorithm in this link. The main advantage of the midpoint circle drawing algorithm over Bresenham's circle drawing is that the computation time of this algorithm is quite faster. It is because the distance variable for the pixels of the midpoint circle drawing algorithm is less complex than Bresenham's circle drawing algorithm.

The distance variable for Bresenham's circle drawing algorithm is,

d = 3-2r

The distance variable for the Midpoint circle drawing algorithm is,

d = 1-r (here distance variable is 'p')

Midpoint Circle Drawing algorithm

The algorithm is exactly same as the Bresenham's circle drawing algorithm. (here 'p' is the distance variable of a pixel)

step 1: To begin, enter the radius of the circle as an input. The radius parameter has been set to 'r'.

step 2: set x->0, y->r, and the distance p-> 1 - r. 

step 3: Set the x and y coordinates in the frame as the starting points for creating the circle in the frame.(These variables are named 'xc' and 'yc' in the Python code). For the 'graphics.h' header file in C++, these variables are auto defaulted in the center position.) 

step 4: run a while loop until the condition is satisfied (condition: while the x is less than or equal to y). The while loop runs until the circle is drawn. ( until step 4, 5, and 6 is satisfied).

step 5: set pixel to the x and y points under step 2.

step 6: increase the x variable with 1 which is x->x+1

step 7: set conditions for the distance variable of each pixel for drawing a circle is 'p'. If the distance 'p' is less than zero than,

p-> p + 2x + 3

else,

p-> p + 2(x-y) + 5

y-> y - 1

Midpoint circle drawing algorithm using C++

#include <bits/stdc++.h>

using namespace std;

int main()

{

int r;

cin>>r;

int x=0, y=r, p=1-r;

while (x <=y)

{

setPixel(x, y);

if (p < 0)

{

p=p+2*x+3;

}

else

{

p=p+2*(x-y)+5;

y--;

}

x++;

}

}

NoteBook: The setPixel() function is the function of graphics.h header file. You will find it on the web.

Midpoint circle drawing algorithm using Python

from PIL import Image as img

def drawMidCircle1(xc, yc ,x, y,im):
    im.putpixel((x+xc, -y+yc), 0)
    im.putpixel((y+xc, x+yc), 0)
    im.putpixel((-y+xc, x+yc), 0)

def drawMidCircle2(xc, yc ,x, y,im):
    im.putpixel((x+xc, y+yc), 0)
    im.putpixel((-x+xc, y+yc), 0)
    im.putpixel((x+xc, -y+yc), 0)
    im.putpixel((-x+xc, -y+yc), 0)

def drawMidCircle3(xc, yc ,x, y,im):
    im.putpixel((y+xc, x+yc), 0)
    im.putpixel((-y+xc, x+yc), 0)
    im.putpixel((y+xc, -x+yc), 0)
    im.putpixel((-y+xc, -x+yc), 0)

def Midcircle(x_centre,y_centre,r)  :
    im = img.new(mode='1', size=(900,900),color=1)
    x = r
    y = 0

    if (r > 0):
        drawMidCircle1(x_centre, y_centre,x,y, im)
    P = 1 - r

    while x > y:

        y += 1

        if P <= 0:
            P = P + 2 * y + 1

        else:
            x -= 1
            P = P + 2 * y - 2 * x + 1

        if (x < y):
            break
        drawMidCircle2(x_centre, y_centre,x,y, im)

        if x != y:
            drawMidCircle3(x_centre, y_centre, x, y, im)
    im.save('Midpoint Circle Output.png')
    im.show()

if __name__=='__main__':
    Midcircle(500,400,300)

NoteBook: The implementation of the Midpoint circle drawing algorithm using Python is the same as mentioned in this post's algorithm. To easily draw a circle of this algorithm using python, we just exchange the position of x and y. 

Read Similar Posts:

1. Flood fill algorithm

2. Boundary fill algorithm

3. Scan line polygon filling algorithm

4. Bresenham's line algorithm code using python

5. Bresenham's line algorithm with example

6. DDA algorithm with examples

7. DDA algorithm code using python

8. Bresenham's circle drawing algorithm