找到包含其他圆圈的最小圆圈? [英] Finding the smallest circle that encompasses other circles?

问题描述

If a circle is defined by the X, Y of it's center and a Radius, then how can I find a Circle that encompasses a given number of circles? A single circle that is the smallest possible circle to completely contain 2 or more circles of any size and location.

At first I tried just encompassing 2 circles by finding the midpoint of the centers and that being the midpoint of the new circle while the radius was equal to the half of the radius of the 2 initial circles and half the distance between their centers, but somehow it always turned out to be a little off. The problem always seemed to be a problem with finding the radius, but I have such a headache about this I can't make it work.

I don't necessarily need a method for finding a circle that encompasses 3 or more circles. I can find a circle that encompasses 2, take that circle and encompass it with another, and another, and the final circle should encompass all circles given throughout the steps.

解决方案

Given two circles, with centers [x1,y1], [x2,y2], and radii R1 and R2. What is the center of the enclosing circle?

Assume that R1 is no larger than R2. If the second circle is the smaller, then just swap them.

1. Compute the distance between centers of the circles.

   D = sqrt((x1-x2)^2 + (y1-y2)^2)

2. Does the first circle lie entirely inside the second circle? Thus if (D + R1) <= R2, then we are done. Return the larger circle as the enclosing circle, with a center of [x2,y2], with radius R2.

3. If (D+R1) > R2, then the enclosing circle has a radius of (D+R1+R2)/2

In this latter case, the center of the enclosing circle must lie along the line connecting the two centers. So we can write the new center as

center = (1-theta)*[x1,y1] + theta*[x2,y2]

where theta is given by

theta = 1/2 + (R2 - R1)/(2*D)

Note that theta will always be a positive number, since we have assured that (D+R1) > R2. Likewise, we should be able to ensure that theta is never larger than 1. These two conditions ensure that the enclosing center lies strictly between the two original circle centers.

这篇关于找到包含其他圆圈的最小圆圈?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！