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
}
