Re: [QUIZ] The Smallest Circle (#157)

Hello,

Had a lot of fun with this one :) My solution works by taking the average of
all points as the center, and the farthest outlying point as the radius. An
optimal solution is then found by moving the circle center towards the
outlier as the radius is reduced, while all points still are within the
radius. The same principles could be applied for higher dimensions as well.

class Point < Struct.new(:x, :y)
    def self.random
        Point.new(rand, rand)
    end

    def to_s
        "(#{x}, #{y})"
    end
end

class Circle < Struct.new(:center, :radius)
    def to_s
        "{center:#{center}, radius:#{radius}}"
    end
end

# Calculate distance between points
def distance(pt_a, pt_b)
  Math.sqrt((pt_a.x - pt_b.x) * (pt_a.x - pt_b.x) +
            (pt_a.y - pt_b.y) * (pt_a.y - pt_b.y))
end

# Determine if given points are all within a circle
def inside_circle?(points, circle)
  for point in points
    dist = distance(point, circle.center)
    return false if dist > circle.radius
  end
  true
end

def encircle(points)        # takes array of Point objects
  # find the average midpoint of all points
  mid = Point.new(
    points.inject(0){|sum, pt| sum += pt.x} / (points.size * 1.0),
    points.inject(0){|sum, pt| sum += pt.y} / (points.size * 1.0))

  # sort points by longest distance from midpoint
  # longest point (index 0) is the initial radius
  points.sort!{|a,b| distance(mid, a) <=> distance(mid, b) }.reverse!

  # Taking the average midpoint does not necessarily work because the points
may
  # be weighted more heavily to one side. We correct for this by sliding the
circle
  # along the line from its original center to the outmost point, decreasing
the
  # radius as we go. Keep doing this until the circle can be made no
smaller.
  point = points[0]
  slope = (mid.y - point.y) / (mid.x - point.x)
  new_pt, delta, sign = mid, 0.0, 1.0
  sign = -1.0 if mid.x > point.x
  while inside_circle?(points, Circle.new(new_pt, distance(new_pt, point)))
    mid = new_pt
    delta += 0.000001 * sign
    new_pt = Point.new(mid.x + delta, mid.y + (slope * (delta)))
  end

  return Circle.new(mid, distance(mid, point))
end

def generate_samples(n)
    (1..n).map { Point.random }
end


Here are Pasties of the program and a RMagick script to generate images:

Algorithm: http://pastie.caboo.se/153387
Graphics code: http://pastie.caboo.se/153388
Images:
 http://justin.ethier.googlepages.com/157_jae_25_2.jpg
 http://justin.ethier.googlepages.com/157_jae_100_0.jpg
 http://justin.ethier.googlepages.com/157_jae_1000_3.jpg

Thanks,

Justin

On Feb 15, 2008 8:19 AM, Matthew D Moss <[e-mail]> wrote:

> 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://
> matthew.moss.googlepages.com/home>.
>
> 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.
>
> -=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
> =-=-=-
>
> The Smallest Circle
> by Matthew Moss
>
> Your task this week sounds simple enough, but may be more difficult
> than it first appears. Given a set of points on a plane, your goal is
> to find the smallest circle that encloses those points.
>
> You are to provide a function, *encircle*, that takes an array of
> points and returns the smallest circle surrounding those points.
> Start with the following base code and extend as needed to solve the
> problem:
>
>     class Point < Struct.new(:x, :y)
>         def self.random
>             Point.new(rand, rand)
>         end
>
>         def to_s
>             "(#{x}, #{y})"
>         end
>     end
>
>     class Circle < Struct.new(:center, :radius)
>         def to_s
>             "{center:#{center}, radius:#{radius}}"
>         end
>     end
>
>     def encircle(points)        # takes array of Point objects
>         # returns a Circle object
>     end
>
>
> I will be running several tests on the submitted solutions, with
> various point sets, to see how well they perform at this task. I
> recommend you you test your algorithm with a variety of sample sets,
> from small sets consisting of just 1-5 points, up to medium and
> larger sets, containing a few thousand points.
>
> To generate an array of random points, start with the above code and
> add:
>
>     def generate_samples(n)
>         (1..n).map { Point.random }
>     end
>
>
> And then you may test your implementation like this:
>
>     # encircle 10 random points
>     puts encircle( generate_samples(10) )
>
>
> As mentioned, this one may be more difficult than it seems. Feel free
> to estimate the smallest circle, if you get stuck on getting the
> exact solution.
>
>