Re: [QUIZ] Circle Drawing (#166)

Matthew Moss ha scritto:
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> The three rules of Ruby Quiz 2:
>
> 1.  Please do not post any solutions or spoiler discussion for this
> quiz until 48 hours have passed from the time on this message.
>
> 2.  Support Ruby Quiz 2 by submitting ideas as often as you can! (A
> permanent, new website is in the works for Ruby Quiz 2. Until then,
> please visit the temporary website at
>
>      <http://splatbang.com/rubyquiz/>.
> 3.  Enjoy!
>
> Suggestion:  A [QUIZ] in the subject of emails about the problem
> helps everyone on Ruby Talk follow the discussion.  Please reply to
> the original quiz message, if you can.
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
>
> ## Circle Drawing (#166)
>
> 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).
>
>
>
>   
Here my solution. It is available on pastie:

http://pastie.org/215379
http://pastie.org/215380 (specs)

and it is also attached below:

#
# Solution to Ruby Quiz #166 - Circle Drawing
#
# Usage:
#
# Circle.new(5).to_s
#
# or:
#
# Circle.new(5, 2).to_s
#
#
# or:
#
# Circle.new(5, 2, 'x').to_s
#

# Objects of class Circle draw circles on stdout. The aspect ratio
# correction is actually made drawing an ellipse with semimajor axis
# (a) equals to the given circle radius and semiminor axis (b) equals
# to a / aspect_ratio.
#
# Circle class is responsible to
#
#  * initialize a Circle object with the given radius, aspect ratio
#    and drawing char
#  
#  * initialize a canvas
#
#  * draw the circle on its internal canvas
#
#  * convert the canvas to string for output on stdout
#
class Circle

  # cx, cy are the coordinates of the circle's center.
  attr_reader :cx, :cy

  attr_reader :radius
 
  # w, h are width and height of the canvas
  attr_reader :w, :h
 
  # canvas is a linear array that is initially filled with spaces
  attr_reader :canvas
 
  #
  # Initialize a Circle object passing a value for radius, aspect
  # ratio and drawing character.
  #
  def initialize(radius, aspect_ratio = 1.0, char = '#')
    
    @radius = radius.to_i
    @aspect_ratio = aspect_ratio.to_f
    @char = char

    fail "Error: radius must be > 0" if @radius <= 0
    fail "Error: aspect ratio must be > 0" if @aspect_ratio <= 0
        
    # a is the semimajor axis of the ellipse and is equal to the given
    # radius
    @a = @radius
    
    # b is the semiminor axis of the ellipse and is calculated from a
    # and the given aspect ratio
    @b = (@a / @aspect_ratio).ceil
    
    # calculate the size of the canvas
    @w, @h = (@a + 1) * 2, (@b + 1) * 2
    
    # center coordinates correspond to the size of semiaxis.
    @cx, @cy = @a, @b
    
    # initialize the canvas with spaces
    @canvas = Array.new(@w * @h, ' ')
    
    # draw ellipse on canvas
    draw_ellipse(@a, @b)
  end
 
  #
  # Print circle on stdout.
  #
  def to_s
    result = ""
    (0..@h - 1).each do |line|
      result << @canvas[line * @w..line * @w + @w - 1].to_s << "\n"
    end
    result
  end
 
  private

  #
  # Draw the given character on canvas to the given coordinates.
  #
  def point(x, y)
    @canvas[y * @w + x] = @char
  end
 
  #
  # Translates and mirrors point (x, y) in the quadrants taking
  # advantage of the simmetries in the ellipse. Thus, for a given
  # point (x, y) the method plot three other points in the remaining
  # quadrants.
  #
  def plot_four_points(x, y)
    point(@cx + x, @cy + y)
    point(@cx - x, @cy + y)
    point(@cx + x, @cy - y)
    point(@cx - x, @cy - y)
  end
 
  #
  # Draw an ellipse on canvas. This method implements a Bresenham
  # based algorithm by John Kennedy
  # (http://homepage.smc.edu/kennedy_john/BELIPSE.PDF)
  #
  # The method calculates two set of points in the first quadrant. The
  # first set starts on the positive x axis and wraps in a
  # counterclockwise direction until the tangent line slope is equal
  # to -1.  The second set starts on the positive y axis and wraps in
  # a clockwise direction until the tangent line slope is equal to -1.
  #
  def draw_ellipse(a, b)
    a_square = 2 * a**2
    b_square = 2 * b**2
    
    draw_first_set(a, b, a_square, b_square)
    draw_second_set(a, b, a_square, b_square)
  end
 
  #
  # The method increments y and decides when to decrement x testing
  # the sign of a function.  In this case, the decision function is
  # (2*ellipse_error+x_change) and its value is calculated
  # iteratively.
  #
  def draw_first_set(a, b, a_square, b_square)
    
    x, y = a, 0
    x_change, y_change = b**2 * (1 - 2 * a), a**2
    stopping_x, stopping_y = b_square * a, 0
    ellipse_error = 0
    
    while(stopping_x >= stopping_y) do
      plot_four_points(x, y)
      y += 1
      stopping_y += a_square
      ellipse_error += y_change
      y_change += a_square
      if (2 * ellipse_error + x_change) > 0
        x -= 1
        stopping_x -= b_square
        ellipse_error += x_change
        x_change += b_square
      end
    end      
    
  end

  #
  # The method increments x and decides when to decrement y testing
  # the sign of a function.  In this case, the decision function is
  # (2*ellipse_error+y_change) and its value is calculated
  # iteratively.
  #
  def draw_second_set(a, b, a_square, b_square)
    
    x, y = 0, b
    x_change, y_change = b**2, a**2 * (1 - 2 * b)
    stopping_x, stopping_y = 0, a_square * b
    ellipse_error = 0
    
    while stopping_x <= stopping_y do
      plot_four_points(x, y)
      x += 1
      stopping_x += b_square
      ellipse_error += x_change
      x_change += b_square
      if (2 * ellipse_error + y_change) > 0
        y -= 1
        stopping_y -= a_square
        ellipse_error += y_change
        y_change += a_square
      end
    end  
    
  end
 
end

# Usage:
#
# ruby circle.rb 7 #=> print out a circle of radius 7
#
# ruby circle.rb 7 1.8 #=> print out a circle of radius 7 and aspect 
ratio 1.8
#
# ruby circle.rb 7 1.8 x #=> print out a circle of radius 7 and aspect 
ratio 1.8
#                            using the ascii char 'x'
#

print Circle.new(ARGV[0], ARGV[1] || 1.0, ARGV[2] || '#').to_s if $0 == 
__FILE__