Home » Computer Graphics

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

    x2 + y2 - r2 = 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: (xk+1, yk) 
    and
    For B: (xk+1, yk-1)

Derivation

Then, the co-ordinates of mid-point be

MP= [((xk+1+xk+1)/2) , ((yk+yk-1) /2)]

(xk +1 , yk-1 / 2)

Now, put MP in the equation of circle x2 + y2 - r2 = 0

(xk +1 )2 + (yk-1 / 2)2 - r2

Let us define this equation as the decision parameter, using the mid-point MP:

Pk = ( xk+1 )2 + ( yk-1 / 2 )2 - r2                                                              -----(1)

 Let us define the successive decision parameter, Pk+1:

Pk+1 = ( xk+1 + 1 )2 + ( yk+1-1 / 2 )2 - r2                                                  -----(2)

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

Pk+1- Pk = ( xk+1+1 )2 + ( yk+1-1 / 2 )2- r2 - [ (xk+1)2 + ( yk-1 /2 )2 - r2]

Now put xk+1 = xk+1

             = (xk+1 + 1)2 + (yk+1-1 / 2)2 - r2 - [ (xk+1)2 + (yk-1 / 2)2 - r2 ]

             = (xk+1 + 1)2 - (xk+1)2 + ( yk+1-1 / 2 )2- ( yk-1 / 2 )2

 Pk+1= Pk + 2xk +3 + (yk+1)2 – yk+1- (yk)2 + yk

If Pk < 0:           yk+1 =  yk                (choose point A)

Pk+1= Pk+ 2xk + 3

If Pk > 0:           yk+1 = yk - 1     (choose point B)                                                      

Pk+1 = Pk + 2xk + 2yk + 5

Let us calculate the initial decision parameter (P0) 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 xk and yk, we get:

P0= ( 0 + 1 )2 + ( r-1 / 2 )2 - r2
P0 = 5/4 - r

If r is an integer:
P0 = 1 - r

If r is a floating point:
P0 = 5/4 - r

The Mid-Point Circle Drawing Algorithm

Step 1: Start.

Step 2: Declare x, y, r, xc , yc , P as variables, where (xc , yc) 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 Pk < 0 :
Pk+1=Pk+ 2xk+3

For Pk ≥ 0 :
Pk + 2xk+2yk+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.





Comments and Discussions

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





Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com some rights reserved.