Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   Ruby (http://www.velocityreviews.com/forums/f66-ruby.html)
-   -   [QUIZ] The Smallest Circle (#157) (http://www.velocityreviews.com/forums/t848149-quiz-the-smallest-circle-157-a.html)

Matthew D Moss 02-15-2008 01:19 PM

[QUIZ] The Smallest Circle (#157)
 
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.


Horea Raducan 02-15-2008 06:06 PM

Re: [QUIZ] The Smallest Circle (#157)
 
[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 02-15-2008 06:26 PM

Re: [QUIZ] The Smallest Circle (#157)
 
Horea Raducan wrote:
> 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 02-15-2008 06:59 PM

Re: The Smallest Circle (#157)
 
On Feb 15, 1:06 pm, "Horea Raducan" <hradu...@gmail.com> 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
radius.


Alex Shulgin 02-16-2008 01:10 PM

Re: The Smallest Circle (#157)
 
On Feb 15, 3:19 pm, Matthew D Moss <matthew.m...@gmail.com> 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(:x, :y)
> def self.random
> Point.new(rand, rand)
> end


May I propose a bit refined random method?

class Point < Struct.new(:x, :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 02-16-2008 09:21 PM

[Quiz] The Smallest Circle (#157)
 
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 02-16-2008 11:21 PM

Re: [Quiz] The Smallest Circle (#157)
 
On Feb 16, 2008 3:21 PM, John Joyce <dangerwillrobinsondanger@gmail.com> 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 02-17-2008 03:24 AM

Re: The Smallest Circle (#157)
 
> May I propose a bit refined random method?
>
> =A0 =A0 =A0class Point < Struct.new(:x, :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 02-17-2008 06:59 AM

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

From: "John Joyce" <dangerwillrobinsondanger@gmail.com>
>
> 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 02-17-2008 08:58 AM

Re: The Smallest Circle (#157)
 
On Feb 17, 8:59 am, Bill Kelly <bi...@cts.com> wrote:
> From: "John Joyce" <dangerwillrobinsondan...@gmail.com>
>
>
>
> > 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


All times are GMT. The time now is 03:56 AM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.