Path: utzoo!mnetor!uunet!husc6!cmcl2!nrl-cmf!ames!ucsd!sdcsvax!ucsdhub!hp-sdd!artecon!sceard!mrm
From: mrm@sceard.UUCP (M.R.Murphy)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <821@sceard.UUCP>
Date: 4 Apr 88 18:16:02 GMT
References: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu> <496@etn-rad.UUCP> <3229@phri.UUCP>
Reply-To: mrm@sceard.UUCP (0040-M.R.Murphy)
Organization: Sceard Systems, Inc., Carlsbad, CA  92009
Lines: 30

In article <3229@phri.UUCP> roy@phri.UUCP (Roy Smith) writes:
<jru@etn-rad.UUCP (John Unekis) writes:
<> Try finding the maximum and minimum x coordinates, then average to get the
<> center x. Do the same for y [...] look at the distances to those four
<> points [...] from the center x,y and take the largest distance as the radius.
<
<	It doesn't take much thought to show that this doesn't work.  Take,
<for example, the 5 points (0,-2), (2,0), (0,2), (-2,0), and (1.9,1.9).  The
<min and max x and y are -2 and 2, giving a center of (0,0) and a radius of
<2.  The fifth point, (1.9,1.9) does not fall within that circle.
<-- 
<Roy Smith, {allegra,cmcl2,philabs}!phri!roy
<System Administrator, Public Health Research Institute
<455 First Avenue, New York, NY 10016

The "center" probably isn't the right terminology. I think it's "centroid"
and assuming equal weighting for all points, the centroid is at
((0+2+0+(-2)+1.9)/5,((-2)+0+2+0+1.9)/5). Then after one pass through the data
to determine the centroid, you pass through again to find the largest
distance from the centroid to any of the points.
Using the centroid as the center of a circle, and the largest distance from
the centroid to any of the points as the radius...
Now the question for the mathematicians out there. Is that the smallest
enclosing circle?
-- Mike
-- 
Mike Murphy  Sceard Systems, Inc.  6353C El Camino Real  Carlsbad, CA  92009
ARPA: sceard!mrm@nosc.MIL   BITNET: MURPHY@UCLACH
UUCP: ucsd!sceard!mrm     INTERNET: mrm%sceard.UUCP@ucsd.ucsd.edu