Hi,

Since Matthew has a cold, I decided to take another look at my
"solution". Accuracy hasn't changed because the idea is exactly the
same as before, but speed is at least measurable now. Well, overall
performance is still abominable but since I started it (i.e. posted
the previous version) I thought I could also post this slightly more
complex version. I also included some hopefully correct code for ruby
1.8 compatibility. The use of complex could be easily avoided of
course.

Maybe of more interest to you: I also include a revised version of my
accuracy checker that makes use of Lionel's more sophisticated sample
generator. My "solution" performs especially bad on "random on disk"
and "2d gaussian" it seems. Oh well.

Regards,
Thomas.


========================================================================


require 'complex'


class Point < Struct.new(:x, :y)
    def self.random
        Point.new(rand, rand)
    end

    def to_s
        "(#{x}, #{y})"
    end

    def self.from_complex(c)
        self.new(c.real, c.image)
    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
    return if points.nil? or points.empty?
    return Circle.new(points[0], 0) if points.size == 1

    points = prepare(points)
    a, ar  = points_max_dist_center(points)
    return Circle.new(Point.from_complex(a), ar) unless points.size >
2

    points = points.sort_by {|p| -(a - p).abs}
    f      = points[0]
    points.delete(f)
    zz = nil
    zr = 0
    points.each do |p|
        aang = (a - f).angle
        pang = (p - f).angle
        phi  = pang - aang
        rd   = (f - p).abs / 2.0
        rr   = rd / Math.cos(phi)
        if rr > zr
            ra = f.real  + rr * Math.cos(aang)
            rb = f.image + rr * Math.sin(aang)
            zz = Complex(ra, rb)
            zr = rr
        end
    end
    return Circle.new(Point.from_complex(zz), zr)
end


def points_max_dist_center(points)
    m, n = points.combination(2).sort_by {|a, b| -(a - b).abs}[0]
    a = (m + n) / 2.0
    d = (a - m).abs
    return [a, d]
end


def prepare(points)
    points = points.uniq
    points.map! {|p| Complex(*p.to_a)}
    i = 3
    while i < points.size
        p1, p2, p3 = points[i-3, i]
        points.delete_if {|p| in_triangle?(p1, p2, p3, p)}
        i += 1
    end
    return points
end


def in_triangle?(a, b, c, p)
    return false if a.nil? or b.nil? or c.nil? or p.nil? or a == p or
b == p or c == p
    u = (a - b).angle
    l = (a - c).angle
    x = (a - p).angle
    return false unless x.between?(l, u)
    u = (c - a).angle
    l = (c - b).angle
    x = (c - p).angle
    return x.between?(l, u)
end


if RUBY_VERSION < '1.9.0'
    class ::Array

        def combination(n)
            out = []
            size.times do |i|
                head  = self[i]
                if n > 1
                    rest = self[i + 1, size]
                    if rest.size >= n - 1
                        tails = rest.combination(n - 1)
                        out += tails.map {|t| t.unshift(head)}
                    end
                else
                    out << [head]
                end
            end
            out
        end

    end
end


if __FILE__ == $0
    points = []
    ARGV.each {|p| points << Point.new(*p.split(/,/).map{|c| c.to_f})}
    c = encircle(points)
    p c
end



========================================================================


#!/usr/bin/env ruby19

require 'mathn'

E = 1e-10


num_runs = 10
num_samples = 100
# num_runs = 10
# num_samples = 1000

module PHILIPP ; eval(File.read('s_philip.rb'))  ;  end
module PHILIPP2; eval(File.read('s_philip2.rb'))  ;  end
module LIONEL ;  eval(File.read('s_lionel.rb'))    ;  end
module LIONEL4;  eval(File.read('s_lionel4.rb'))    ;  end
module DOUG ;    eval(File.read('s_douglas.rb'))     ;  end
module FRANK ;   eval(File.read('s_frank.rb'))    ;  end
module JUSTIN ;  eval(File.read('s_justin.rb'))    ;  end
module BILL ;    eval(File.read('s_billk.rb'))       ;  end
module BILL2 ;   eval(File.read('s_billk2.rb'))       ;  end
module THOMAS ;  eval(File.read('quiz157l.rb'))        ;  end
module THOMAS2 ;  eval(File.read('quiz157s.rb'))        ;  end

