Circle Generating algorithm Properties of the Circle

Circle Generating algorithm Properties of the Circle

Circle is defined as a set of points that are all at a given distance r from a center position (Xc,Yc). This distance relationship is expressed by the Pythagorean theorem in Cartesian coordinates as

(X-Xc)² +(Y-Yc)²=r²

Bresenham’s line algorithm for raster display is adapted to circle generation by setting up the decision parameters for finding the closest pixel for each sampling step.

A method for direct distances comparison is to test the halfway position between two pixels, to determine if this midpoint is inside or outside the circle boundary. This method is more easy . For an integer circle radius, the midpoint approach generates the same pixel position.

Midpoint Circle Algorithm

1.Input radius r and circle center (xc,yc) and obtain the first point on the circumference of a circle centered on the origin as

(x0,y0)=(0,r)

2.Calculate the initial value of the decision parameter as P0=5/4 –r

3 At each xk position, starting at k=0,perform the following test:

if Pk<0 , then next point along the circle centered on (0,0) is (xk+1,yk) and

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

otherwise the next point along the circle is (xk+1,yk-1) and

Pk+1=Pk + 2xk+1 +1 – 2yk+1

where 2xk+1 =2xk + 2, 2yk+1=2yk-2

4. Determine the symmetry points in the other seven octants

5.Move each calculated position(x,y) onto the circular path centered on (xc,yc) and plot the coordinate values x=x+xc,y=y+yc

6.Repeat steps 3 to 5 until x > = y