Bresenham-Circle-drawing-algorithm, Midpoint Circle Drawing Algorithm

DDA Circle Drawing algorithm, Bresenham-Circle-drawing-algorithm, Midpoint Circle Drawing algorithm

1. Circle Drawing Algorithm WITH SOLVED EXAMPLE Prof. Sujata L. Sonawane Assistant Professor Department of Artificial Intelligence and Machine Learning P.E.S. Modern College of Engineering, Pune .

2. Circle Drawing Set of points that are all at a distance r from the center position (Xc,Yc) . Frequently used component in pictures and graphs Procedure for generating full circle or circular arcs is included in graphics packages . Single procedure can be used to draw circle or elliptical curve.

3. Circle Properties Distance relationship in cartesian coordinates

4. Spacing between plotted pixel positions is not uniform It involves considerable equations at each step. Increases the computation and processing required by algorithm.

5. Another way to eliminate the unequal spacing , calculate points along the circular boundary using polar coordinates r and Theta. Circle is plotted with equally spaced points along the circumference.

6. For more continuous boundary on a raster display, we can set the step size at 1/r. It plots pixel positions that are approximately one unit apart.

7. Computations: Cartesian equation : multiplication and square root calculation Parametric equation : multiplication and trigonometric calculation Most efficient circle drawing algorithms are based on incremental calculations of decision parameter, as in Bresenham line algorithm , simple integer operations.

8. DDA Line Drawing Algorithm

9. Bresenham Circle Drawing Algorithm Considers 8-way symmetry plots 1/8th part of circle, from 90 to 45 degrees angle.

10. To achieve best approximation to the true circle we have to select those pixels in the raster that fall the least distance from true circle . if points are generated from 90 to 45 degree, each new point closest to the true circle can be found by applying either of two options : increment in positive x direction by one unit or Increment in +ve x direction and -ve y direction both by one unit

11. Closer pixel amongst these two can be determined as

12. Midpoint-Circle Drawing Algorithm Uses eight way symmetry to generate a circle. It plots 1/8 th part of circle i.e. from 90 to 45 degree To draw a circle, we take unit steps in the positive x direction and make use of decision parameter to determine which of the two possible y directions is closer to the circle path at each step.

13. 2 possible y positions ( y i and y i+1 )at sampling position x i+1 . To determine closer y coordinate to circle, decision parameter is used.

14. If d i <0, midpoint is inside the circle, pixel on the scan line y i is closer to the circle boundary. If d i >=0, the midposition is outside or on the circle boundary, and y i-1 is closer to the circle boundary. Incremental calculation determined to obtain successive decision parameters.

15. Questions Explain Mid-point circle drawing algorithm? List its advantages and disadvantages over DDA circle drawing algorithm. Write midpoint circle generation algorithm. Draw circle having center (0,0) and radius 9 using this algorithm Derive the Midpoint circle algorithm. Considering the midpoint circle algorithm draw a circle with radius 10 and center (0,0) Explain midpoint circle generation algorithm by deriving the steps.

16. THANK YOU