[#289458] Parsing JSON (#155) — Ruby Quiz <james@...>

The three rules of Ruby Quiz:

86 messages 2008/02/01
[#289675] Re: [QUIZ] Parsing JSON (#155) — steve <oksteev@...> 2008/02/03

Hey guys

[#289709] Re: [QUIZ] Parsing JSON (#155) — "Eric Mahurin" <eric.mahurin@...> 2008/02/04

On Feb 3, 2008 8:14 AM, steve <oksteev@yahoo.com> wrote:

[#289712] Re: [QUIZ] Parsing JSON (#155) — Clifford Heath <no@...> 2008/02/04

Eric Mahurin wrote:

[#289715] Re: [QUIZ] Parsing JSON (#155) — "Eric Mahurin" <eric.mahurin@...> 2008/02/04

On Feb 3, 2008 6:25 PM, Clifford Heath <no@spam.please.net> wrote:

[#289718] Re: [QUIZ] Parsing JSON (#155) — Clifford Heath <no@...> 2008/02/04

Eric Mahurin wrote:

[#289722] Re: [QUIZ] Parsing JSON (#155) — "Eric Mahurin" <eric.mahurin@...> 2008/02/04

On Feb 3, 2008 6:39 PM, Clifford Heath <no@spam.please.net> wrote:

[#289557] Comparing Active Record VS Datamapper...? — Softmind Technology <softmindtechnology@...>

Hello,

15 messages 2008/02/02
[#289633] Re: Comparing Active Record VS Datamapper...? — Ilan Berci <coder68@...> 2008/02/02

Softmind Technology wrote:

[#289636] Re: Comparing Active Record VS Datamapper...? — "s.ross" <cwdinfo@...> 2008/02/03

On 2/2/08 3:56 PM, "Ilan Berci" <coder68@yahoo.com> wrote:

[#289572] Extracting vowels and consonants using regular expression — Dondi <Donovan.Dillon@...>

I am trying to parse a string and extract all vowels and consonants

10 messages 2008/02/02

[#289579] FastRI 0.3.1: faster, Leopard compatibility, etc. — Mauricio Fernandez <mfp@...>

FastRI is an alternative to the ri documentation browser for Ruby.

21 messages 2008/02/02
[#289683] Re: [ANN] FastRI 0.3.1: faster, Leopard compatibility, etc. — botp <botpena@...> 2008/02/03

On Feb 3, 2008 1:07 AM, Mauricio Fernandez <mfp@acm.org> wrote:

[#290164] Re: [ANN] FastRI 0.3.1: faster, Leopard compatibility, etc. — Eric Hodel <drbrain@...7.net> 2008/02/06

On Feb 3, 2008, at 07:40 AM, botp wrote:

[#291478] Re: [ANN] FastRI 0.3.1: faster, Leopard compatibility, etc. — Mauricio Fernandez <mfp@...> 2008/02/18

On Thu, Feb 07, 2008 at 07:52:20AM +0900, Eric Hodel wrote:

[#291493] Re: [ANN] FastRI 0.3.1: faster, Leopard compatibility, etc. — James Gray <james@...> 2008/02/18

On Feb 18, 2008, at 5:53 AM, Mauricio Fernandez wrote:

[#289674] Ruby for game programming — t3chn0n3rd <darrin_allen@...>

Is anyone using Ruby for game programming?

17 messages 2008/02/03

[#289859] how to say # in ruby — Dan Ford <wade@...>

I'm accustomed to usenet as opposed to whatever this is.

22 messages 2008/02/04

[#289900] Introducing Waves - Web App Framework — Dan Yoder <dan@...>

I am pleased to announce the first beta release of Waves, an open-

32 messages 2008/02/05
[#290017] Re: [ANN] Introducing Waves - Web App Framework — Daniel DeLorme <dan-ml@...42.com> 2008/02/06

Dan Yoder wrote:

[#290001] Computer Science Problems — markonlinux@...

Hi all,

33 messages 2008/02/05

[#290020] Ruby type-safe? Ruby strongly/weakly typed? Ruby pitfalls? — "rule.rule.rule@..." <rule.rule.rule@...>

Hi,

36 messages 2008/02/06

[#290022] simple ruby proxy server? — Dt Town <dtown22@...>

I am trying to right at application which will simply record the headers

13 messages 2008/02/06

[#290167] Array Practice — Adam Akhtar <adamtemporary@...>

As some of you may know from previous threads im trying to practice

27 messages 2008/02/06

[#290195] info on block arguments — Russell Me <russ@...>

I'm trying to pick up ruby and I'm impressed by all the cool stuff it

24 messages 2008/02/07

[#290208] idiom I've not seen before — Rob Saul <wyrd@...>

12 messages 2008/02/07

[#290244] Parsing JSON (#155) — Ruby Quiz <james@...>

We saw a large variety of solutions for this week's problem. Many of them used

13 messages 2008/02/07

[#290245] using net::ssh shell to sudo to another user and execute commands — "wbsurfver@..." <wbsurfver@...>

11 messages 2008/02/07

[#290272] is lots of files with Threads faster? — Chris Richards <evilgeenius@...>

Im required to open 50+ files and parse the data in them. WOuld using

11 messages 2008/02/07

[#290296] BigDecimal.new('15.25') == 15.25, false ?? — Henry Jones <mathieu.houle@...>

Hi,

14 messages 2008/02/07

[#290328] trouble with FileUtils.rm() -- Invalid arguement error — an an <dtown22@...>

I have been screwing with this for the last hour, and I still cant get

12 messages 2008/02/08

[#290374] Internal Rate of Return (#156) — Ruby Quiz <james@...>

The three rules of Ruby Quiz:

47 messages 2008/02/08

[#290483] Beginner help - txt dungeon — Jonathon Hartoon <ezrickknight@...>

Hi. I have tried to learn other programming languages before and ruby

20 messages 2008/02/09

[#290716] non case sensitive searching — Adam Akhtar <adamtemporary@...>

If i want to see if a list contains a particular word how would i go

15 messages 2008/02/11

[#290735] Rev/actor TCP monkey patching — fedzor <fedzor@...>

Short and sweet -

13 messages 2008/02/11

[#290825] How do C programmers do unit testing? — "M. Edward (Ed) Borasky" <znmeb@...>

This may seem like a silly question, but how do C programmers (assume

13 messages 2008/02/12

[#290931] Robert's Ruby Riddle: Local or Method — "Robert Dober" <robert.dober@...>

Hi list I was just thinking it might fun to present some of Ruby's

10 messages 2008/02/13

[#290982] ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...>

I recently upgraded to ruby 1.8.6 on mac os x 10.4.7. I had ruby tk

47 messages 2008/02/13
[#290994] Re: ruby tk -- how do you get it working? — Jeremy Henty <onepoint@...> 2008/02/13

On 2008-02-13, 7stud -- <bbxx789_05ss@yahoo.com> wrote:

[#291001] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/14

Jeremy Henty wrote:

[#291006] Re: ruby tk -- how do you get it working? — Hidetoshi NAGAI <nagai@...> 2008/02/14

From: 7stud -- <bbxx789_05ss@yahoo.com>

[#291014] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/14

Hidetoshi NAGAI wrote:

[#291447] Re: ruby tk -- how do you get it working? — Hidetoshi NAGAI <nagai@...> 2008/02/18

From: 7stud -- <bbxx789_05ss@yahoo.com>

[#291459] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/18

Hidetoshi NAGAI wrote:

[#291519] Re: ruby tk -- how do you get it working? — Morton Goldberg <m_goldberg@...> 2008/02/18

On Feb 18, 2008, at 2:52 AM, 7stud -- wrote:

[#291529] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/18

Morton Goldberg wrote:

[#291556] Re: ruby tk -- how do you get it working? — Morton Goldberg <m_goldberg@...> 2008/02/19

On Feb 18, 2008, at 3:05 PM, 7stud -- wrote:

[#291567] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/19

Morton Goldberg wrote:

[#291601] Re: ruby tk -- how do you get it working? — Morton Goldberg <m_goldberg@...> 2008/02/19

On Feb 18, 2008, at 10:28 PM, 7stud -- wrote:

[#291603] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/19

Morton Goldberg wrote:

[#291621] Re: ruby tk -- how do you get it working? — Morton Goldberg <m_goldberg@...> 2008/02/19

On Feb 19, 2008, at 7:05 AM, 7stud -- wrote:

[#291626] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/19

Morton Goldberg wrote:

[#291637] Re: ruby tk -- how do you get it working? — John Joyce <dangerwillrobinsondanger@...> 2008/02/19

[#291707] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/20

John Joyce wrote:

[#291742] Re: ruby tk -- how do you get it working? — Morton Goldberg <m_goldberg@...> 2008/02/20

On Feb 19, 2008, at 7:41 PM, 7stud -- wrote:

[#291747] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/20

Morton Goldberg wrote:

[#291819] Re: ruby tk -- how do you get it working? — "Leslie Viljoen" <leslieviljoen@...> 2008/02/20

On Feb 20, 2008 8:59 AM, 7stud -- <bbxx789_05ss@yahoo.com> wrote:

[#291846] Re: ruby tk -- how do you get it working? — John Joyce <dangerwillrobinsondanger@...> 2008/02/20

[#291967] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/21

John Joyce wrote:

[#292774] Re: ruby tk -- how do you get it working? — Tim Ferrell <s0nspark@...> 2008/02/27

7stud -- wrote:

[#292964] Re: ruby tk -- how do you get it working? — 7stud -- <bbxx789_05ss@...> 2008/02/29

Tim Ferrell wrote:

[#292971] Re: ruby tk -- how do you get it working? — Tim Ferrell <s0nspark@...> 2008/02/29

7stud -- wrote:

[#292992] Re: ruby tk -- how do you get it working? — Tim Ferrell <s0nspark@...> 2008/02/29

Tim Ferrell wrote:

[#290985] my noob "numbering lines" programe. How to improve? — Adam Akhtar <adamtemporary@...>

Give us hints on how to improve this program. If you want to show your

11 messages 2008/02/13

[#291013] Memcached: Dealing with unknown keys — Tony Garcia <tony23@...>

I was wondering if there is a way to handle reading keys when you don't

14 messages 2008/02/14

[#291039] Internal Rate of Return (#156) — Ruby Quiz <james@...>

Solving the IRR equation is essentially a matter of computational guesswork.

15 messages 2008/02/14

[#291084] object specific methods and id — UpsNDowns <tnospamhomas@...>

Hi,

24 messages 2008/02/14
[#291088] Re: object specific methods and id — 7stud -- <bbxx789_05ss@...> 2008/02/14

UpsNDowns wrote:

[#291089] Re: object specific methods and id — Gary Wright <gwtmp01@...> 2008/02/14

[#291184] Re: object specific methods and id — UpsNDowns <tnospamhomas@...> 2008/02/15

Thanks for the reply.

[#291261] Re: object specific methods and id — Gary Wright <gwtmp01@...> 2008/02/16

[#291302] Re: object specific methods and id — UpsNDowns <tnospamhomas@...> 2008/02/16

Gary Wright wrote:

[#291141] The Smallest Circle (#157) — Matthew D Moss <matthew.moss@...>

The three rules of Ruby Quiz 2:

61 messages 2008/02/15

[#291192] Proper way to RDoc markup? — Serg Koren <skoren@...>

Hi,

12 messages 2008/02/15

[#291269] Alter String base class to perform new (private methods) before returning itself when called by print statements — "Steven G. Harms" <steven.harms@...>

class String

8 messages 2008/02/16

[#291280] GC error ? — Piotr Sawicki <piotr.sawicki@...>

Run this program and observe memory usage.

26 messages 2008/02/16
[#291584] Re: GC error ? — "evanwebb@..." <evanwebb@...> 2008/02/19

On Feb 16, 4:12=A0am, Piotr Sawicki <piotr.sawi...@gmail.com> wrote:

[#291281] TRAC - Trac, Project Leads, Python, and Mr. Noah Kantrowitz (sanitizer) — Ilias Lazaridis <ilias@...>

Essence:

14 messages 2008/02/16

[#291354] Slide Show v0.1 - A Free Web Alternative to PowerPoint and KeyNote in Ruby Now Live — "Gerald Bauer" <geraldbauer2007@...>

Hello,

12 messages 2008/02/17

[#291381] displaying user inputed arrays — Isaac Toothyxdip <toothyxdip@...>

[code]

36 messages 2008/02/17
[#291405] Re: displaying user inputed arrays — Wally T Terrible <wally.terrible@...> 2008/02/17

I'm not entirely sure what you intend to do. If you wanted to get five

[#291424] Re: displaying user inputed arrays — Siep Korteling <s.korteling@...> 2008/02/17

Wally T Terrible wrote:

[#291858] Re: displaying user inputed arrays — "Todd Benson" <caduceass@...> 2008/02/20

On Feb 17, 2008 9:18 AM, Isaac Toothyxdip <toothyxdip@gmail.com> wrote:

[#291877] Re: displaying user inputed arrays — "Todd Benson" <caduceass@...> 2008/02/20

On Wed, Feb 20, 2008 at 1:30 PM, Todd Benson <caduceass@gmail.com> wrote:

[#291884] Re: displaying user inputed arrays — Isaac Toothyxdip <toothyxdip@...> 2008/02/20

Thanks that works!

[#291887] Re: displaying user inputed arrays — Isaac Toothyxdip <toothyxdip@...> 2008/02/20

Isaac Toothyxdip wrote:

[#291899] Re: displaying user inputed arrays — "Todd Benson" <caduceass@...> 2008/02/20

On Wed, Feb 20, 2008 at 3:56 PM, Isaac Toothyxdip <toothyxdip@gmail.com> wrote:

[#291515] Connecting to HyperTerminal — Active View <active.view@...>

Hi all...

16 messages 2008/02/18
[#291525] Re: Connecting to HyperTerminal — Ben Bleything <ben@...> 2008/02/18

On Tue, Feb 19, 2008, Active View wrote:

[#291630] Object#freeze as a basis for caching of method results? — "Shot (Piotr Szotkowski)" <shot@...>

Hello, ruby-talk.

12 messages 2008/02/19

[#291664] ||= [] idiom — "Leslie Viljoen" <leslieviljoen@...>

I often make use of this idiom to add something to an array in a hash of arrays:

24 messages 2008/02/19

[#291677] Is there any object-oriented File class in ruby ? — tom_33 <tomjbr.56770318@...>

I am very new to Ruby and my question is about trying to understand

22 messages 2008/02/19

[#291682] HELP: Need to continue the loop after the exception — mirth <mirthcyy@...>

hi guys,

12 messages 2008/02/19

[#291717] IP Address to Decimal - is an one-liner possible? — "Tiago Pinto" <thpinto@...>

Hi guys,

22 messages 2008/02/20

[#291774] What does *args do? — Stedwick <philip.brocoum@...>

I sometimes see funcs declared with def fun (blah, *args)

14 messages 2008/02/20

[#291853] 32bit vs 64bit vs UML performance — Lionel Bouton <lionel-subscription@...>

I've run the QUIZ benchmark on several systems to check their relative

17 messages 2008/02/20

[#291990] beginner's problem with sqlite3 — Tom Cloyd <tomcloyd@...>

It would be helpful if the sqlite3-ruby documentation offered one or two

15 messages 2008/02/21

[#292056] Where does instance_eval _magically_ set the variable to? — Andrew Chen <hangfei@...>

Hi,

13 messages 2008/02/21

[#292080] Newbie Mem Leak Issue — Keith Barr <keith.barr@...>

I am fairly new to Ruby and a program that I have created seems to have

14 messages 2008/02/21

[#292186] gsub("\\", "\\\\") seems unintuitive — John Woods <jqwoods@...>

The following confusing behavior is noted in the pickaxe book (2nd ed)

11 messages 2008/02/22

[#292250] ANN: Teach yourself Ruby - the hard way! — "Martin DeMello" <martindemello@...>

A frequent question from Ruby newcomers is "Okay, I've read the

12 messages 2008/02/23

[#292269] Monkeypatching is Destroying Ruby — "Avdi Grimm" <avdi@...>

Hi folks,

118 messages 2008/02/23
[#292274] Re: Monkeypatching is Destroying Ruby — "Eric Mahurin" <eric.mahurin@...> 2008/02/23

On Sat, Feb 23, 2008 at 3:07 PM, Avdi Grimm <avdi@avdi.org> wrote:

[#292385] Re: Monkeypatching is Destroying Ruby — James Gray <james@...> 2008/02/25

On Feb 23, 2008, at 4:23 PM, Eric Mahurin wrote:

[#292281] Re: Monkeypatching is Destroying Ruby — "M. Edward (Ed) Borasky" <znmeb@...> 2008/02/23

Avdi Grimm wrote:

[#292514] Re: Monkeypatching is Destroying Ruby — "Michal Suchanek" <hramrach@...> 2008/02/25

On 24/02/2008, M. Edward (Ed) Borasky <znmeb@cesmail.net> wrote:

[#292584] Re: Monkeypatching is Destroying Ruby — "Jones, Brian - McClatchy Interactive" <bjones@...> 2008/02/26

I'd be at least a little interested in potentially offering developers

[#292594] Re: Monkeypatching is Destroying Ruby — Trans <transfire@...> 2008/02/26

[#292601] Re: Monkeypatching is Destroying Ruby — James Britt <james.britt@...> 2008/02/26

Trans wrote:

[#292603] Re: Monkeypatching is Destroying Ruby — "Avdi Grimm" <avdi@...> 2008/02/26

On Tue, Feb 26, 2008 at 1:25 PM, James Britt <james.britt@gmail.com> wrote:

[#292362] Re: Monkeypatching is Destroying Ruby — furtive.clown@... 2008/02/24

[#292366] Re: Monkeypatching is Destroying Ruby — Gary Wright <gwtmp01@...> 2008/02/24

[#292961] Re: Monkeypatching is Destroying Ruby — Trans <transfire@...> 2008/02/29

[#292978] Re: Monkeypatching is Destroying Ruby — "Eric Mahurin" <eric.mahurin@...> 2008/02/29

On Fri, Feb 29, 2008 at 6:20 AM, Trans <transfire@gmail.com> wrote:

[#292368] Suprising behaviour with "def property=" method — "Farrel Lifson" <farrel.lifson@...>

I had a bit of a surprise with the following

14 messages 2008/02/24

[#292394] NoMethodError: private method `to_date' — Sukeerthi Adiga <sukeerthiadiga@...>

Loading development environment.

12 messages 2008/02/25

[#292398] Thread#raise, Thread#kill, and timeout.rb are unsafe — Charles Oliver Nutter <charles.nutter@...>

I wrote up an article on Thread#raise, Thread#kill, and timeout.rb that

58 messages 2008/02/25
[#294446] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Yukihiro Matsumoto <matz@...> 2008/03/13

Hi,

[#294479] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Paul Brannan <pbrannan@...> 2008/03/13

On Fri, Mar 14, 2008 at 01:02:52AM +0900, Yukihiro Matsumoto wrote:

[#294491] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Yukihiro Matsumoto <matz@...> 2008/03/13

Hi,

[#294551] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Paul Brannan <pbrannan@...> 2008/03/14

On Fri, Mar 14, 2008 at 07:43:28AM +0900, Yukihiro Matsumoto wrote:

[#294559] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Yukihiro Matsumoto <matz@...> 2008/03/14

Hi,

[#294591] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Tanaka Akira <akr@...> 2008/03/14

In article <E1JaB7P-0000Zc-QP@x61.netlab.jp>,

[#294639] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Yukihiro Matsumoto <matz@...> 2008/03/15

Hi,

[#294917] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Tanaka Akira <akr@...> 2008/03/18

In article <E1JaM9H-0000jj-AB@x61.netlab.jp>,

[#295093] Re: Thread#raise, Thread#kill, and timeout.rb are unsafe — Paul Brannan <pbrannan@...> 2008/03/19

On Tue, Mar 18, 2008 at 02:04:40PM +0900, Tanaka Akira wrote:

[#292540] Math problem — grandmabeckie@...

I am try to help my daughter:

25 messages 2008/02/26

[#292704] Getting number of days in a month — Shandy Nantz <shandybleu@...>

This is probably an easy question but I am trying to get at the number

26 messages 2008/02/27

[#292781] MacRuby — "Laurent Sansonetti" <laurent.sansonetti@...>

Hi,

16 messages 2008/02/28

[#292795] Need a regex searching html code — Chirantan <chirantan.rajhans@...>

I have an html code into string. I want to retrieve the content (Can

18 messages 2008/02/28

[#292816] proc.new and return — S2 <email@...>

I am sure this is a really easy question for most of you, but i was not

15 messages 2008/02/28

[#292839] Proposed Solutions - Was [ Re: Monkeypatching is Destroying Ruby ] — hemant <gethemant@...>

On Tue, Feb 26, 2008 at 11:55 PM, James Britt <james.britt@gmail.com> wrote:

17 messages 2008/02/28

[#292860] Named sprintf parameters — Trans <transfire@...>

I have a question and perhaps a bit of challenge for those with mad

15 messages 2008/02/28

[#292865] constants defined in Kernel are also defined in Object? — Paul Brannan <pbrannan@...>

This seems peculiar to me:

15 messages 2008/02/28

[#293044] making a monthly calendar... — Mikkel Bruun <mikkel@...>

Hey

25 messages 2008/02/29
[#293088] Re: making a monthly calendar... — "Todd Benson" <caduceass@...> 2008/03/01

On Fri, Feb 29, 2008 at 4:30 PM, Mikkel Bruun <mikkel@helenius.dk> wrote:

[#293090] Re: making a monthly calendar... — Mikkel Bruun <mikkel@...> 2008/03/01

Todd Benson wrote:

[#293092] Re: making a monthly calendar... — "Todd Benson" <caduceass@...> 2008/03/01

On Sat, Mar 1, 2008 at 2:34 AM, Mikkel Bruun <mikkel@helenius.dk> wrote:

[#293223] Re: making a monthly calendar... — "Todd Benson" <caduceass@...> 2008/03/03

Oh my goodness! A thousand apologies. I gave you a rotating month. See below.

[#293264] Re: making a monthly calendar... — Mikkel Bruun <mikkel@...> 2008/03/03

So I ended up with:

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

From: Philipp Hofmann <phil@...126.de>
Date: 2008-02-18 23:27:07 UTC
List: ruby-talk #291548
Here is my solution. Although it uses a brute force approach if the
first attempts (driven by obvious constraints) of determining the
circle fail, it scales on larger sets, because the given equal
distibution of random points form an approximate square on these
sets. In that case the convex hull which is used for the brute force
has very few points.

I also did some visualization with RMagick.

g phil

Attachments (1)

smallest_enclosing_circle.rb (7.23 KB, text/x-ruby)
class Point < Struct.new(:x, :y) 
  def self.random
    Point.new(rand, rand)
  end
  
  def to_s 
    "(#{x}, #{y})" 
  end

  def distance(p)
    Math.sqrt((x-p.x)**2+(y-p.y)**2)
  end

  def middle(p)
    Point.new((self.x+p.x)/2, (self.y+p.y)/2)
  end
end
 
class Circle < Struct.new(:center, :radius)
  def to_s 
    "{center:#{center}, radius:#{radius}}" 
  end
end
 
def generate_samples(n)
  (1..n).map { Point.random }
end

def encircle(points)

  # only one point? then we're done
  return Circle.new(points.first, 0) if points.size==1

  # firstly, we calculate the convex hull
  # this will reduce points to calculate
  # especially for larger sets
  hull = ConvexHull::convex_hull(points)
  draw_hull(hull.clone, :lightgray) if VISUALIZE

  # find the two spots on the hull with the larges distance
  # these will make a good starting point
  distances0 = {}
  list_of_points = hull.clone
  until list_of_points.empty?
    p1 = list_of_points.shift
    list_of_points.each do |p2|
      distances0[[p1, p2]] = p1.distance(p2)
    end
  end
  max0 = distances0.values.max
  p0, p1 = distances0.invert[max0]
  circle0 = Circle.new(p0.middle(p1), max0/2)
  hull.delete(p0)
  hull.delete(p1)

  # we're done if the hull only had two points
  return circle0 if hull.empty?
  # find the point that has the largest
  # distance to the center of circle0
  distances1 = {} 
  hull.each do |point|
    distances1[point] = circle0.center.distance(point)
  end
  max1 = distances1.values.max
  # if the farest point from center is
  # closer then the radius we're done
  draw_circle(circle0.center, circle0.radius, :green) if VISUALIZE
  return circle0 if max1 <= circle0.radius

  p2 = distances1.invert[max1]
  circle1 = SOLE::circle_of(p0, p1, p2)
  hull.delete(p2)
  # find the point that has the largest
  # distance to the center of circle1
  distances2 = {}
  hull.each do |point|
    distances2[point] = circle1.center.distance(point)
  end
  max2 = distances2.values.max
  # if the farest point from center is in the circle we're done
  draw_circle(circle1.center, circle1.radius, :blue) if VISUALIZE
  return circle1 if max2 <= circle1.radius
  
  # ok, now we fall back to brute force on the convex hull
  # we can do this because the random distribution given
  # leads to an approximate square and therefore to convex hulls
  # with very few points, if this weren't the case we should
  # uses clarksons probabilistic approach here, especcially
  # for larger sets of points.
  hull.concat([p0, p1, p2])
  sets_of_three = SubSet::subsets(hull, 3)
  solutions = []
  sets_of_three.each do |subset|
    circle2 = SOLE::circle_of(*subset)
    distances3 = {}
    hull.each do |p3|
      distances3[p3] = circle2.center.distance(p3) unless subset.include?(p3)
    end
    max3 = distances3.values.max
    solutions << circle2 if max3 <= circle2.radius
  end

  circle3 = solutions.sort_by { |circle| circle.radius }.first
  draw_circle(circle3.center, circle3.radius, :red) if VISUALIZE
  return circle3

end

# --- calculate subsets

module SubSet
  
  # i admit this could definitly be improved
  def self.subsets(set, ranks=nil)
    ranks ||= 0..set.size
    ranks = ranks..ranks unless ranks.is_a?(Range)
    sets = all_subsets(set)
    sets.select { |s| ranks.include?(s.size) }
  end
  
  def self.all_subsets(set)
    return [[]] if set.empty?
    set = set.clone
    first = set.shift
    sets = all_subsets(set)
    sets.concat(sets.collect { |s| [first] + s })
    return sets
  end
  
end

# --- calculate the convex hull

module ConvexHull

  # after graham & andrew
  def self.convex_hull(points)
    lop = points.sort_by { |p| p.x }
    left = lop.shift
    right = lop.pop
    lower, upper = [left], [left]
    lower_hull, upper_hull = [], []
    det_func = determinant_function(left, right)
    until lop.empty?
      p = lop.shift
      ( det_func.call(p) < 0 ? lower : upper ) << p
    end
    lower << right
    until lower.empty?
      lower_hull << lower.shift
      while (lower_hull.size >= 3) &&
          !convex?(lower_hull.last(3), true)
        last = lower_hull.pop
        lower_hull.pop
        lower_hull << last
      end
    end
    upper << right
    until upper.empty?
      upper_hull << upper.shift
      while (upper_hull.size >= 3) &&
          !convex?(upper_hull.last(3), false)
        last = upper_hull.pop
        upper_hull.pop
        upper_hull << last
      end
    end
    upper_hull.shift
    upper_hull.pop
    lower_hull + upper_hull.reverse
  end
  
  private

  def self.determinant_function(p0, p1)
    proc { |p| ((p0.x-p1.x)*(p.y-p1.y))-((p.x-p1.x)*(p0.y-p1.y)) }
  end
  
  def self.convex?(list_of_three, lower)
    p0, p1, p2 = list_of_three
    (determinant_function(p0, p2).call(p1) > 0) ^ lower
  end
  
end

# --- calculate a circle out of three given points

module SOLE
  
  def self.circle_of(*three_points)
    m = sole_matrix_for_circle(three_points)
    solve_sole!(m)
    x = m[1].last
    y = m[2].last
    r = Math.sqrt(x*x + y*y - m[0].last)
    Circle.new(Point.new(x, y), r)
  end
  
  private

  def self.sole_matrix_for_circle(points)
    matrix = []
    c = 0
    points.each do |p|
      matrix[c] = [1]
      matrix[c] << -2 * p.x
      matrix[c] << -2 * p.y
      matrix[c] << -p.x**2 - p.y**2
      c += 1
    end
    matrix
  end
  
  # solve system of linear equations
  def self.solve_sole!(matrix) 
    num_equations = matrix.size
    num_variables = matrix.first.size
    (num_variables-1).times do |j|
      q = matrix[j][j]
      if q == 0
        for i in j+1..num_equations-1 do
          if matrix[i][j] != 0
            for k in 0..num_variables-1 do
              matrix[j][k] += matrix[i][k]
            end
            q = matrix[j][j]
            break
          end
        end
      end
      if q != 0
        for k in 0..num_variables-1
          matrix[j][k] = matrix[j][k] / q
        end
      end
      for i in 0..num_equations-1
        if i != j
          q = matrix[i][j]
          for k in 0..num_variables-1
            matrix[i][k] -= matrix[j][k] * q
          end
        end
      end
    end
  end
  
end

# ----- visualize

def scale(value)
  $size / 6 + value * $size / 1.5
end

def draw_circle(center, radius, color=false)
  $gc.stroke_color(color.to_s) if color
  $gc.circle(scale(center.x), scale(center.y), scale(center.x), scale(center.y+radius))
end

def draw_point(center, color=false)
  $gc.stroke_color(color.to_s) if color
  $gc.circle(scale(center.x), scale(center.y), scale(center.x), scale(center.y)+2)
end

def draw_line(p0, p1, color=false)
  $gc.stroke_color(color.to_s) if color
  $gc.line(scale(p0.x), scale(p0.y), scale(p1.x), scale(p1.y))
end

def draw_hull(points, color=false)
  first = points.shift
  prev = first
  until points.empty?
    p = points.shift
    draw_line(prev, p, color)
    prev = p
  end
  draw_line(prev, first, color)
end

# ----- if executed directly

if __FILE__ == $0
  
  VISUALIZE = true

  if VISUALIZE
    require 'RMagick'
    $size = 600
    $gc = Magick::Draw.new
    $gc.fill_opacity(0)
    $gc.stroke_width(2)
    $gc.stroke_opacity(1)
  end
  
  samples = generate_samples(ARGV[0].to_i)
  circle = encircle(samples)
  puts circle
  
  if VISUALIZE
    samples.each { |p| draw_point(p, :black) }
    canvas = Magick::ImageList.new
    canvas.new_image($size, $size)
    $gc.draw(canvas)
    canvas.display
  end
  
end

In This Thread