Oh, well, it was a good try I guess, but I ran afoul of the case
exposed by Alex Shugin. The points farthest from the new point don't
necessarily (all) have to be on the circumference of the circle.
···
On 2/20/08, Rick DeNatale <rick.denatale@gmail.com> wrote:
Here's my solution.
I also eschewed doing any google research and started from scratch. I
think I've taken a slightly different approach than any already
described.The basic approach is to start with a circle containing only the first
point, and then add the points one by one changing the circle as
necessary. SoFirst point
Set center to the point and radius to zero.Subsequent points.
If the point is already in the circle then the point is simply
added to the collection of points and the circle is unchanged. The
point is in the circle if the distance from the center of the circle
is less than the radius (within some epsilon to deal with floating
point comparisons).If the point is further from the center than the radius, the we know
that it must lie on the circumference of the new circle which will
contain all of the points examined thus far. We now find the set of
points which are furthest from the new point (again within some
epsilon). There will of course be one or more of these points.Now the center of the new circle is the average of those furthest
points plus the new points, and the radius is the distance between the
center and the new point.
--
Rick DeNatale
My blog on Ruby
http://talklikeaduck.denhaven2.com/