Scribd
Upload
597 views6 pages

2D Algorithms (Midpoint Circle Algorithm) Computer Graphics

This document describes the midpoint circle algorithm for drawing circles in 2D computer graphics. It explains the mathematical formula for determining if a point is inside, outside or on a circle boundary. It then outlines the steps of the algorithm, which starts at an initial point and uses incremental calculations and a decision parameter to iteratively determine the next point on the circle, plotting each point to draw the circle. It also notes that the algorithm calculates points in all eight octants to fully draw the circular shape centered at any given coordinates.

Uploaded by

शिशिर ढकाल
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
597 views6 pages

2D Algorithms (Midpoint Circle Algorithm) Computer Graphics

This document describes the midpoint circle algorithm for drawing circles in 2D computer graphics. It explains the mathematical formula for determining if a point is inside, outside or on a circle boundary. It then outlines the steps of the algorithm, which starts at an initial point and uses incremental calculations and a decision parameter to iteratively determine the next point on the circle, plotting each point to draw the circle. It also notes that the algorithm calculates points in all eight octants to fully draw the circular shape centered at any given coordinates.

Uploaded by

शिशिर ढकाल
Copyright
© Attribution Non-Commercial (BY-NC)
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd

Computer Graphics (L06)

EG678EX

2-D Algorithms

Prepared By: Dipesh Gautam

Midpoint Circle Algorithm


Circle function defined as:
f circle ( x, y ) ! x 2  y 2  r 2

Any point (x,y) satisfies following conditions


0, f circle ( x, y )! 0, 0, " if ( x, y ) if ( x, y ) if ( x, y ) is inside the circle boundary is on the circle boundary is outside the circle boundary
2

Prepared By: Dipesh Gautam

Decision parameter is the circle function; evaluated as:


p k ! f circle ( x k  1, y k  1 ) 2 1 ! ( x k  1) 2  ( y k  ) 2  r 2 2

1 pk 1 ! f circle ( xk 1  1, yk 1  ) 2 1 ! [( xk  1)  1]2  ( yk 1  ) 2  r 2 2 2 2 pk 1 ! pk  2( xk  1)  ( yk 1  yk )  ( yk 1  yk )  1

Prepared By: Dipesh Gautam

yk+1 = yk if pk<0 yk+1 = yk-1 otherwise

Thus
Pk+1 = Pk + 2xk+1+1 if pk<0 Pk+1 = Pk + 2xk+1+1-2yk+1 otherwise

Also incremental evaluation of 2xk+1 and 2yk+1


2xk+1 = 2xk + 2 2yk+1 = 2yk 2 if pk >0

At start position (x0,y0) = (0,r)


2x0 = 0 and 2y0 = 2r

Prepared By: Dipesh Gautam

Initial decision parameter


1 p 0 ! f circle (1 , r  ) 1 22 2 ! 1  (r  )  r 2 5 ! r 4

For r specified as an integer, round p0 to P0 = 1-r (because all increments are integers)
Prepared By: Dipesh Gautam 5

Algorithm
1. 2. 3. Input radius r and circle center (xc, yc) and obtain the first point on the circumference of a circle centered on the origin as
(x0,y0) = (0,r)

Calculate the initial value of the decision parameter as


P0 = 5/4 r

At each xk position, starting at k = 0, perform the following test: If pk < 0, the next point along the circle centered on (0,0) is (xk+1,yk) and
Pk+1 = pk + 2xk+1 + 1

Otherwise, the next point along the circle is (xk+1,yK-1) and


Where 2xk+1 Pk+1 = pk + 2xk+1 + 1 -2yk+1 = 2xk + 2 and 2yk+1 = 2yk-2

4. 5.

Determine the symmetry points in the other seven octants. Move each calculated pixel position (x,y) onto the circular path centered on (xc,yc) and plot the co-ordinate values:
x = x + xc, y = y+yc

6.

Repeat steps 3 through 5 until x y


Prepared By: Dipesh Gautam 6

You might also like