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.
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_{k} is a decision parameter and in this ½ is taken because it is a midpoint value through which it is easy to calculate value of y_{k} and 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_{k} otherwise we will select next y as y_{k-1} for the condition of p_{k} > 0.
Conclusion
- If p_{k} < 0 then y_{k+1}=y_{k}, by this the plotting points will be ( x_{k+1} ,y_{k}). By this the value for the next point will be given as:
P_{k+1}=p_{k} +2(x_{k+1}) +1
- If p_{k} > 0 then y_{k+1}=y_{k-1}, by this the plotting points will be (x_{k+1}, y_{k-1}). By this the value of the next point will be given as:
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_{c} , y_{c}). To obtain the first point 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_{k} position starting k=0, perform the following task.
if p_{k} < 0 then plotting point will be ( x_{k+1} ,y_{k}) and
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.