Bresenham's circle algorithm

Circles have the property of being highly symmetrical, which is handy when it comes to drawing them on a display screen.

Consider the diagram below:

      |y          
      |           
  \ ..... /
   .  |  .        
  . \ | / .       
  .  \|/  .       
--.---+---.--     
  .  /|\  . x     
  . / | \ .       
   .  |  .        
  / ..... \       
      |
      |

(This diagram is supposed to be a circle, try viewing it in 50 line mode). We know that there are 360 degrees in a circle. First we see that a circle is symmetrical about the x axis, so only the first 180 degrees need to be calculated. Next we see that it's also symmetrical about the y axis, so now we only need to calculate the first 90 degrees. Finally we see that the circle is also symmetrical about the 45 degree diagonal axis, so we only need to calculate the first 45 degrees.
Bresenham's circle algorithm calculates the locations of the pixels in the first 45 degrees. It assumes that the circle is centered on the origin. So for every pixel (x,y) it calculates we draw a pixel in each of the 8 octant of the circle :

PutPixel(CenterX + X, Center Y + Y)
PutPixel(CenterX + X, Center Y - Y)
PutPixel(CenterX - X, Center Y + Y)
PutPixel(CenterX - X, Center Y - Y)
PutPixel(CenterX + Y, Center Y + X)
PutPixel(CenterX + Y, Center Y - X)
PutPixel(CenterX - Y, Center Y + X)
PutPixel(CenterX - Y, Center Y - X)

So let's get into the actual algorithm. Given a radius for the circle we perform this initialisation:

d := 3 - (2 * RADIUS)
x := 0
y := RADIUS

Now for each pixel we do the following operations:

Draw the 8 circle pixels
if d < 0 then
    d := d + (4 * x) + 6
else
  begin
    d := d + 4 * (x - y) + 10
    y := y - 1;
  end;

And we keep doing this until x = y. Note that the values added to the decision variable in this algorithm (x and y) are constantly changing, so we cannot precalculate them. The muliplications however are by 4, and we can accomplish this by shifting left twice.

More articles

• http://www.asksatyam.com/2011/01/bresenhams-circle-algorithm_22.html
• http://www.ecse.rpi.edu/~wrf/Research/Short_Notes/bresenham.html

Read More

Line Drawing Algorithms

Line Algorithm
The basic algorithm works for lines which look like this:

      o-------                         |
     p1       --------                 | deltaY
                      -------      p2  |
                             -------o  |
      ----------------------------------
                  deltaX

where p1 = (x1,y1),
      p2 = (x2, y2),
      x and y are both increasing from p1 to p2,
      deltaX = x2 - x1,
      deltaY = y2 - y1 and
      deltaX >= deltay.

All other types of lines can be derived from this type. I'll get to this bit later.
First you need to perform the following intialisation:

x = x1
y = y1
d = (2 * deltaY) - deltaX

x is the current x location, you will add 1 to this variable after every pixel you draw until all pixels have been drawn. y is the current y location. The decision variable is used to determine when to add 1 to this value. d is the decision variable which will be used to keep a track of what to do.
Now you loop across the screen from x1 to x2 and for each loop perform the following operations for each pixel :

PutPixel(x, y);  { Draw a pixel at the current point }
if d < 0 then
    d := d + (2 * deltaY)
else
  begin
    d := d + 2 * (deltaY - deltaX);
    y := y + 1;
  end;
x := x + 1;

Read More

Routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.

Problem

Write a routine to draw a circle (x ** 2 + y ** 2 = r ** 2) without making use of any floating point computations at all.

Solution

Let

(x ^ 2 + y ^2 = r ^ 2)...................................1 

The basic idea is to draw one quadrant and replicate it to other four quadrants.
Assuming the center is given as (a,b) and radius as r units, then start X from (a+r) down to (a) and start Y from (b) up to (b+r). In the iteration, keep comparing is the equation (1) is satisfied or not within an error of one unit for a and b. If not then re-adjust X and Y.

Also, we should either use Mid point theorem or Bresenham's circle drawing algorithm for this.

Read More