Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
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

Home » Algorithms

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.

Midpoint circle algo

In this algorithm decision parameter is based on a circle equation. As we know that the equation of a circle is x2 +y2 =r2 when the centre is (0, 0).

Now let us define the function of a circle i.e.: fcircle(x,y)= x2 +y2 - r2

  1. If fcircle < 0 then x, y is inside the circle boundary.
  2. If fcircle > 0 then x, y is outside the circle boundary.
  3. If fcircle = 0 then x, y is on the circle boundary.

Decision parameter

pk =fcircle(xk+1,yk-1/2) where pk is a decision parameter and in this ½ is taken because it is a midpoint value through which it is easy to calculate value of yk and yk-1.

I.e. pk= (xk+1)2+ (yk-1/2)2-r2

If pk <0 then midpoint is inside the circle in this condition we select y is yk otherwise we will select next y as yk-1 for the condition of pk > 0.

Conclusion

  1. If pk < 0 then yk+1=yk, by this the plotting points will be ( xk+1 ,yk). By this the value for the next point will be given as:
    Pk+1=pk +2(xk+1) +1
  2. If pk > 0 then yk+1=yk-1, by this the plotting points will be (xk+1, yk-1). By this the value of the next point will be given as:
    Pk+1=pk+2(xk+1) +1-2(yk+1)

Initial decision parameter

P0 = fcircle (1, r-1/2)

This is taken because of (x0, y0) = (0, r)

i.e. p0 =5/4-r or 1-r, (1-r will be taken if r is integer)

ALGORITHM

  1. In this the input radius r is there with a centre (xc , yc). To obtain the first point m the circumference of a circle is centered on the origin as (x0,y0) = (0,r).
  2. Calculate the initial decision parameters which are:
    p0 =5/4-r or 1-r
  3. Now at each xk position starting k=0, perform the following task.
    if pk < 0 then plotting point will be ( xk+1 ,yk) and
    Pk+1=pk +2(xk+1) +1
    else the next point along the circle is (xk+1, yk-1) and
    Pk+1=pk+2(xk+1) +1-2(yk+1)
  4. Determine the symmetry points in the other quadrants.
  5. Now move at each point by the given centre that is:
    x=x+xc
    y=y+yc
  6. At last repeat steps from 3 to 5 until the condition x>=y.





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



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 (2015-2018), Some rights reserved.