namespaces = [
  THOMAS,
  THOMAS2,
  FRANK,
  JUSTIN,
  LIONEL,
  LIONEL4,
  DOUG,
  PHILIPP,
  PHILIPP2,
  BILL,
  BILL2,
]



class Point < Struct.new(:x, :y)
    def self.random(type=0)
        case type
        when 1
            ro = rand / 2
            theta = Math::PI * 2 * rand
            Point.new(ro * Math::cos(theta) + 0.5, ro *
Math::sin(theta) + 0.5)
        else
            Point.new(rand, rand)
        end
    end

    def to_s
        "(#{x}, #{y})"
    end
end

def generate_samples(mod, coords)
  coords.map {|xy| mod::Point.new(*xy)}
end


def distance(p1, p2)
    Math.sqrt((p1.x - p2.x) ** 2 + (p1.y - p2.y) ** 2)
end


distributions = {
  "Random on square" =>
    (1..num_runs).map {(1..num_samples).map {[rand, rand]}},
  "Random on disk" =>
    (1..num_runs).map {(1..num_samples).map {
        ro = rand(0.5)
        theta = Math::PI * 2 * rand
        [ ro * Math::cos(theta), ro * Math::sin(theta)]
      }
    },
  "Random on circle" =>
    (1..num_runs).map {(1..num_samples).map {
        theta = Math::PI * 2 * rand
        [ Math::cos(theta), Math::sin(theta)]
      }
    },
  "2D Gaussian" =>
    (1..num_runs).map {(1..num_samples).map {
	ro = Math::sqrt(-2 * Math::log(rand))
        theta = Math::PI * 2 * rand
        [ ro * Math::cos(theta), ro * Math::sin(theta)]
      }
    },
}


def prepare_pointsets(namespaces, raw_coords, num_runs)
  pointsets = {}
  namespaces.each do |mod|
    pointsets[mod.name] = (0...num_runs).map do |i|
      generate_samples(mod, raw_coords[i])
    end
  end
  pointsets
end

puts
distributions.each { |name,raw_coords|
    results = Hash.new {|h, k| h[k] = {}}
    winners = Hash.new {|h,k| h[k] = 0}

    puts "-- #{name} --"
    pointsets = prepare_pointsets(namespaces, raw_coords, num_runs)
    solutions = {}
    namespaces.each {|mod| solutions[mod.name] = Class.new { include
mod }.new}
    namespaces.each do |mod|
        name = mod.name
        solution = solutions[name]
        num_runs.times do |i|
            points = pointsets[name][i]
            val = solution.encircle(points)
            results[i][mod] = val
        end
    end

    f_dist = Hash.new {|h,k| h[k] = []}

    results.each do |i, s|
        cwinner = namespaces.sort_by {|f| s[f] ? s[f].radius :
100000000}
        best_radius = s[cwinner[0]].radius
        winners[cwinner[0]] += 1
        cwinner.each_cons(2) do |a,b|
            if (s[a].radius - s[b].radius).abs <= E
                winners[b] += 1
            else
                break
            end
        end

        namespaces.each do |fav|
            f_d = ((s[fav].radius - best_radius) / best_radius).abs *
100
            f_dist[fav] << f_d
        end
    end


    puts "Winners (best circle):"
    winners.each do |f, n|
        puts '%10s %d' % [f, n]
    end
    puts

    puts "Fav: %s" % namespaces.join(', ')
    puts 'Min: %s' % f_dist.map {|fav, d| '%6.2f' % d.min}.join(', ')
    puts 'Max: %s' % f_dist.map {|fav, d| '%6.2f' % d.max}.join(', ')
    puts 'Avg: %s' % f_dist.map {|fav, d| '%6.2f' % (d.inject(0.0){|
a,d| a + d} / d.size)}.join(', ')
    puts

}