delorie.com/archives/browse.cgi search
Mail Archives: djgpp/1997/03/01/19:57:57

 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>

```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 -

 webmaster delorie software   privacy Copyright © 2019   by DJ Delorie Updated Jul 2019