Message-ID: <3318C3DA.5E70@pobox.oleane.com> Date: Sun, 02 Mar 1997 01:03:38 +0100 From: Francois Charton 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