# Mid-Point Circle Algorithm in Computer Graphics

**Computer Graphics | Mid-Point Circle Algorithm**: In this tutorial, we are going to learn about the mid-point circle drawing algorithm. Here, we will be studying about its algorithm and how it is implemented in the drawing of a circle. Apart from that, the pros and cons of this algorithm are also mentioned.

Submitted by Monika Sharma, on April 24, 2020

## What is a circle?

A circle is defined as a set of points that all are the same distance from a common point known as the center and the distance from the center of the circle to any point on its circumference is called a radius.

It is an eight-way symmetric figure which can be divided into four quadrants and each quadrant has two octants. This symmetry helps in the implementation of any circle drawing algorithm.

## Introduction to Mid-Point Circle Drawing Algorithm

In computer graphics, the **mid-point circle drawing algorithm** is used to calculate all the perimeter points of a circle. In this algorithm, the mid-point between the two pixels is calculated which helps in calculating the decision parameter.

The value of the decision parameter will decide which pixel should be chosen for drawing the circle.

This algorithm only calculates the points for one octant and the points for other octants are generated using the eight-way symmetry for the circle.

### Working of the Mid-Point Circle Drawing Algorithm

The algorithm works in the following way:

Suppose a mid-point with coordinates **(x', y')** is put in the general equation of the circle is

x^{2 }+ y^{2 }- r^{2 }= 0

gives these three values,

- If
**0**: the given point lies on the circle boundary, then any pixel can be chosen. - If
**< 0**: the given point lies inside the circle boundary, then the upper pixel can be chosen. - If
**> 0**: the given point lies outside the circle boundary, then the lower pixel is chosen.

Let there be two pixels:

One pixel which is outside (**A**), and the other pixel which is inside (**B**) the circle boundary,

Let their coordinates be:

For A: (x_{k}+1, y_{k}) and For B: (x_{k}+1, y_{k}-1)

**Derivation**

Then, the co-ordinates of mid-point be

M_{P}= [((x_{k}+1+x_{k}+1)/2) , ((y_{k}+y_{k}-1) /2)]

(x_{k }+1 , y_{k}-1 / 2)

Now, put M_{P} in the equation of circle x^{2 }+ y^{2 }- r^{2 }= 0

(x_{k }+1 )^{2} + (y_{k}-1 / 2)^{2 }- r^{2}

Let us define this equation as the decision parameter, using the mid-point M_{P}:

P_{k }= ( x_{k}+1 )^{2} + ( y_{k}-1 / 2 )^{2 }- r^{2 } -----(1)

Let us define the successive decision parameter, P_{k+1}:

P_{k+1 }= ( x_{k+1 }+ 1 )^{2} + ( y_{k+1}-1 / 2 )^{2 }- r^{2} -----(2)

Subtracting eq.(1) from eq.(2);

P_{k+1}- P_{k} = ( x_{k+1}+1 )^{2} + ( y_{k+1}-1 / 2 )^{2}- r^{2 }- [ (x_{k}+1)^{2} + ( y_{k}-1 /2 )^{2 }- r^{2}]

Now put x_{k+1 }= x_{k}+1

= (x_{k+1 }+ 1)^{2} + (y_{k+1}-1 / 2)^{2 }- r^{2 }- [ (x_{k}+1)^{2} + (y_{k}-1 / 2)^{2 }- r^{2 }]

= (x_{k+1 }+ 1)^{2 }- (x_{k}+1)^{2 }+ ( y_{k+1}-1 / 2 )^{2}- ( y_{k}-1 / 2 )^{2}

P_{k+1}= P_{k} + 2x_{k }+3 + (y_{k+1})^{2 }– y_{k+1}- (y_{k})^{2} + y_{k}

If P_{k }< 0: y_{k+1 }= y_{k }(choose point A)

P_{k+1}= P_{k}+ 2x_{k }+ 3

If P_{k }> 0: y_{k}+1 = y_{k }- 1 (choose point B)^{ }

P_{k+1 }= P_{k }+ 2x_{k }+ 2y_{k }+ 5

Let us calculate the initial decision parameter (P_{0}) where the initial points will be defined as (0, r) [which is the first point to be plotted of the first octant].

On putting these coordinates in eq. (1) in place of x_{k }and y_{k}, we get:

P_{0}= ( 0 + 1 )^{2} + ( r-1 / 2 )^{2 }- r^{2}P_{0 }= 5/4 - r

If r is an integer:

P_{0 }= 1 - r

If r is a floating point:

P_{0 }= 5/4 - r

### The Mid-Point Circle Drawing Algorithm

Step 1: Start.

Step 2: Declare x, y, r, x_{c }, y_{c }, P as variables, where (x_{c }, y_{c}) are coordinates of the center.

Step 3: Put x = 0 and y = r

Step 4: Repeat the steps while x ≤ y;

Step 5: Plot (x, y).

Step 6: if (P < 0):

Set P = P + 2x + 3

else if (P >= 0):

Set P = P + 2(x-y) + 5

y = y - 1

Step 7: Do x = x + 1

Step 8: End

**Formulas used:**

**For P _{k }< 0 :**

P

_{k+1}=P

_{k}+ 2x

_{k}+3

**For P _{k }≥ 0 :**

P

_{k }+ 2x

_{k}+2y

_{k}+5

**Advantages:**

- The mid-point circle algorithm is an efficient algorithm in drawing a circle.
- The implementation of the algorithm is easy from the programmer’s point of view.

**Disadvantages:**

- The time consumption of this algorithm is high.

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.