[SUMMARY] Circle Drawing (#166)

Discussion in 'Ruby' started by Matthew Moss, Jun 19, 2008.

  1. Matthew Moss

    Matthew Moss Guest

    [Note: parts of this message were removed to make it a legal post.]

    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][1]. 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

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


    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)

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

    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 ? '#' : '.'

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

    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][2] 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.

    [1]: http://www.codinghorror.com/blog/archives/000885.html
    [2]: http://en.wikipedia.org/wiki/Bresenham's_line_algorithm
    Matthew Moss, Jun 19, 2008
    1. Advertisements

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Replies:
    Kevin Spencer
    Jan 9, 2006
  2. chotchkie
    Aug 4, 2005
  3. defn noob
    Mark Space
    Jun 28, 2008
  4. Matthew Moss

    [QUIZ] Circle Drawing (#166)

    Matthew Moss, Jun 13, 2008, in forum: Ruby
    Jul 12, 2008
  5. Ben
    Geir Klemetsen
    Sep 12, 2003

Share This Page