找到包含其他圆圈的最小圆圈？
如果圆圈由其中心的X，Y和半径定义，那么如何找到包含给定圈数的圆？ 单个圆圈，是可能的最小圆圈，可完全包含任意大小和位置的2个或更多圆圈。
起初，我尝试通过找到中心的中点并且是新圆的中点来尝试仅包含2个圆，而半径等于2个初始圆的半径的一半和中心之间的距离的一半，但不知何故它总是变得有点偏。 找到半径似乎问题似乎总是存在问题，但我对此感到头疼，我无法使其发挥作用。
我不一定需要一种方法来查找包含3个或更多圆的圆。 我可以找到一个包含2的圆圈，取圆圈并用另一个圆圈包围它，另一个圆圈，最后一个圆圈应包含整个步骤中给出的所有圆圈。
它被称为最小封闭圆（“MEC”），或有时“最小的封闭圆”。
一个不错的网站： http ： //www.personal.kent.edu/~rmuhamma/Compgeometry/MyCG/CG-Applets/Center/centercli.htm
给定两个圆，中心为[x1，y1]，[x2，y2]，半径为R1和R2。 封闭圆的中心是什么？
假设R1不大于R2。 如果第二个圆圈较小，则只需交换它们即可。
-
计算圆心之间的距离。
D = sqrt（（x1-x2）^ 2 +（y1-y2）^ 2）
-
第一个圆圈是否完全位于第二个圆圈内？ 因此，如果（D + R1）<= R2，那么我们就完成了。 将较大的圆圈作为封闭圆返回，其中心为[x1，x2]，半径为R2。
-
如果（D + R1）> R2，则包围圆的半径为（D + R1 + R2）/ 2
在后一种情况下，封闭圆的中心必须位于连接两个中心的线上。 所以我们可以把新中心写成
center = (1-theta)*[x1,y1] + theta*[x2,y2] theta由哪个给出
theta = 1/2 + (R2 - R1)/(2*D)
请注意，theta将始终为正数，因为我们已确保（D + R1）> R2。 同样，我们应该能够确保theta永远不会大于1.这两个条件确保封闭中心严格位于两个原始圆心之间。
我现在打算反对这个
请参阅下面的讨论。
原创的想法
我会考虑一种迭代的推拉方法。
- 猜猜中心的位置（最简单的是所有中心的平均位置）
- 将向量计算到每个圆上的最远点。 它们总是朝向该圆心的方向，并且长度为
distance_to_center_of_circle[i]+radius_of_circle[i]并且distance_to_center_of_circle[i]+radius_of_circle[i]形成矢量和。 另请注意，当前位置的必要半径是这些长度的最大值。 - 从2开始（例如）1/5或1/10的向量和，并从2为新点重做计算
- 如果新点需要比旧点小的圆，则将新点作为当前点，否则，拆分差值，减小建议步长的大小（比如说它的一半）。
- 转到3
当它停止[+]收敛时你就完成了。
尼基戳了戳直到……
按要求澄清第二步。 调用要测试的位置\vec{P} （矢量）。[++]调用每个圆的中心\vec{p}_i （也是矢量），每个圆的半径是r_i 。 形成和\sum_i=1^n \hat{p_i - P}*|(p_i-P)|+r_i) 。[+++]和的每个元素指向从当前评估点到中心的方向有问题的圆圈，但r_i更长。 总和本身就是一个矢量。
半径R需要包围P所有圆是max(|p_i-P|_r_i) 。
病理案例
我不认为nikie带来的特殊情况是一个问题，但它让我遇到了这个算法失败的情况。 失败是未能改善解决方案，而不是分歧，但仍然……
考虑四个半径为1的圆圈
(-4, 1) (-5, 0) (-4, 1) ( 5, 0)
和起始位置(-1, 0) 。 通过设计对称，使所有距离沿x轴。
正确的解决方案是(0, 0) ，半径为6，但是在步骤2中计算的向量约为::计算错误: (-.63, 0) ，指向错误的方向，导致永远不会找到对原点的改进。
现在，上面的算法将实际选择(-2, 0)作为起始点，这给出了一个初始向量和::计算furiously ::约+1.1。 因此，（3）中步长的错误选择将导致不太理想的解决方案。 ：：叹：：
可能的方法：
- 在（3）中抛出一个随机分数（比如+1/5和-1/5）可能加权到正大小。
- 在（4）中如果步骤被拒绝，则只需返回步骤3而不改变步长限制。
然而，在这一点上它并不比纯随机游走好多了，并且你没有一个简单的条件来知道它何时收敛。 咩。
[+]当然，或者减慢到令你满意的速度。 [++]使用乳胶符号。 [+++]这里\hat{}表示规范化的向量指向与参数相同的方向。
由于我的不精确解决方案不受欢迎。 这是一种获得确切解决方案的方法。 但它的缓慢（O（N ^ 4）？）和计算上令人讨厌。 （与不精确的方法不同）
首先你需要知道，给定三个圆圈，我们可以找到一个与它们相切的圆，而不是包含所有三个圆。 这是Apollonius的一个圈子。 你可以从mathworld获得算法。
接下来，您可以显示N个圆圈的最小封闭圆与N个圆圈中的至少3个圆相切。
要找到此圈子，我们会执行以下操作
- 循环遍历所有圆圈 – O（N ^ 3）
- 找到这3个圆圈的封闭Apollonius圆圈 – 计算上令人讨厌
- 如果它包含所有圆圈，则将其添加到潜在列表中 – 检查是否为O（N）
- 解决方案是半径最小的潜力
可能有一些技巧可以加快速度，但它应该为您提供准确的解决方案。 将最小的封闭圆算法设置为线性时间的一些“技巧”可能适用于此，但我怀疑它们不会是微不足道的适应。
你手边的问题被称为球体的最小封闭球体 。 我已经写了关于它的论文，参见苏黎世联邦理工学院的“最小的球形球” 。
您可以在Bounding Volumes包中的Computational Geometry Algorithms Library（CGAL）中找到一个非常有效的C ++实现。 （不需要使用所有CGAL;只需提取所需的源文件和头文件即可启动并运行。）
注意：如果您正在寻找一种算法来计算最小的封闭球体点 ，那么还有其他实现，请参阅这篇文章 。
我已经采取了一些你不得不说的话，这是我发现的解决方案：
public static Circle MinimalEnclosingCircle(Circle A, Circle B) { double angle = Math.Atan2(BY - AY, BX - AX); Point a = new Point((int)(BX + Math.Cos(angle) * B.Radius), (int)(BY + Math.Sin(angle) * B.Radius)); angle += Math.PI; Point b = new Point((int)(AX + Math.Cos(angle) * A.Radius), (int)(AY + Math.Sin(angle) * A.Radius)); int rad = (int)Math.Sqrt(Math.Pow(aX - bX, 2) + Math.Pow(aY - bY, 2)) / 2; if (rad < A.Radius) { return A; } else if (rad < B.Radius) { return B; } else { return new Circle((int)((aX + bX) / 2), (int)((aY + bY) / 2), rad); } }
圆由其中心的X，Y和半径定义，都是整数。 有一个构造函数是Circle（int X，int Y，int Radius）。 在突破了一些旧的概念之后，我认为最好的方法是找到距离最远的圆圈上的2个点。 一旦我有了，中点将是中心，一半的距离将是半径，因此我有足够的定义一个新的圆。 如果我想包含3个或更多个圆圈，我首先在2个圆圈上运行它，然后我在生成的包围圆圈和另一个圆圈上运行它，依此类推，直到包含最后一个圆圈。 可能有一种更有效的方法来做到这一点，但现在它的工作原理，我很高兴。
我回答自己的问题感到很奇怪，但如果没有每个人的想法和联系，我都无法找到解决方案。 谢谢大家。
只需了解圆的方程并导出一个方程（或一系列），找到答案，然后开始实施。 鉴于你已经做了一些事情，也许我们能够帮助你。
因此，如果您不需要精确的圆，则此近似可能会这样做。
- 取你所有圈子中心的平均值称为X点
- 设R1是从X到圆心的最大距离。
- 设R2为圆的最大半径
所有圆圈必须落在以X为中心的圆内，半径为R1 + R2
这不是一个小问题。 我没有阅读上面的所有答案，所以如果我重复一个人已经说过的话，那就是我的错。
每个圆c_i由3个参数x_i，y_i，r_i定义
需要找到3个参数x *，y *，r *表示最佳圆C *
C *是这样的，它包含所有i的c_i
设d_i = ||（x，y） – （x_i，y_i）|| + r_i
然后，如果r是包含所有c_i的圆的半径，则对于所有i，r> = d_i
我们希望r尽可能小
所以，r * = max（d_i）
因此，我们希望最小化d_i的最大值
所以（x *，y *）由max（d_i）的arg min给出。 并且一旦找到（x *，y *），就可以容易地计算r *并且将等于max（d_i）。 这是一个极小极大的问题。
为了让事情更容易理解，只考虑2个圆圈，我们如何找到（x *，y *）？
通过找到最小化（d_1-d_2）^ 2的（x，y）可以找到（x *，y *）。 在一般情况下
设e_ij =（d_i – d_j）^ 2
然后为i！= j定义e = \ sum e_ij（有n在此总和中选择2个术语）
（x *，y *）= arg min of e
这是需要解决的问题。
提示：如果对于所有i，r_i = 0，那么当输入是一堆点时，这会减少到传统的最小封闭圆问题，并且我们希望找到涵盖所有这些的最小圆。