Path: utzoo!yunexus!geac!david
From: david@geac.UUCP (David Haynes)
Newsgroups: comp.graphics
Subject: Re: Algorithm wanted: Circle enclosing points
Message-ID: <2535@geac.UUCP>
Date: 5 Apr 88 12:48:42 GMT
Article-I.D.: geac.2535
Posted: Tue Apr  5 08:48:42 1988
References: <wWIfSMy00Xo3A5u1dC@andrew.cmu.edu: <496@etn-rad.UUCP: <3229@phri.UUCP:
Reply-To: david@geac.UUCP (David Haynes)
Organization: Geac Computers International Inc.
Lines: 29

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

I am sorry, but since when does a square of length 2 have a *longest*
radius of 2? How about sqrt(8) => ~2.8 so that (1.9, 1.9) does fall
within it. This is *a* solution but not the optimal solution.
(Since the example above only needs a radius of sqrt(7.22))

I would normalize the points to a zero origin and then discover
the maximum of sqrt((x^2)+(y^2)), then map the system back to 
its origin. (in one equation of course!)

-david-

-- 
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
David Haynes                                              Just another road
Geac Computers International Inc.                         kill on the highway
UUCP: uunet!mnetor!geac!david -or- david@geac.UUCP        of life.