Message-ID: <3318C3DA.5E70@pobox.oleane.com>
Date: Sun, 02 Mar 1997 01:03:38 +0100
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: djgpp AT delorie DOT com
Subject: Re: bounding circle vs. bounding boxes
References: <19970226 DOT 065019 DOT 4511 DOT 1 DOT fwec AT juno DOT com> <5f8aob$93q AT freenet-news DOT carleton DOT ca>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Paul Derbyshire wrote:
> 
> Get the centroid of all your points. Then get the distance to the furthest
> point. This gets you the center and radius.
> 

Instead of the centroid (ie average of the points) you could use the 
center of the best bounding box : find the maximum and minimum x and y 
coordinate of the points, and use the point

((max(x) - min(x))/2, (max(y)-min(y))/2) as the center of the circle. 

This has several advantages on the centroid method: 
1/ it is a little faster to calculate (no averaging involved)
2/ when the points are not well distributed (for instance if one point is 
far away from the others), this will provide a much better solution
3/ it also provides the best bounding box, so you can decide whether you 
want to use a circle or a box.

IMHO, this should be better as an "on the fly" method. But the circle you 
get is not optimal (ie the smallest possible).

I think it is possible to find such a "best circle". Here is an idea on 
how to proceed : 

1/ find the convex hull of the points, let it be composed of points M_0, 
M_1 ... M_p, ordered so that M_i and M_i+1 are next to each other (with 
convention M_p+1=M_0), let O be the centroid of the hull

2/ you can calculate the center of the hull by the following algorithm: 
for each i, between 0 and p, let G_i be the barycenter of the triangle 
(M_i, M_i+1, O), and S_i be its surface, then the center of the hull 
should be the weighted average of the G_i, with weights S_i, that is

G = Sum(G_i*S_i)/Sum(S_i)

3/ I think (didn't prove it though) that G is the center of the "best 
circle", you can then calculate the radius by finding the point M_i 
furthest from it (if it is the optimum, there should be either 2 points 
on the circle, which form a diameter, or 3 points on the circle
 
Francois