Velocity Reviews > Ruby > [QUIZ] The Smallest Circle (#157)

# [QUIZ] The Smallest Circle (#157)

Matthew D Moss
Guest
Posts: n/a

 02-15-2008
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://

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem
helps everyone
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(, :y)
def self.random
Point.new(rand, rand)
end

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

def to_s
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

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.

Guest
Posts: n/a

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

If one of the points is on the enclosing circle, is that a valid solution ?

Lionel Bouton
Guest
Posts: n/a

 02-15-2008
> If one of the points is on the enclosing circle, is that a valid solution ?
>
>

I wouldn't care about such details :
the points are defined by floating point coordinates : I'd say that
defining a circle with a center and a radius in floating point which
passes exactly through such points is most often impossible.
There are obvious exceptions like circles with zero radius and some
values where there's no approximation in the computations but these
cases aren't likely to matter here.

Lionel

Matthew Moss
Guest
Posts: n/a

 02-15-2008
On Feb 15, 1:06 pm, "Horea Raducan" <(E-Mail Removed)> wrote:
> If one of the points is on the enclosing circle, is that a valid solution ?

Yes, points on the circle are considered enclosed.

Which also means that for an input set of one point, your function
should return a circle with that point as its center and a zero

Alex Shulgin
Guest
Posts: n/a

 02-16-2008
On Feb 15, 3:19 pm, Matthew D Moss <(E-Mail Removed)> wrote:
>
> 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(, :y)
> def self.random
> Point.new(rand, rand)
> end

May I propose a bit refined random method?

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

This should give us negative coordinates as well.

--
Cheers and welcome new quizmasters!
Alex

John Joyce
Guest
Posts: n/a

 02-16-2008
Interesting, the numbering is continuing from Ruby Quiz ?
Not starting at 1???

SUGGESTION: I don't have time to do this quiz, but it looks like fun.
I for one would encourage anybody to do it with some visual
representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL,
etc...)
An audio representation could be interesting as well (perhaps a sort
of sonar?)

Todd Benson
Guest
Posts: n/a

 02-16-2008
On Feb 16, 2008 3:21 PM, John Joyce <(E-Mail Removed)> wrote:
> Interesting, the numbering is continuing from Ruby Quiz ?
> Not starting at 1???
>
> SUGGESTION: I don't have time to do this quiz, but it looks like fun.

I also would love to do this one, but am on vacation

I hope there's someone out there that supplies a multidimensional
solution (something that gives the user a choice of the dimensional
space; 3-D, 4-D, etc).

> I for one would encourage anybody to do it with some visual
> representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL,
> etc...)
> An audio representation could be interesting as well (perhaps a sort
> of sonar?)

Those would be pretty interesting.

Todd

Matthew Moss
Guest
Posts: n/a

 02-17-2008
> May I propose a bit refined random method?
>
> =A0 =A0 =A0class Point < Struct.new(, :y)
> =A0 =A0 =A0 =A0 =A0def self.random
> =A0 =A0 =A0 =A0 =A0 =A0 =A0Point.new(0.5 - rand, 0.5 - rand)
> =A0 =A0 =A0 =A0 =A0end
>
> This should give us negative coordinates as well.

Sure, but your algorithm should work with any set of random points,
whether they fit in the unit square from 0 to 1, -0.5 to 0.5, or
coordinates outside the unit square.

Bill Kelly
Guest
Posts: n/a

 02-17-2008

From: "John Joyce" <(E-Mail Removed)>
>
> SUGGESTION: I don't have time to do this quiz, but it looks like fun.
> I for one would encourage anybody to do it with some visual
> representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL,
> etc...)

Here's an OpenGL/GLUT-based visualizer for the quiz:

http://tastyspleen.net/~billk/ruby/q...sualization.rb

The visualizer is designed to run with any quiz solution that
provides the encircle() and generate_samples(n) methods at
outer scope.

A screenshot for those curious, but not curious enough to actually
try installing ruby OpenGL bindings ... <grin>

http://tastyspleen.net/~billk/ruby/q...le/157_vis.png

NOTE: I've only tried this program on ruby 1.8.4 so far... I have
no idea if it might run on 1.9 ...

Also... I believe I'm using yoshi's opengl-0.32f bindings. I haven't
tried it with the very latest ruby/OpenGL bindings on rubyforge.

Regards,

Bill

Alex Shulgin
Guest
Posts: n/a

 02-17-2008
On Feb 17, 8:59 am, Bill Kelly <(E-Mail Removed)> wrote:
> From: "John Joyce" <(E-Mail Removed)>
>
>
>
> > SUGGESTION: I don't have time to do this quiz, but it looks like fun.
> > I for one would encourage anybody to do it with some visual
> > representation! (suggested libs: RMagick, Gosu, Rubygame, Ruby/SDL,
> > etc...)

>
> Here's an OpenGL/GLUT-based visualizer for the quiz:
>
> http://tastyspleen.net/~billk/ruby/q...rcle/157_small...

I'm trying to utilize gnuplot for visualization. With any luck I can
post the visual part without spoiling the quiz.

Anyone interested?

--
Alex