Message-ID: <33146FD7.A93@pobox.oleane.com>
Date: Wed, 26 Feb 1997 18:16:07 +0100
From: Francois Charton <deef AT pobox DOT oleane DOT com>
Organization: CCMSA
MIME-Version: 1.0
To: Mark T Logan <fwec AT juno DOT com>
CC: 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>
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit

Mark T Logan wrote:
> 
> I need to calculate the bounding box of a set of points.
> That is, the smallest rectangle which will encompass
> all the points.  I decided that I could simply find the greatest
> x value among all the points, the greatest y value, and then
> the least x and y values to find the edges of my box.  To
> easy, I decided.
> 
> 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. 

However, this algorithm is very slow if you have many points : you have 
to evaluate n(n-1)/2 point to point distances... (I don't know if there 
is a way to make it faster, anyone?) So this method can be applied only 
if you calculate the bounding circle once, and use it many times after 
that.

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.

However, if speed is the concern, I think rectangle bounds are much 
better...

> Also, If I use bounding circles, I need to be able to check
> if the bounding circle is intersected or contained by two rays
> which extend from a single point at a slight angle from one another
> (I'd do some ASCII art here, but my mailer uses a proportional font).
> How can I do this? (quickly!)
> 

Let A be the point, u be the angle between the two rays, O the center of 
the circle, R its radius, 

calculate the square distance between A and O, and call it d^2

if d^2 * (tan(u/2))^2 >= R^2 the ray is contained

Hope this helps
Francois