如果一个圆由它的中心点的X,Y坐标和半径定义，那么如何找到一个包含给定数量圆的圆？一个最小的圆，足以完全容纳任何大小和位置的2个或多个圆。
起初，我试图通过找到中心点的中点，并使其成为新圆的中点，而半径等于两个初始圆的半径的一半和它们中心之间距离的一半来包含2个圆，但是总是稍有偏差。问题似乎总是出现在找半径的问题上，但是我对此头痛不已，无法使其正常工作。
我不一定需要找到一个包含3个或更多圆的圆的方法。 我可以找到一个包含2个圆的圆，然后用另一个圆将其环绕，再用另一个圆环绕它，最后的圆应该包含所有在步骤中给出的圆。
给定两个圆，中心为 [x1,y1]，[x2,y2]，半径分别为 R1 和 R2。什么是包围圆的中心？
假设 R1 不大于 R2。如果第二个圆更小，则只需交换它们。
计算圆心之间的距离。
D = sqrt((x1-x2)^2 + (y1-y2)^2)
第一个圆是否完全位于第二个圆内？如果 (D + R1) ≤ R2，则完成了。将较大的圆作为包围圆返回，半径为 R2，中心为 [x2,y2]。
如果 (D+R1) > R2，则包围圆的半径为 (D+R1+R2)/2
在后一种情况下，包围圆的中心必须位于连接两个中心的直线上。因此我们可以将新的中心写为
center = (1-theta)*[x1,y1] + theta*[x2,y2]
其中theta由以下给出
theta = 1/2 + (R2 - R1)/(2*D)
可能有一些技巧可以加速这个过程，但它应该能给你一个准确的解决方案。 使最小外接圆算法达到线性时间的一些“技巧”可能适用于这里，但我怀疑它们不是微不足道的改编。
我现在不建议这样做
请参阅下面的讨论。
我会考虑使用迭代推拉方法。
distance_to_center_of_circle[i]+radius_of_circle[i]，并且随着向量和的变化而形成。还要注意，当前位置所需的半径是这些长度的最大值。当它停止[+]收敛时，就完成了。
按请求澄清第二步。称要测试的位置为\vec{P}（矢量量）。[++] 将每个圆的中心称为\vec{p}_i（也是矢量量），每个圆的半径为r_i。形成总和\sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i)。[+++] 总和的每个元素指向从当前评估点到问号中心的方向，但长度比r_i长。总和本身是一个矢量量。
需要包含来自P的所有圆的半径R是max(|p_i-P|_r_i)。
我不认为Nikie提出的特定案例是问题，但它让我想到了一种算法失败的情况。失败不是发散的问题，而是不能改进解决方案的问题，但仍然......
考虑四个半径均为1的圆，位于
(-4, 1)
(-5, 0)
(-4, 1)
( 5, 0)
起始位置为(-1, 0)，对称设计使得所有距离都沿x轴。
正确的解法是半径为6的(0, 0)，但步骤2计算出的向量大约为::疯狂计算:: (-.63, 0)，指向错误方向导致无法找到朝向原点的改进。
现在，上述算法实际上会选择(-2, 0)作为起始点，这会给出一个初始向量和为::疯狂计算:: 约+1.1。因此，在(3)上选择不良的步长大小会导致不太理想的解决方案。::叹气::
可能的解决方案：
然而，此时它与纯随机漫步相比并没有更好，并且您没有易于知道何时收敛的条件。嗯。
[+] 或者按您的要求减速。
[++] 使用latex符号。
[+++] 这里\hat{}表示指向与参数相同方向的归一化向量。
我听取了一些人的意见，这是我发现的解决方案：
public static Circle MinimalEnclosingCircle(Circle A, Circle B) {
double angle = Math.Atan2(B.Y - A.Y, B.X - A.X);
Point a = new Point((int)(B.X + Math.Cos(angle) * B.Radius), (int)(B.Y + Math.Sin(angle) * B.Radius));
angle += Math.PI;
Point b = new Point((int)(A.X + Math.Cos(angle) * A.Radius), (int)(A.Y + Math.Sin(angle) * A.Radius));
int rad = (int)Math.Sqrt(Math.Pow(a.X - b.X, 2) + Math.Pow(a.Y - b.Y, 2)) / 2;
if (rad < A.Radius) {
return A;
} else if (rad < B.Radius) {
return B;
} else {
return new Circle((int)((a.X + b.X) / 2), (int)((a.Y + b.Y) / 2), rad);
}
}
如果您不需要精确的圆形，则此近似可能可行。
所有圆都必须落在以X为中心，半径为R1 + R2的圆内
这不是一个琐碎问题。我没有读过上面所有的答案，所以如果我重复了别人已经说过的话，那是我的错。
每个圆 c_i 由 3 个参数 x_i、y_i 和 r_i 定义。
需要找到 3 个参数 x*、y* 和 r* 来定义最优圆 C*。
C* 要包含所有的 c_i。
设 d_i = ||(x,y)-(x_i,y_i)|| + r_i。
然后，如果一个圆的半径 r 能够包含所有的 c_i，那么 r >= d_i 对于所有的 i 成立。
我们希望 r 尽可能小。
所以，r* = max(d_i)。
因此，我们要使 d_i 的最大值最小化。
所以，(x*,y*) 由 max(d_i) 的 arg min 给出。一旦找到了 (x*,y*)，r* 可以很容易地计算，并且等于 max(d_i)。这是一个极小极大化（minimax）问题。
为了更容易理解，考虑只有 2 个圆，如何找到 (x*,y*)？
(x*,y*) 可以通过找到最小化 (d_1 - d_2)^2 的 (x,y) 来找到。在一般情况下。
令 e_ij = (d_i - d_j)^2
然后定义 e = \sum e_ij，其中 i != j（在这个总和中有 n 个选择 2 项）
(x*,y*) = e 的 arg min
这就是需要解决的问题。
提示：如果对于所有 i，r_i = 0，则当输入为一堆点并且我们想要找到覆盖它们所有的最小圆时，这将简化为传统的最小包围圆问题。