From: ThoML <micathom@...>
Date: 2008-02-18T05:39:57+09:00
Subject: Re: The Smallest Circle (#157)

> And again I reply to my own post.

This is getting a bad habit. Sorry. This slightly modified version
uses the center of the two points with maximum distance as starting
point. For random sets, the results fit quite well most of the time --
on certain sets it's farther off than the mass center version though.

Regards,
Thomas.


def encircle(points)        # takes array of Point objects
    points = points.uniq
    return if points.nil? or points.empty?

    return Circle.new(points[0], 0) if points.size == 1

    m, n = points.combination(2).sort_by {|a, b| -distance(a, b)}[0]
    a    = Point.new(m.x / 2 + n.x / 2, m.y / 2 + n.y / 2)
    return Circle.new(a, distance(a, m)) unless points.size > 2

    points = points.sort_by {|p| -distance(a, p)}
    f  = points[0]
    df = distance(f, a)
    b  = med(f, a)
    e  = 1e-10
    1000.times do
        db = distance(f, b)
        if points.all? {|p| distance(b, p) <= db + e}
            da = distance(f, a)
            if (da - db).abs <= e
                return Circle.new(b, db)
            else
                a, b = b, med(f, b)
            end
        else
            b = med(a, b)
        end
    end
    raise RuntimeError
end


def med(a, b)
    Point.new((b.x - a.x) / 2.0 + a.x, (b.y - a.y) / 2.0 + a.y)
end


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