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:
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)
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.
$ 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.