Mid-point Circle Drawing Algorithm


Computer Graphics / Thursday, November 8th, 2018
(Last Updated On: November 8, 2018)

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 (x0, y0), 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 xC to x and yC 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.

mid-point01

mid-point02

The mid point between two candidate pixels at sampling position xk+1. Assuming we have just plotted the pixel (xk, yk), we next need to determine whether the pixel at position (xk+1, yk) or the one of position (xk+1, yk-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 dk < 0, this mid-point is inside the circle and the pixel on scan line yk 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 yk-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 xk+1 +1 = xk+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 yk+1 either yk or yk-1 depending on the sign of dk.

Increments for obtaining dk+1 are either 2xk+1 + 1 – 2yk+1. Evaluation of the terms 2xk+1 and 2yk+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 (x0, y0) = (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 d0 to d0 = 1 – r since all increments are integer.

Algorithm

Step 1. Start.

Step 2. Input radius r and circle center (xC, yC) and obtain the first point on the circumference of a circle centered on the origin as (xC, yC) = (0, r)

Step 3. Calculate the initial value of the decision parameters as d0 = 5/4 – r

Step 4. At each xk position, starting k = 0, perform the following test:

If dk < 0 the next point along the circle centered on (0, 0) is (xk+1, yk) and dk+1 = dk + 2xk+1 +1. Otherwise, the next point along the circle is (xk + 1, yk – 1) and dk+1 = dk + 2xk+1 +1 -2yk+1, where 2xk+1 = 2xk + 2 and 2yk+1 = 2yk – 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 (x0, y0) and plot the coordinate value x = x + xC, y = y + yC

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 d0 = 1 – r = 1 – 5 = -4

For the circle centered on the coordinate origin, the initial point is (x0, y0) = (0, 5) and the initial increment terms for calculation 2 x0 = 0, 2 y0 = 2 X 5 = 10

Successive decision parameter values and positions along the circle path are calculated using the mid-point method as

 

k dk (xk+1, yk+1) 2xk+1

2yk+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

 

<<Previous

Leave a Reply

Your email address will not be published. Required fields are marked *