Circle Generating Algorithm

A simple Circle drawing algorithm

 

Equation of circle is:​​ 

x2+y2=r2

Where​​ r= radius of the circle

Simple​​ algorithm​​ is to solve​​ the equation for y at unit x intervals using:

y=±r2-x2

But this algorithm is not efficient because:

  • Resulting circle has large gaps.

  • Calculations (multiply, square root) are not very efficient.

Eight-Way Symmetry

For efficient algorithm, we should consider that circle centered at (0, 0) have 8-way symmetry.

Mid-Point circle algorithm

In mid point algorithm, we use eight-way symmetry. So only ever calculate the points for the top right eighth of a circle(first octant)​​ and then use symmetry to get points​​ in other octant.

The mid-point circle drawing algorithm is developed by​​ Jack Bresenham.

Assume we have just plotted point​​ (xk, yk)​​ .​​ 

​​ The next point is a choice between ​​ (xk+1 , yk)​​ and​​ (xk+1 , yk-1)

We like to choose the point that is nearest to the actual circle using the below steps:

  • Find the midpoint pk​​ between above 2 pixels i.e. (​​ xk+1,yk-12​​ )

  • If pk​​ lies inside or on the circle then we plot the pixel​​ (xk+1 , yk)​​ , otherwise plot the pixel​​  (xk+1 , yk-1)​​ .

We can make the decision by evaluating the below function at the midpoint.

fx,y=x2+y2-r2

The equation evaluates as follows:

fx,y= <0,  if x,yis inside the circle boundary.=0,  if x,y is on the circle boundary>0,  if x,y is outside the circle boundary ​​ 

The decision variable defined as:

Pk=fxk+1, yk-12=(xk+1)2+( yk-12)2-r2

Similarly

Pk+1=fxk+1+1, yk+1-12=xk+1+12+ yk+1-122-r2

Pk+1=xk+1+12+ yk+1-122-r2  
Pk+1-Pk=xk+1+12+ yk+1-122-r2-[xk+12+ yk-122-r2]

Pk+1-Pk=xk+1+12-xk+12+ yk+1-122- yk-122

Pk+1-Pk=xk+12+2xk+1+1-xk+12+ yk+12-yk+1+14- yk2-yk+14

Pk+1=Pk+2xk+1+ yk+12-yk2- yk+1-yk+1

Case 1:​​ Pk<0,  so yk+1=yk

Pk+1=Pk+2xk+1+1​​ 

Case 2:​​ Pk>0,  so yk+1=yk-1

Pk+1=Pk+2xk+1-2(yk+1)+1​​ 

Calculation of initial decision variable (P0):

Pk=fxk+1, yk-12

Put k=0 .Also x0=0 and y0=r because we will start from point S having coordinate (0,​​ r​​ )​​ 

Then,

​​ ​​ P0=fx0+1, y0-12=f0+1, r-12

P0=f1, r-12=1+r-122-r2

P0=54-r1-r

 

 

Algorithm

  • Input radius r and circle center (xc,Yc) and obtain the first point on the circumference of circle.

 

x0=0;y0=r

  • Calculate the initial value of decision parameter.

 

P0=54-r1-r

  • At each xk​​ position , starting xk=0, perform the following test

Case 1:​​ Pk<0,    yk+1=yk

  ​​​​ Pk+1=Pk+2xk+1+1

​​ Case 2:​​ Pk>0,    yk+1=yk-1

Pk+1=Pk+2xk+1-2(yk+1)+1

  • Determine symmetry points in other seven octets.

  • Move each calculate pixel position (x,y) onto the circular path centered (xc,Yc) and plot the coordinate.

x=x+xc; y=y+yc

  • Repeat step (c )​​ through(e)​​ until​​ x​​ ≥​​ y

Example:​​ Draw the circle for radius =6 and centre (0,0)

Answer:​​ x=0, y=6, d=1-6=-5

Plot(x,y)

P

Xnew

Ynew

(0,6)

-2

1

6

(1,6)

3

2

6

(2,6)

0

3

5

(3,5)

9

4

5

(4,5)

12

5

4

 

Leave a Reply

avatar
  Subscribe  
Notify of