# Midpoint Circle Algorithm

In this article, we are going to learn about **circle generating algorithms in computer graphics** i.e. **Midpoint circle algorithm**. Derivation of generating midpoint circle algorithm is also prescribed in this article.

Submitted by Abhishek Kataria, on August 04, 2018

## Midpoint circle Algorithm

This is an algorithm which is used to calculate the entire perimeter points of a circle in a first octant so that the points of the other octant can be taken easily as they are mirror points; this is due to circle property as it is symmetric about its center.

In this algorithm decision parameter is based on a circle equation. As we know that the equation of a circle is x^{2} +y^{2} =r^{2} when the centre is (0, 0).

Now let us define the function of a circle i.e.: **fcircle(x,y)= x ^{2} +y^{2} - r^{2} **

- If
**fcircle < 0**then**x**,**y**is inside the circle boundary. - If
**fcircle > 0**then**x**,**y**is outside the circle boundary. - If
**fcircle = 0**then**x**,**y**is on the circle boundary.

### Decision parameter

**p _{k} =fcircle(x_{k+1},y_{k-1/2})** where

**p**is a decision parameter and in this

_{k}**½**is taken because it is a midpoint value through which it is easy to calculate value of

**y**and

_{k}**y**.

_{k-1}I.e. **p _{k}= (x_{k+1})^{2}+ (y_{k-1/2})^{2}-r^{2}**

If **p _{k} <0** then midpoint is inside the circle in this condition we select

**y**is

**y**otherwise we will select next

_{k}**y**as

**y**for the condition of

_{k-1}**p**.

_{k}> 0### Conclusion

- If
**p**then_{k}< 0**y**, by this the plotting points will be_{k+1}=y_{k}**( x**. By this the value for the next point will be given as:_{k+1},y_{k})**P**_{k+1}=p_{k}+2(x_{k+1}) +1 - If
**p**then_{k}> 0**y**, by this the plotting points will be_{k+1}=y_{k-1}**(x**. By this the value of the next point will be given as:_{k+1}, y_{k-1})**P**_{k+1}=p_{k}+2(x_{k+1}) +1-2(y_{k+1})

### Initial decision parameter

**P _{0} = fcircle (1, r-1/2)**

This is taken because of **(x _{0}, y_{0}) = (0, r)**

i.e. **p _{0} =5/4-r or 1-r**, (

**1-r**will be taken if

**r**is integer)

### ALGORITHM

- In this the input radius
**r**is there with a centre**(x**. To obtain the first point_{c}, y_{c})**m**the circumference of a circle is centered on the origin as**(x**._{0},y_{0}) = (0,r) - Calculate the initial decision parameters which are:
**p**_{0}=5/4-r or 1-r - Now at each
**x**position starting_{k}**k=0**, perform the following task.

if**p**then plotting point will be_{k}< 0**( x**and_{k+1},y_{k})**P**_{k+1}=p_{k}+2(x_{k+1}) +1

else the next point along the circle is (x_{k+1}, y_{k-1}) and**P**_{k+1}=p_{k}+2(x_{k+1}) +1-2(y_{k+1}) - Determine the symmetry points in the other quadrants.
- Now move at each point by the given centre that is:
**x=x+x**_{c}**y=y+y**_{c} - At last repeat steps from 3 to 5 until the condition
**x>=y**.

Related Tutorials

- Introduction to Algorithms
- Introduction to Greedy Strategy in Algorithms
- Stability in sorting
- External Merge Sorting Algorithm
- Radix Sort and its Algorithm
- Bucket Sort Algorithm
- Bubble sort Algorithm, Flow Chart and C++ Code
- Insertion sort Algorithm, flowchart and C, C++ Code
- Merge Sort | One of the best sorting algorithms used for large inputs
- Binary Search in C, C++
- Randomized Binary Search
- Meta Binary Search | One-sided Binary Search
- Difference between Linear Search and Binary Search
- Binary Search in String
- Variants of Binary Search
- Sieve of Eratosthenes to find prime numbers
- Optimal Merge Pattern (Algorithm and Example)
- Given an array of n numbers, Check whether there is any duplicate or not
- Finding the missing number
- Find the number occurring an odd number of times
- Find the pair whose sum is closest to zero in minimum time complexity
- Find three elements in an array such that their sum is equal to given element K
- Bitonic Search Algorithm
- Check whether a number is Fibonacci or not
- Segregate even and odd numbers in minimum time complexity
- Find trailing zeros in factorial of a number
- Find Nearest Greatest Neighbours of each element in an array
- Interpolation search algorithm
- Floor and ceil of an element in an array using C++
- Two Elements whose sum is closest to zero
- Find a pair with a given difference
- Count number of occurrences (or frequency) in a sorted array
- Find a Fixed Point (Value equal to index) in a given array
- Find the maximum element in an array which is first increasing and then decreasing
- Dynamic Programming (Components, Applications and Elements)
- Algorithm for fractional knapsack problem
- Algorithm and procedure to solve a longest common subsequence problem
- Find the Nth Fibonacci number | C++
- Longest Common Subsequence using Dynamic programming (DP)
- Longest Increasing Subsequence using Dynamic programming (DP)
- Find the maximum sub-array sum using KADANE'S ALGORITHM
- Non-intersecting chords using Dynamic Programming (DP)
- Edit Distance using Dynamic Programming (DP)
- Finding Ugly Number using Dynamic Programming (DP)

- Backtracking (Types and Algorithms)
- 4 Queen's problem and solution using backtracking algorithm
- N Queen's problem and solution using backtracking algorithm
- Find the GCD (Greatest Common Divisor) of two numbers using EUCLID'S ALGORITHM
- Compute the value of A raise to the power B using Fast Exponentiation
- Implement First Come First Served (FCFS) CPU Scheduling Algorithm using C program
- Implementations of FCFS scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Non-Preemptive CPU scheduling algorithm using C++
- Implementation of Shortest Job First (SJF) Preemptive CPU scheduling algorithm using C++
- Implementation of Priority scheduling (Pre-emptive) algorithm using C++
- Implementation of Priority scheduling (Non Pre-emptive) algorithm using C++
- Implementation of Round Robin CPU Scheduling algorithm using C++
- Analysis of LRU page replacement algorithm and Belady's anomaly
- Branch and Bound
- Find the roots of a complex polynomial equation using Regula Falsi Method in C
- Divide and Conquer Paradigm (What it is, Its Applications, Pros and Cons)
- Strassen's Matrix Multiplication in algorithms
- Huffman Coding (Algorithm, Example and Time complexity)
- Tournament Tree and their properties
- Deterministic and Non Deterministic Algorithms
- Lower Bound Theory
- Non Recursive Tree Traversal Algorithm
- Line Drawing Algorithm
- P and NP problems and solutions | Algorithms
- 2 – 3 Trees Algorithm
- Reliability design problem
- Removing consecutive duplicates from a string
- Fast Exponentiation using Bitmasking
- Egg dropping problem using Dynamic Programming (DP)
- Wild card matching problem using Dynamic programming (DP)
- Compute sum of digits in all numbers from 1 to N for a given N
- Minimum jumps required using Dynamic programming (DP)
- Graph coloring problem's solution using backtracking algorithm
- Breadth First Search (BFS) and Depth First Search (DFS) Algorithms
- Travelling Salesman Problem
- Kruskal's (P) and Prim's (K) Algorithms
- Multistage graph problem with forward approach and backward approach algorithms
- Floyd Warshall algorithm with its Pseudo Code

Comments and Discussions!