Midpoint Circle Algorithm

circle

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

  1. Jack E. Bresenham, “Algorithms for Computer Control of a Digital Plotter“, IBM System Journal, 1965.
Tagged with: , , ,

Leave a Reply

Your email address will not be published. Required fields are marked *

*