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 Merton College, Oxford.