Mail Archives: djgpp/1997/02/26/12:41:59
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
- Raw text -