Mail Archives: djgpp/1997/03/01/19:57:57
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
- Raw text -