I have already discussed about Bresenham circle drawing algorithm in the previous article, here in this article I will discuss about Mid-point circle drawing algorithm.
Mid-point Circle Drawing Algorithm
For a given radius r and center position (x_{0}, y_{0}), we can first set up our algorithm to calculate pixel positions around a circle path centered at the coordinate origin (0, 0). Then each calculated position (C, 4) is moved to its proper screen position by adding x_{C} to x and y_{C} to y along the circle section from x = 0 to x = y in the first quadrant, the slope of the curve varies from 0 to -1. Therefore, we can take unit steps in the position x direction over this octant and use a decision parameter to determine which of the two possible y positions is closer to the circle path at each step. Positions in the other seven octants are obtained by symmetry.
To apply the mid-point method, we define a circle function
\[f\left( x,y \right)={{x}^{2}}+{{y}^{2}}-{{r}^{2}}\]
Any point (x, y) on the boundary of the circle with radius r satisfies the equation. If the point is in the interior of the circle, the circle function is negative. And if the point outside the circle, the circle function is positive. To summarize the relative position of any point (x, y) can be determined by checking the sign of the circle function.
The mid point between two candidate pixels at sampling position x_{k+1}. Assuming we have just plotted the pixel (x_{k}, y_{k}), we next need to determine whether the pixel at position (x_{k+1}, y_{k}) or the one of position (x_{k+1}, y_{k-1}) is closer to the circle. Our decision parameter is the circle function at the mid-point between these two pixels.
\[{{d}_{k}}=f\left( {{x}_{k+1}},{{y}_{k}}-\frac{1}{2} \right)\]
\[\Rightarrow {{d}_{k}}={{\left( {{x}_{k+1}} \right)}^{2}}+{{\left( {{y}_{k}}-\frac{1}{2} \right)}^{2}}-{{r}^{2}}\]
If d_{k} < 0, this mid-point is inside the circle and the pixel on scan line y_{k} is closer to the circle boundary. Otherwise, the mid position is outside or on the circle boundary and we select the pixel on scan line y_{k-1}.
Successive decision parameters are obtained using incremental calculations. We obtain a recursive expression for the next decision parameter by evaluating the circle function at sampling position x_{k+1} +1 = x_{k+2}
\[{{d}_{k+1}}=f\left( {{x}_{k+1}}+1,{{y}_{k+1}}-\frac{1}{2} \right)\]
\[\Rightarrow {{d}_{k+1}}={{\left( {{x}_{k+1}}+1 \right)}^{2}}+{{\left( {{y}_{k+1}}-\frac{1}{2} \right)}^{2}}-{{r}^{2}}\]
\[\therefore {{d}_{k+1}}={{d}_{k}}+2\left( {{x}_{k}}+1 \right)+\left( y_{k+1}^{2}-y_{k}^{2} \right)-\left( {{y}_{k+1}}-{{y}_{k}} \right)+1\]
Where y_{k+1 }either y_{k} or y_{k-1 }depending on the sign of d_{k}.
Increments for obtaining d_{k+1 }are either 2x_{k+1 }+ 1 – 2y_{k+1}. Evaluation of the terms 2x_{k+1 }and 2y_{k+1 }are also be done incrementally as
\[2{{x}_{k+1}}=2{{x}_{k}}+2\]
\[2{{y}_{k+1}}=2{{y}_{k}}-2\]
At the start (0, r) these two terms have the values 0 and 2r, respectively. Each successive value is obtained by adding 2 to the previous value of 2y.
The initial decision parameter is obtained by evaluating the circle function at the start position (x_{0}, y_{0}) = (0, r)
\[i.e.,{{d}_{0}}=f\left( 1,r-\frac{1}{2} \right)=1+{{\left( r-\frac{1}{2} \right)}^{2}}-{{r}^{2}}=\frac{5}{4}-r\]
If the radius r is specified as an integer we can simply round d_{0} to d_{0} = 1 – r since all increments are integer.
Algorithm
Step 1. Start.
Step 2. Input radius r and circle center (x_{C}, y_{C}) and obtain the first point on the circumference of a circle centered on the origin as (x_{C}, y_{C}) = (0, r)
Step 3. Calculate the initial value of the decision parameters as d_{0} = 5/4 – r
Step 4. At each x_{k} position, starting k = 0, perform the following test:
If d_{k} < 0 the next point along the circle centered on (0, 0) is (x_{k+1}, y_{k}) and d_{k+1 }= d_{k} + 2x_{k+1 }+1. Otherwise, the next point along the circle is (x_{k} + 1, y_{k} – 1) and d_{k+1 }= d_{k} + 2x_{k+1 }+1 -2y_{k+1}, where 2x_{k+1 }= 2x_{k} + 2 and 2y_{k+1 }= 2y_{k} – 2
Step 5. Determine symmetry points in the other seven octants.
Step 6. Move each calculated pixel position (x, y) onto the circular path centered on (x_{0}, y_{0}) and plot the coordinate value x = x + x_{C}, y = y + y_{C}
Step 7. Repeat Step 4 through Step 6 until x ≥ y.
Step 8. End.
Example 01 |
Given a circle radius r = 5, we demonstrate the mid-point circle algorithm by determining position along the circle octant in the first quadrant from x = 0 to x = y. The initial value of the decision parameter is d_{0} = 1 – r = 1 – 5 = -4
For the circle centered on the coordinate origin, the initial point is (x_{0}, y_{0}) = (0, 5) and the initial increment terms for calculation 2 x_{0} = 0, 2 y_{0} = 2 X 5 = 10
Successive decision parameter values and positions along the circle path are calculated using the mid-point method as
k | d_{k} | (x_{k+1}, y_{k+1}) | 2x_{k+1} |
2y_{k+1} |
0 |
-4 | (1, 5) | 2 | 10 |
1 | -1 | (2, 5) | 4 |
1 |
2 |
8 | (3, 4) | 6 | 8 |
3 | 4 | (4, 3) | 8 |
6 |
Mid-point Circle Drawing Algorithm Implementation in C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
#include<stdio.h> #include<graphics.h> void drawcircle(int x0, int y0, int radius) { int x = radius; int y = 0; int err = 0; while (x >= y) { putpixel(x0 + x, y0 + y, 7); putpixel(x0 + y, y0 + x, 7); putpixel(x0 - y, y0 + x, 7); putpixel(x0 - x, y0 + y, 7); putpixel(x0 - x, y0 - y, 7); putpixel(x0 - y, y0 - x, 7); putpixel(x0 + y, y0 - x, 7); putpixel(x0 + x, y0 - y, 7); if (err <= 0) { y += 1; err += 2*y + 1; } if (err > 0) { x -= 1; err -= 2*x + 1; } } } int main() { int gdriver=DETECT, gmode, error, x, y, r; initgraph(&gdriver, &gmode, "c:\\turboc3\\bgi"); printf("Enter radius of circle: "); scanf("%d", &r); printf("Enter co-ordinates of center(x and y): "); scanf("%d%d", &x, &y); drawcircle(x, y, r); return 0; } |