text: 0
  Upcoming SlideShare
  ×
  
  Thanks for flagging this SlideShare!
  
  Oops! An error has occurred.
  
  ×
  Saving this for later? Get the SlideShare app to save on your phone or tablet. Read anywhere, anytime – even offline.
  Standard text messaging rates apply
  
  # Midpoint circle algo
  
  7,733
  
  Published on
  
  4 Likes
  Statistics
  Notes
  • Full Name
  Comment goes here.
  
  Are you sure you want to Yes No
  Your message goes here
  • Be the first to comment
  
  Views
  Total Views
  7,733
  On Slideshare
  0
  From Embeds
  0
  Number of Embeds
  0
  Actions
  Shares
  0
  231
  0
  Likes
  4
  Embeds 0
  No embeds
  
  No notes for slide
  
  ### Transcript
  
  • 1. Midpoint Circle AlgorithmMid point algorithm is very similar toBresenham’s approach. It is based on thefollowing function for testing the spatialrelationship between an arbitrary point(x,y)and a circle of radius centered at the origin: < 0 (x,y) inside circlef(x,y) = x2 + y2 – r2 = 0 (x,y) on the circle > 0 (x,y) outside circle`
  • 2. Now consider the coordinates of the pointhalfway between pixel T & S (xi + 1, yi – ½)This is called the midpoint and we use it todefine a decision parameter: pi = f( xi +1, yi – ½) = (xi + 1)2 + (yi – ½)2 – r2If pi is –ve , the midpoint is inside the circle,then we choose pixel T. If pi is +ve, themidpoint is outside the circle, & we choose S.
  • 3. Similarly, the decision parameter for the nextstep is:pi+1 = (xi+1 + 1)2 + (yi+1 – ½)2 – r2Since x i+1 = xi + 1 pi+1 - pi = [(xi + 1)+ 1]2 – (xi + 1)2 + (y i+1 – ½)2 – (yi – ½)2Hence pi+1 = pi + 2(xi + 1) + 1 + (y i+12 – yi2) – (y i+1 – yi)
  • 4. If pixel T is chosen (meaning pi < 0), we have yi+1 = yi.If pixel S is chosen (meaning pi > 0), we have yi+1 = yi – 1. Thus, pi+1= pi + 2(xi + 1) +1 if pi<0 pi + 2(xi + 1) +1 – 2(yi – 1) if pi>0In terms of (xi, yi), we have pi+1= pi + 2xi + 3 if pi<0 pi + 2(xi - yi ) + 5 if pi>0
  • 5. Finally, we compute the initial value for thedecision parameter using the originaldefinition of pi and (0,r): pi = (0 + 1)2 + (r – ½)2 – r2 = 5/4 – rOne can see that this is not really integercomputation. However, when r is an integerwe can simply set p1= 1 – r. The error ofbeing ¼ less than the precise value does notprevent p1 from getting the appropriate sign.
  • 6. It does not affect the rest of the scanconversion process, because the decisionvariable is only updated with integer incrementin subsequent steps.
  • 7. Algorithm:The following is a description of this midpointcircle algorithm that generates the pixelcoordinates in the 90˚ to 45 ˚ octant: int x = 0, y = r, p = 1-r while (x <=y) { setpixel(x,y); if (p < 0) p = p + 2x + 3
  • 8. else { p = p + 2(x – y) + 5 y- - } x++ }