The Midpoint circle algorithm is a clever and efficient way of drawing a circle using only addition, subtraction, and bit shifts. It is based on the Bresenham line algorithm developed by Jack Bresenham in 1962 at IBM.

The algorithm was also independently discovered by Apple programmer Bill Atkinson in 1981 when developing QuickDraw for the original Macintosh.

A Fortran implementation is given below (which was used to draw the circle shown here, which has a radius of 7 pixels):

subroutine draw_circle(x0, y0, radius, color) implicit none integer,intent(in) :: x0, y0, radius, color integer :: x,y,err x = radius y = 0 err = 1-x do while (x >= y) call color_pixel( x + x0, y + y0, color) call color_pixel( y + x0, x + y0, color) call color_pixel( -x + x0, y + y0, color) call color_pixel( -y + x0, x + y0, color) call color_pixel( -x + x0, -y + y0, color) call color_pixel( -y + x0, -x + y0, color) call color_pixel( x + x0, -y + y0, color) call color_pixel( y + x0, -x + y0, color) y = y + 1 if (err<0) then err = err + 2 * y + 1 else x = x - 1 err = err + 2 * (y - x + 1) end if end do end subroutine draw_circle

### References

- Jack E. Bresenham, “Algorithms for Computer Control of a Digital Plotter“, IBM System Journal, 1965.

## Leave a Reply