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.





Comments and Discussions

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




Quick links
Latest articles, Internship, Members
New...
Coding problems, 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


Recommended posts
C Tips & Tricks, C++ Tips & Tricks
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distros of 2018
C programming optimization techniques
Differences b/w C & Embedded C?
Embedded C Interview Q. & A.
C programming tips for Embedded Development
Basic rules of writing a C program
Important points (rules) to remember while writing C/C++ program
Top 5 Websites for solving programming challenges
Read more...


Others...
Computer G.K. (MCQ)
Most viewed pages...
Categories...



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.