CMSC 15200 Lab — Winter 2007
Lab Assignment 3
Bresenham's Circle Algorithm

A simple version of Bresenham's Circle Algorithm

In the early sixties Jack Bresenham came-up with a clever algorithm for determining which pixels in a two-dimensional raster graph should be plotted to draw smooth lines, circles and ellipses. We will look at the basic algorithm behind drawing circles.

We can take advantage of the symmetry of the circle to plot only points in a single octant of the circle. I have drawn a circle in raster graphics, divided into octants determined by a horizontal, a vertical and the two diagonal lines. (The code for drawing this is also provided.)

     WIN win;
     clearW(win);
     addLine(win, 15, 0, 20, V, '|');
     addLine(win, 5, 10, 20, H, '-');
     addLine(win, 5, 20, 20, DU, '/');
     addLine(win, 5, 0, 20, DD, '\\');
     addCircle(win, 15, 10, 5, OUTLINE,'.');
     printW(win);
+----------------------------------------+
|               |                        |
|      \        |        /               |
|               |       /                |
|        \  8   |   1  /                 |
|               |     /                  |
|          \  .....  /                   |
|    7       .  |  ./      2             |
|           .\  |  /.                    |
|          .    | /  .                   |
|          .   \|/   .                   |
|     -----.----/----.----               |
|          .   /|\   .                   |
|          .  / |    .                   |
|           ./  |  \.                    |
|   6       /.  |  .         3           |
|          /  .....  \                   |
|         /     |                        |
|        /  5   |  4   \                 |
|       /       |                        |
|      /        |        \               |
+----------------------------------------+
The circle is 360 degrees, and each octant is 45 degrees. Once you calculate the pixels in one octant, simply rotate the circle to get points in all other octants. Our algorithm will calculate the pixels to plot in quadrant 1 of a circle centered at (0,0) of a given radius. We can use this information to generate a whole circle centered at (a,b) of the same radius as follows: Suppose that we have we have determined to plot a pixel located at position (x,y) in quadrant 1 of a circle centered at (0,0). Then we will want to plot the following 8 pixels in our actual circle centered at (a,b)
     1.	 (a+x, b+y)
     2.  (a+y, b+x)
     3.  (a+y, b-x)
     4.  (a+x, b-y)
     5.  (a-x, b-y)  
     6.  (a-y, b-x)
     7.  (a-y, b+x)
     8.  (a-x, b+y)

Bresenham's Circle Algorithm

     Bresenham's Algorithm for plotting pixels in quadrant 1
     	of a circle centered at (0,0)
	
     INPUT:  R : radius of circle
There are two variables to the algorithm charts:
     	x : x-coordinate, initially set to 0
	y : y-coordinate, initially set to R
So, the first point will be (0,R). The idea of the algorithm is that we will always increment x, so the only question is to determine the value of y. This value either remains the same or is decremented:
	If (x,y) is the current pixel coordinate, then
	  the next pixel to plot is either (x+1,y) or
	  (x+1, y-1).
Here is how we decide the next pixel to plot. Consider the following picture:
where
	P : current pixel, (x,y)
	E : one possible next pixel, (x+1, y)
	SE : second possible next pixel,(x+1, y-1)
	M : mid-point of E and SE, (x+1, y-0.5)
The algorithm chooses the next pixel to plot depending whether M lies above, on or below the circle:
	* If (x+1)^2 + (y-0.5)^2 - R^2 > 0, then M lies above the
	  circle and we choose SE to be the next point.
	* If (x+1)^2 + (y-0.5)^2 - R^2 ==  0, then M lies on the
	  circle and we choose SE to be the next point.
	* If (x+1)^2 + (y-0.5)^2 - R^2 < 0, then M lies below the
	  circle and we choose E to be the next point.
The algorithm terminates when x>y, and determines all the pixels to plot in quadrant 1 of a circle of radius R centered at (0,0).


Kenneth Harris