Finding Pixels that lie on a Circle

x² + y² = r²

for y in [ 0, n ]
   for x in [ 0, n ]
      if x2 + y2 - r2 = 0
         setPixel ( x, y )

Finding Pixels that nearly lie on a Circle

x² + y² = r²

for y in [ 0, n ]
   for x in [ 0, n ]
      if | x2 + y2 - r2 | <= [delta]
         setPixel ( x, y )

A quarter circle generated with unit steps in x, and with y calculated and then rounded.

Unique values of y for each x produce gaps

Finding the Pixels on a Circle - Polar Parametric

x² + y² = r²

Finding the Pixels on a Circle - Polar Parametric

x² + y² = r²

for [theta] in [ 0, 2[pi] ]
   x = r cos[theta]
   y = r sin[theta]
   setPixel ( x, y )

Symmetry of a Circle

Calculation of a circle point (x,y) in one octant yields the circle points shown for other seven octants

Midpoint Algorithm for Circle

Midpoint between candidate pixels at sampling position x_k+1 along a circular path

Midpoint Algorithm for Circle

The pixel grid for the midpoint circle algorithm showing M and the pixels E and SE to choose between

Midpoint Circle Algorithm

   f(x,y) = x2 + y2 - R2
      f(x,y) > 0  =>  point outside circle
      f(x,y) < 0  =>  point inside circle

Midpoint Circle Algorithm

   f(x,y) = x2 + y2 - R2
      f(x,y) > 0  =>  point outside circle
      f(x,y) < 0  =>  point inside circle

   f(M) = f(xp+1, yp - 1/2)
        = (xp + 1)2 + (yp - 1/2)2 - R2

   d >= 0 choose SE
        next M: +1 in x, -1 in y

   d <  0 choose E
        next M: +1 in x

Midpoint Circle Algorithm

   f(x,y) = x2 + y2 - R2
      f(x,y) > 0  =>  point outside circle
      f(x,y) < 0  =>  point inside circle

   f(n) = f(xp+1, yp - 1/2)
        = (xp + 1)2 + (yp - 1/2)2 - R2

   d >= 0 choose SE
        next n: +1 in x, -1 in y

   d <  0 choose E
        next n: +1 in x

   deltaE  = dnew - dold
           = f(xp + 2, yp - 1/2) - f(xp+1, yp - 1/2)
	   = 2xp + 3

   deltaSE = f(xp + 2, yp - 3/2) - f(xp+1, yp - 1/2)
  	   = 2xp - 2yp + 5

   dstart   = f(x0 + 1, y0 - 1/2) = f(1, R - 1/2)
     	   = 5/4 - R

Midpoint Circle Algorithm

void MidpointCircle ( int radius, int value )
{
   int   x, y;
   float d;

   x = 0;
   y = radius;
   d = 5.0 / 4 - radius;
   CirclePoints ( x, y, value );
   
   while ( y > x ) {
      if ( d < 0 ) {
         d += x * 2.0 + 3;
	 x ++;
      }
      else {
         d += (x - y) * 2.0 + 5;
	 x ++;
	 y --;
      }
      CirclePoints ( x, y, value );
   }
}

Midpoint Circle Algorithm

void MidpointCircle ( int radius, int value )
{
   int   x, y;
   int d;

   x = 0;
   y = radius;
   d = 1 - radius;
   CirclePoints ( x, y, value );
   
   while ( y > x ) {
      if ( d < 0 ) {
         d += x * 2 + 3;
	 x ++;
      }
      else {
         d += (x - y) * 2 + 5;
	 x ++;
	 y --;
      }
      CirclePoints ( x, y, value );
   }
}

Midpoint Circle Algorithm

void CirclePoints (float x, float y, int value)
{
   WritePixel (  x,  y, value );
   WritePixel (  y,  x, value );
   WritePixel (  y, -x, value );
   WritePixel (  x, -y, value );
   WritePixel ( -x, -y, value );
   WritePixel ( -y, -x, value );
   WritePixel ( -y,  x, value );
   WritePixel ( -x,  y, value );
}

Midpoint Circle Algorithm

Midpoint Circle Algorithm

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

x y p 0 3 -2

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

