algorithm - 理解寻找最小圆包围点的算法

Question

目前我尝试学习和理解几何算法，我发现最小圆问题非常有趣。我找到了许多解决方案和不同的算法，包括 this one我不确定是不是 Emo Welzl 的。

但是，我不明白一个特定的(重要的)部分:

1. 你在 (XY) 平面上得到 N 个点。
2. 你随机排序这些点数
3. 选择 3 个点并在它们位于圆边界上的位置创建圆。

4. 获取下一个点并检查它是否被圆包围:

   a) 如果是封闭的，重复4直到没有剩下的点。

   b) 如果 未包含在内，则创建一个新圆，其中新点位于圆边界上，所有其他点仍位于圆内或圆上。

步骤 1) 到 4a) 很简单，我的问题是步骤 4b)。我怎样才能找到这个新圈子？对我来说，这似乎是同一个问题，只是有一个较小的(子)点集。 (分而治之)

我想我必须用新点替换 3 个原始点中的一个(前 3 个点，构成第一个圆圈)，但我不确定 如果这真的有效……

Answer 1

从 A、B、C 三个点，您可以计算出圆心 O:与这三个点等距的点。其坐标xO和yO分别是xA、xB、xC和yA、yB、yC的平均值。

我们称 D 为第 4 个点，追踪圆心 0 和半径 OD 的圆。

OD > OA(且 OA=OB=OC)所以 A、B 和 C 在圆圈中。

编辑

我上面提出的解决方案并不是最优的。

我找到了 Welzl 算法的一个很好的解释:see link

当然，你可以很容易地通过谷歌学术搜索找到他的论文，但它很难阅读。

基本原则是，在 4b) 中，圆是根据边界上具有 D 的所有可能圆以及之前在边界上的其他两个点(或者一个点，如果不起作用，它将与 D 截然相反)。