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++ }
explanation: The provided text is a detailed explanation of the Midpoint Circle Algorithm, a method used in computer graphics for drawing circles. The text describes the mathematical basis of the algorithm, including the decision parameter and the incremental computation for determining the next pixel to plot. It also includes the algorithm in pseudocode form.
  
  The text does not contain a specific question or an answer to a question. It is purely an explanatory document.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: 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++ }
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The provided text is a detailed explanation of the Midpoint Circle Algorithm, a method used in computer graphics for drawing circles. The text describes the mathematical basis of the algorithm, including the decision parameter and the incremental computation for determining the next pixel to plot. It also includes the algorithm in pseudocode form.
  
  The text does not contain a specific question or an answer to a question. It is purely an explanatory document.
  
  Label: no-question