Velocity Reviews - Computer Hardware Reviews

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

Reply
Thread Tools

[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://
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(, :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.

 
Reply With Quote
 
 
 
 
Horea Raducan
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 ?

 
Reply With Quote
 
 
 
 
Lionel Bouton
Guest
Posts: n/a
 
      02-15-2008
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

 
Reply With Quote
 
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
radius.

 
Reply With Quote
 
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
 
Reply With Quote
 
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?)

 
Reply With Quote
 
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

 
Reply With Quote
 
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.

 
Reply With Quote
 
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



 
Reply With Quote
 
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
WinXP + 350 Cisco card vicious circle... =?Utf-8?B?aG9tZXBpeGVscw==?= Wireless Networking 1 05-02-2005 10:23 PM
Jisatsu circle (Suicide Circle) Col's Cavern DVD Video 1 06-07-2004 06:55 PM
moving label in c# around circle =?Utf-8?B?dGFnaHJlZWQ=?= ASP .Net 1 05-03-2004 04:27 PM
Circle Hell Talon Perl 2 09-04-2003 07:25 PM



Advertisments