Midpoint Circle Algorithm We will first calculate pixel positions for a circle centered around the origin (0,0). Then, each calculated position (x,y) is moved to its proper screen position by adding xc to x and yc to y Note that along the circle section from x=0 to x=y in the first octant, the slope of the curve varies from 0 to -1 Circle function around the origin is given by fcircle(x,y) = x 2 + y 2 – r 2 Any point (x,y) on the boundary of the circle satisfies the equation and circle function is zero

Midpoint Circle Algorithm:

Midpoint Circle Algorithm For a point in the interior of the circle, the circle function is negative and for a point outside the circle, the function is positive Thus, f circle (x,y) < 0 if (x,y) is inside the circle boundary f circle (x,y) = 0 if (x,y) is on the circle boundary f circle (x,y) > 0 if (x,y) is outside the circle boundary yk Yk-1 xk xk+1 Xk+2 Midpoint X 2 +y 2 -r 2 =0 Midpoint between candidate pixels at sampling position x k +1 along a circular path

Midpoint Circle Algorithm:

Midpoint Circle Algorithm Assuming we have just plotted the pixel at (x k ,y k ) , we next need to determine whether the pixel at position ( x k + 1, y k -1) is closer to the circle Our decision parameter is the circle function evaluated at the midpoint between these two pixels p k = f circle (x k +1, y k -1/2) = (x k +1) 2 + (y k -1/2) 2 – r 2 If p k < 0 , this midpoint is inside the circle and the pixel on the 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 the scan line y k -1

Midpoint Circle Algorithm:

Midpoint Circle Algorithm Successive decision parameters are obtained using incremental calculations P k+1 = f circle (x k+1 +1, y k+1 -1/2) = [(x k+1 )+1] 2 + (y k+1 -1/2) 2 –r 2 OR P k+1 = P k +2(x K +1) + (y K+1 2 – y k 2 ) – (y k +1- y k )+1 Where y k+1 is either y k or y k-1 , depending on the sign of p k Increments for obtaining P k+1 : 2x k+1 +1 if p k is negative 2x k+1 +1-2y k+1 otherwise

Midpoint circle algorithm:

Midpoint circle algorithm Note that following can also be done incrementally: 2x k+1 = 2x k +2 2 y k+1 = 2y k – 2 At the start position (0,r) , these two terms have the values 2 and 2r-2 respectively Initial decision parameter is obtained by evaluating the circle function at the start position (x0,y0) = (0,r) p 0 = f circle (1, r-1/2) = 1+ (r-1/2) 2 -r 2 OR P 0 = 5/4 -r If radius r is specified as an integer, we can round p 0 to p 0 = 1-r

The Midpoint Circle algorithm:

The Midpoint Circle algorithm 1: Input radius r and circle center (x c ,y c ) and obtain the first point on the circumference of the circle centered on the origin as (x 0 ,y 0 ) = (0,r) 2: Calculate the initial value of the decision parameter as P 0 = 5/4 - r 3: At each x k position starting at k = 0 , perform the following test: If p k < 0 , the next point along the circle centered on (0,0) is (x k+1 , y k ) and p k+1 = p k + 2x k+1 + 1

Continuation…:

Continuation… Otherwise the next point along the circle is (x k+1 , y k-1 ) and p k+1 = p k + 2x k+1 +1 -2y k+1 Where 2x k+1 = 2x k+2 and 2y k+1 = 2y k -2 4: Determine symmetry points in the other seven octants 5: Move each calculated pixel position (x,y) onto the circular path centered on (xc,yc) and plot the coordinate values x = x+ x c , y= y+ y c 6: Repeat steps 3 through 5 until x >= y

PowerPoint Presentation:

Void circlemidpoint(int Xcenter , int YCenter, int radius) { int x=0; int y=radius; int p=1-radius; Void circleplotpoints (int , int , int, int ); }

PowerPoint Presentation:

/* plot first set of points*/ circleplotpoints ( XCenter , Ycenter, x, y); while(x<y) { X++; If(p<0) P+=2*x+1;

You do not have the permission to view this presentation. In order to view it, please
contact the author of the presentation.

Send to Blogs and Networks

Processing ....

Premium member

Use HTTPs

HTTPS (Hypertext Transfer Protocol Secure) is a protocol used by Web servers to transfer and display Web content securely. Most web browsers block content or generate a “mixed content” warning when users access web pages via HTTPS that contain embedded content loaded via HTTP. To prevent users from facing this, Use HTTPS option.