From:	gfoot AT mc31 DOT merton DOT ox DOT ac DOT uk (George Foot)
Newsgroups:	comp.os.msdos.djgpp
Subject:	Re: bounding circle vs. bounding boxes
Date:	26 Feb 1997 22:04:51 GMT
Organization:	Oxford University
Message-ID:	<5f2c23$cdp@news.ox.ac.uk>
References:	<19970226 DOT 065019 DOT 4511 DOT 1 DOT fwec AT juno DOT com> <33146FD7 DOT A93 AT pobox DOT oleane DOT com>
NNTP-Posting-Host:	mc31.merton.ox.ac.uk
Lines:	30
To:	djgpp AT delorie DOT com
DJ-Gateway:	from newsgroup comp.os.msdos.djgpp

Francois Charton (deef AT pobox DOT oleane DOT com) wrote:
: Mark T Logan wrote:
: > How can I calculate a bounding circle?  Anyone know?

: The best (ie smallest) bounding circle can be calculated as follow : 
: find the two points A and B in your set which are farthest from each 
: other, the best circle has the middle of segment AB as its center, and 
: half the distance between A and B as its radius. 

I don't think that's quite correct... e.g. if you have three points 
at (-1,0), (1,0) and (0,3/2) the farthest two points are the first and
second. By your algorithm, the centre would be the origin, with radius
1, and the third point would not be included.

: You could use simpler (and non optimal) algorithms, which require less 
: evaluations : use the center of gravity of the points (its (x,y) 
: coordinates are the averages of the coordinates of the points), as the 
: center of the circle, then calculate its distance to all points in the 
: circle, and take the largest as the radius. This takes only N point to 
: point distance evaluations. The resulting bounding sphere will be good if 
: your point cluster is shaped like a disk, and very bad if one point is 
: far from all the others.

I prefer this algorithm, even though it doesn't necessarily produce the
smallest possible circle. If the points aren't approximately disc-shaped,
a bounding circle is a bad idea anyway.

-- 
George Foot <gfoot AT mc31 DOT merton DOT ox DOT ac DOT uk>
Merton College, Oxford.

- Raw text -