x y p 0 3 -2 1 3 3

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

x y p 0 3 -2 1 3 3 2 2 8

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

plotPoints ( x, xc, y, yc ) xc + x, yx + y xc - x, yx + y xc + x, yx - y xc - x, yx - y xc + y, yx + x xc - y, yx + x xc + y, yx - x xc - y, yx - x

x y p -> 0 3 -2 1 3 3 2 2 8

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

plotPoints ( x, xc, y, yc ) xc + x, yx + y xc - x, yx + y xc + x, yx - y xc - x, yx - y xc + y, yx + x xc - y, yx + x xc + y, yx - x xc - y, yx - x

x y p -> 0 3 -2 1 3 3 2 2 8

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

plotPoints ( x, xc, y, yc ) xc + x, yx + y xc - x, yx + y xc + x, yx - y xc - x, yx - y xc + y, yx + x xc - y, yx + x xc + y, yx - x xc - y, yx - x

x y p -> 0 3 -2 -> 1 3 3 2 2 8

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle Algorithm

plotPoints ( x, xc, y, yc ) xc + x, yx + y xc - x, yx + y xc + x, yx - y xc - x, yx - y xc + y, yx + x xc - y, yx + x xc + y, yx - x xc - y, yx - x

x y p -> 0 3 -2 -> 1 3 3 -> 2 2 8

x = 0, y = r, p = 1 - r

plotPoint ( x + xc, y + yc )
while x < y {
   if p < 0 {
      x = x + 1
      p = p + 2x + 3
   }
   else {
      x = x + 1
      y = y - 1
      p = p + 2( x - y ) + 5
   } 
   plotPoint ( x + xc, y + yc )
}

Midpoint Circle: Second Order Differences

Key idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally

Midpoint Circle: Second Order Differences

Key idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally

caseE: 
   deltaEold = 2xp + 3
   deltaEnew = 2xp + 5
   deltaDeltaE  = 2
   deltaDeltaSE = ( 2(xp - 1) - 2yp + 5 ) - ( 2xp - 2yp + 5 )
                = 2

Midpoint Circle: Second Order Differences

Key idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally

caseE: 
   deltaEold = 2xp + 3
   deltaEnew = 2xp + 5
   deltaDeltaE  = 2
   deltaDeltaSE = ( 2(xp - 1) - 2yp + 5 ) - ( 2xp - 2yp + 5 )
                = 2

caseSE: 
   deltaDeltaE  = (2xp + 5) - (2xp + 3)
                = 2
   deltaDeltaSE = ( 2(xp + 1) - 2(yp - 1) + 5 ) - ( 2xp - 2yp - 5 )
                = 4

Midpoint Circle: Second Order Differences

Key idea: Just as we calculate x and y incrementally, we can also calculate deltaE and deltaSE incrementally

caseE: 
   deltaEold = 2xp + 3
   deltaEnew = 2xp + 5
   deltaDeltaE  = 2
   deltaDeltaSE = ( 2(xp - 1) - 2yp + 5 ) - ( 2xp - 2yp + 5 )
                = 2

caseSE: 
   deltaDeltaE  = (2xp + 5) - (2xp + 3)
                = 2
   deltaDeltaSE = ( 2(xp + 1) - 2(yp - 1) + 5 ) - ( 2xp - 2yp - 5 )
                = 4

Starting out:
   deltaEstart = 2 * 0 + 3 = 3
   deltaSEstart = 2 * 0 - 2 * R + 5
                   = 5 - 2R

void MidpointCircle ( int radius, int value )
{                   
   int     x, y, d, deltaE, deltaSE;

   x       = 0;
   y       = radius;
   d       = 1 - radius;
   deltaE  = 3;
   deltaSE = 5 - radius * 2;

   CirclePoints ( x, y, value );
   
   while ( y > x ) {
      if ( d < 0 ) { /* Select E */
         d       += deltaE;
	 deltaE  += 2;
	 deltaSE += 2;
	 x       ++;
      } 
      else {         /* Select SE */
         d       += deltaSE;
	 deltaE  += 2;
	 deltaSE += 4;
	 x       ++;
	 y       ++;
      }
      CirclePoints ( x, y, value );
   }
}