Minimum Enclosing Circle in Ruby
(click to enlarge)
This is a solution of Ruby Quiz #157: The Smallest Circle. The problem is to find the smallest circle that encloses a given set of points. In order to solve it, I Googled around and found the following websites with Java solutions:
- rmuhamma's solution at Kent University
- Jacob Eliosoff and Richard Unger's solution at McGill School of Computer Science
Writing this code turned out to be more of a challenge than I anticipated because I did it late at night and made a bunch of newbish mistakes. One pernicious problem was forgetting to ensure that a method I wrote returned the right thing. I forgot to put an explicit return statement in the method that calculates the upper or lower half of the Convex Hull of the set of points, but the last evalutated statement, which happened to be the input set of points, was returned by default. This is SOP for ruby, but it bit me and I had to spend a few hours tracing through the complex algorithm until I saw what was going on and fixed it.
Another issue is that the algorithm used to solve this problem is very complex and the code is difficult to understand. I had to take that the algorithm even worked on faith basically. My math skills are so out of date that a proof that it is correct would be lost on me.
I ended up getting it right in the end I think. Some quick benchmarks show that the solution scales roughly at O(Cn) (some constant linear multiplier of the number of points being enclosed).
$ ruby mec.rb benchmark
user system total real
points: 1 0.010000 0.000000 0.010000 ( 0.004706)
points: 10 0.130000 0.000000 0.130000 ( 0.136395)
points: 100 1.390000 0.090000 1.480000 ( 1.484994)
points: 1000 11.940000 0.800000 12.740000 ( 12.755417)
points: 10000 224.350000 11.700000 236.050000 (238.382341)
Using RMagick For Building Graphics
Perhaps the funnest part of solution was coding up a visualization of the Minimum Enclosing Circle by using RMagick to draw a png of the results (see example to the right). Having the picture along with the debug output was an invaluable tool for validating the results. It also taught me a lot about the RMagick gem and it's capabilities. The interface is clean and really fun to work with.
Running the Code
The code is available in pretty printed HTML format or you can download the source code here. To get usage information, run the code with no arguments.
$ ruby mec.rb
Usage: ruby mec.rb [draw [num_points]] | [benchmark] | [once [num_points]]
once: Runs the solution once and puts the circle
num_points defaults to 15 if not specified.
draw: draws num_points points and the minimum enclosing circle to the file circle.png
num_points defaults to 15 if not specified.
benchmark: benchmarks the algorithm
The image on this page was produced as follows:
$ ruby mec.rb draw 15
The image ends up in the file 'circle.png' in the current working directory.