×

Algorithms Tutorial

Searching Algorithms

Dynamic Programming

Graph Algorithms

Backtracking Algorithms

Recursion

Operating System Algorithms

Miscellaneous Topics

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.

Related Tutorials



Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.