166 Circle Drawing

Description

This week we’re going to keep it simple… very simple.

Given a radius, draw an ASCII circle.

For example:

ruby circle.rb 7

Should produce a circle of radius 7:

     #####     
   ##     ##   
  #         #  
 #           # 
 #           # 
#             #
#             #
#             #
#             #
#             #
 #           # 
 #           # 
  #         #  
   ##     ##   
     #####     

Note that most fonts do not have a square aspect ratio, which is why the above output may look like an oval, despite my calculations for a circle. It is acceptable if your code produces similar output.

However, for extra credit you may support an additional argument that specifies the aspect ratio (height divided by width).

ruby circle.rb 7 1.4

This should draw a circle of radius 7 with aspect ratio of 1.4. If done correctly, your output will actually look like a circle (assuming 1.4 is an accurate measure of the actual aspect ratio).

Summary

Okay, now perhaps I should have thought about this before giving the “Circle Drawing” quiz, but… how do you summarize circle drawing? “Nice job, it’s a circle!” Or: “Oooh, sorry… but you drew a square. Better luck next time.”

More seriously, there are many serious things that can be said about drawing in the digital realm. The problems associated with trying to draw a simple shape in ASCII do not disappear when you graduate to higher-density pixels. And the correct answer very much depends on the specification. Take, for example, this look at font rendering. Which answer is correct depends very much on your specifications and goals. For fonts, there may be many subjective criteria; for circles, there should be far less.

But, for this quiz, not zero. I didn’t fully specify exactly how I wanted “a circle of radius 7” drawn. Seeing how the mathematical radius of such circle would be 14, some might want their circles drawing within a 14x14 area. However, others (including my own example in the original description) pick the circle center in the middle of an ASCII character center, then measure out 7 units in each direction, which fills a 15x15 area.

Which is correct? Depends on what you want… If you want something close to the mathematical ideal, you want the latter. However, if you’re attempting to integrate circles into a larger system of shapes, it may be that the former fits your purposes better. In any case, as I (intentionally) didn’t specify in the original presentation, no one loses any points here.

Given that, let’s take a look at the solution from Jon Garvin. His solution doesn’t include the aspect ratio correction, but that gives us a good look at the core algorithm. Here it is, holding back on the helper methods for the moment:

class Circle
  def initialize(radius)
    @radius = radius.to_i
  end

  def draw
    (0..@radius*2).each do |x|
      (0..@radius*2).each do |y|
        print distance_from_center(x,y).round == @radius ? '#' : '.'
      end
      puts
    end
  end
end 

Circle.new(ARGV.shift).draw

A nice little Circle class encapsulates the code, storing only the radius during initialization. Some solutions, like Jon’s, didn’t keep a canvas internally, while other solutions did. At this degree of simplicity, keeping a canvas or not is of little concern. In a larger application, speed and memory concerns would be an important factor for keeping a canvas or recalculating each draw.

To draw, two loops are used, nested, to iterate over a 2D grid. At each cell, the cell’s distance from the center is computed and compared to the radius. When equal (i.e. on the circle), our hash symbol is output; when off the circle, a period (to represent empty space). Simple and quite effective.

Now let’s look at distance_from_center:

  def distance_from_center(x,y)
    a = calc_side(x)
    b = calc_side(y)
    return Math.sqrt(a**2 + b**2)
  end

  def calc_side(z)
    z < @radius ? (@radius - z) : (z - @radius)
  end

Given coordinates (x, y) within the circumscribed square, those coordinates are adjusted relative to the center of the circle via calc_side. The adjusted coordinates are the legs of a right triangle, with the hypotenuse calculated via the square-root of the sum of the squares of the legs. Standard basic geometry.

I might make a couple minor changes, though, to Jon’s methods here, just to make things even simpler.

  def draw
    (-@radius..@radius).each do |x|
      (-@radius..@radius).each do |y|
        print distance_from_center(x,y).round == @radius ? '#' : '.'
      end
      puts
    end
  end

  def distance_from_center(x,y)
    return Math.sqrt(x**2 + y**2)
  end

In draw, instead of looping from zero to the radius, loop from negative radius to positive radius. You cover the same range, and x and y are now exactly what a and b would have been as calculated by calc_side, which can now be removed.

It was good to see most folks supporting the aspect ratio, which essentially involved two parts. First, making sure that the canvas (or iterated area) was adjusted (in one dimension or the other; either choice was okay without a better specification). Second, when examining coordinates as the canvas was filled, the coordinates had to be also adjusted.

Finally, kudos to Andrea Fazzi for bringing Bresenham into the mix. Bresenham’s line algorithm is a well known algorithm in the computer graphics field. Not the first line drawer nor the last, it did the job quite well and was quite fast, using only integer numbers and operations – no floating point. The technique is adaptable to more than just lines, as Andrea’s solution shows.


Wednesday, February 04, 2009