Mid-Point Cirle Drawing Algorithm

1. PRESTIGE INSTITUTE OF MANAGEMENT GWALIOR

2. PRESENTATION ON MID-POINT CIRCLE DRAWING PRESENTED BY: NEHA KAURAV HIMANSHI GUPTA CLASS: BCA 3 rd SEM.

3. ABOUT CIRCLE A circle is all points in the same plane that lie at an equal distance from a center point. The circle is only composed of the points on the border. The distance between the midpoint and the circle border is called the radius. A line segment that has the endpoints on the circle and passes through the midpoint is called the diameter. The diameter is twice the size of the radius. A line segment that has its endpoints on the circular border but does not pass through the midpoint is called a chord.

4. Circle Algorithms 4 Use 8-fold symmetry and only compute pixel positions for the 45 ° sector. 45 ° ( x , y ) ( y , x ) (- x , y ) ( y , -x ) ( x , - y ) (- x , - y ) (- y , x ) ( -y , -x )

5. MIDPOINT CIRCLE ALGORITHM Circle function: F circle ( x,y )=x 2 +y 2 -r 2 F circle ( x,y )>0,then ( x,y ) lies outside the circle. F circle ( x,y )<0,then ( x,y ) lies inside the circle F circle ( x,y )=0,then ( x,y ) is on the circle boundary. . F k <0 Y k+1 = y k Next pixel=(x k +1,y k ) Midpoint inside the circle . F k >=0 Y k+1 =y k -1 Next pixel=(x k +1,y k -1) Midpoint above the circle

6. MIDPOINT CIRCLE ALGORITHM The decision parameter is the circle at the midpoint between the pixels y k and y k – 1 . f= f circle (x k +1,y k -1/2) =(x k +1) 2 +(y k -1/2) 2 -r 2 We know that X k+1 =x k +1, F k =f(x k +1,y k -1/2) F k =(x k +1) 2 +(y k -1/2) 2 -r 2 ( i ) F k+1 =f(x k +2,y k+1 -1/2) F k+1 =(x k +2) 2 +(y k+1 -1/2) 2 -r 2 (ii) Now subtracting eq n (ii) by ( i ) F k+1 -f k =2(x k +1)+(y 2 k+1 -y 2 k )-(y k+1 -y k )+1

7. So, If f k <0: y k+1 = y k F k+1 =f k +2x k+1 +1 If f k >=0: y k+1 =y k -1 F k+1 =f k +2x k+1 -2y k+1 +1 For the initial points, (x ,y )=(0,r) F = f circle (1,r-1/2) =1+(r-1/2) 2 -r =5/4-r =1-r

8. The Algorithm Initial values:- point(0, r ) x = 0 y = r Initial decision parameter At each x i position, starting at i = 0, perform the following test: if p i < 0, the next point is ( x i + 1, y i ) and p i +1 = p i + 2 x i +1 + 1 If p i ≥ 0, the next point is ( x i +1, y i -1) and p i +1 = p i + 2 x i +1 + 1 – 2 y i +1 where 2 x i +1 = 2 x i + 2 and 2 y i +1 = 2 y i – 2 Determine symmetry points in the other octants Move pixel positions ( x,y ) onto the circular path centered on ( x c , y c ) and plot the coordinates: x = x + x c , y = y + y c Repeat 3 – 5 until x >= y 8

9. Midpoint algorithm void plotpoints ( int xcenter,int ycenter,int x,int y) { setpixel ( xcenter+x , ycenter+y ); setpixel ( xcenter+x , ycenter -y); setpixel ( xcenter -x, ycenter+y ); setpixel ( xcenter -x, ycenter -y); setpixel ( xcenter+y , ycenter+x ); setpixel ( xcenter+y , ycenter -x); setpixel ( xcenter -y, ycenter+x ); setpixel ( xcenter -y, ycenter -x); } void midpoint( int xcenter,int ycenter,int radius) { int x = 0, y = radius; int f = 1 – radius; plotpoints ( xcenter,ycenter,x,y ); while (x<y) { x++; if (f<0) f += 2*x + 1; else { y--; f+= 2*(x-y) + 1; } plotpoints ( xcenter,ycenter,x,y ); } }

10. Example 10     9   8  7  6  5  4  3  2  1   1 2 3 4 5 6 7 8 9 10 10 i p i x i +1 , y i+1 2 x i +1 2 y i +1 -9 (1, 10) 2 20 1 -6 (2, 10) 4 20 2 -1 (3, 10) 6 20 3 6 (4, 9) 8 18 4 -3 (5, 9) 10 18 5 8 (6, 8) 12 16 6 5 (7, 7) r = 10 p = 1 – r = -9 (if r is integer round p = 5/4 – r to integer) Initial point ( x , y ) = (0, 10)

11. PROGRAM

12. THANK YOU