Bitmap/Midpoint circle algorithm

Using the data storage type defined on this page for raster images, write an implementation of the midpoint circle algorithm (also known as Bresenham's circle algorithm).
(definition on Wikipedia).

Ada

<lang ada> procedure Circle

         (  Picture : in out Image;
            Center  : Point;
            Radius  : Natural;
            Color   : Pixel
         )  is
  F     : Integer := 1 - Radius;
  ddF_X : Integer := 0;
  ddF_Y : Integer := -2 * Radius;
  X     : Integer := 0;
  Y     : Integer := Radius;

begin

  Picture (Center.X, Center.Y + Radius) := Color;
  Picture (Center.X, Center.Y - Radius) := Color;
  Picture (Center.X + Radius, Center.Y) := Color;
  Picture (Center.X - Radius, Center.Y) := Color; 
  while X < Y loop
     if F >= 0 then
        Y := Y - 1;
        ddF_Y := ddF_Y + 2;
        F := F + ddF_Y;
     end if;
     X := X + 1;
     ddF_X := ddF_X + 2;
     F := F + ddF_X + 1;    
     Picture (Center.X + X, Center.Y + Y) := Color;
     Picture (Center.X - X, Center.Y + Y) := Color;
     Picture (Center.X + X, Center.Y - Y) := Color;
     Picture (Center.X - X, Center.Y - Y) := Color;
     Picture (Center.X + Y, Center.Y + X) := Color;
     Picture (Center.X - Y, Center.Y + X) := Color;
     Picture (Center.X + Y, Center.Y - X) := Color;
     Picture (Center.X - Y, Center.Y - X) := Color;
  end loop;

end Circle; </lang> The following illustrates use: <lang ada>

  X : Image (1..16, 1..16);

begin

  Fill (X, White);
  Circle (X, (8, 8), 5, Black);
  Print (X);

</lang> Sample output:



     HHHHH
    H     H
   H       H
  H         H
  H         H
  H         H
  H         H
  H         H
   H       H
    H     H
     HHHHH

C

<C>#define plot(x, y) put_pixel_clip(img, x, y, r, g, b)

void raster_circle(

       image img,
       unsigned int x0,
       unsigned int y0,
       unsigned int radius,
       color_component r,
       color_component g,
       color_component b )

{

   int f = 1 - radius;
   int ddF_x = 0;
   int ddF_y = -2 * radius;
   int x = 0;
   int y = radius;

   plot(x0, y0 + radius);
   plot(x0, y0 - radius);
   plot(x0 + radius, y0);
   plot(x0 - radius, y0);

   while(x < y) 
   {
       if(f >= 0) 
       {
           y--;
           ddF_y += 2;
           f += ddF_y;
       }
       x++;
       ddF_x += 2;
       f += ddF_x + 1;    
       plot(x0 + x, y0 + y);
       plot(x0 - x, y0 + y);
       plot(x0 + x, y0 - y);
       plot(x0 - x, y0 - y);
       plot(x0 + y, y0 + x);
       plot(x0 - y, y0 + x);
       plot(x0 + y, y0 - x);
       plot(x0 - y, y0 - x);
   }

}

undef plot</C>

Forth

: circle { x y r color bmp -- }
  1 r -  0 r 2* negate  0 r  { f ddx ddy dx dy }
  color x     y r + bmp b!
  color x     y r - bmp b!
  color x r + y     bmp b!
  color x r - y     bmp b!
  begin dx dy < while
    f 0< 0= if
      dy  1-      to dy
      ddy 2 + dup to ddy
      f +         to f
    then
    dx 1+       to dx
    ddx 2 + dup to ddx
    f 1+ +      to f
    color x dx + y dy + bmp b!
    color x dx - y dy + bmp b!
    color x dx + y dy - bmp b!
    color x dx - y dy - bmp b!
    color x dy + y dx + bmp b!
    color x dy - y dx + bmp b!
    color x dy + y dx - bmp b!
    color x dy - y dx - bmp b!
  repeat ;

12 12 bitmap value test
0 test bfill
6 6 5 blue test circle
test bshow cr

OCaml

<lang ocaml>let raster_circle ~img ~color ~c:(x0, y0) ~r =

 let plot = put_pixel img color in
 let x = 0
 and y = r
 and m = 5 - 4 * r
 in
 let rec loop x y m =
   plot (x0 + x) (y0 + y);
   plot (x0 + y) (y0 + x);
   plot (x0 - x) (y0 + y);
   plot (x0 - y) (y0 + x);
   plot (x0 + x) (y0 - y);
   plot (x0 + y) (y0 - x);
   plot (x0 - x) (y0 - y);
   plot (x0 - y) (y0 - x);
   let y, m =
     if m > 0
     then (y - 1), (m - 8 * y)
     else y, m
   in
   if x <= y then
     let x = x + 1 in
     let m = m + 8 * x + 4 in
     loop x y m
 in
 loop x y m

</lang>

Vedit macro language

//  Daw a circle using Bresenham's circle algorithm.
//  #21 = center x, #22 = center y; #23 = radius

:DRAW_CIRCLE:
#30 = 1 - #23		// f
#31 = 0			// ddF_x
#32 = -2 * #23		// ddF_y
#41 = 0			// x
#42 = #23		// y

while (#41 <= #42) {
    #1 = #21+#41; #2 = #22+#42; Call("DRAW_PIXEL")
    #1 = #21-#41; #2 = #22+#42; Call("DRAW_PIXEL")
    #1 = #21+#41; #2 = #22-#42; Call("DRAW_PIXEL")
    #1 = #21-#41; #2 = #22-#42; Call("DRAW_PIXEL")
    #1 = #21+#42; #2 = #22+#41; Call("DRAW_PIXEL")
    #1 = #21-#42; #2 = #22+#41; Call("DRAW_PIXEL")
    #1 = #21+#42; #2 = #22-#41; Call("DRAW_PIXEL")
    #1 = #21-#42; #2 = #22-#41; Call("DRAW_PIXEL")
    if (#30 >= 0) {
	#42--
	#32 += 2
	#30 += #32
    }
    #41++
    #31 += 2
    #30 += #31 + 1
}

return