将平面上的点分组为 3 个骰子
Group points on a plane into 3 dice
我有一卷 3（6 面）骰子的（自上而下）图像，我从中提取了点的坐标，剩下 3..18 个点。
如何找到骰子上掷的是什么，或者换句话说，哪些点组合在一起形成骰子？
至此，我把它简化为找3个圆的问题，使每个点正好在一个圆内，最大圆的尺寸最小化。
我想到了 2 种可能的方法，但都不太慢。
方法一：
找到所有可能的不相交点集的三元组和每个点集的最小边界圆。放弃圆中包含点以外的点的任何解决方案，或者如果圆大于已找到的最佳解决方案中的最大圆。
方法二：
找到所有可能的三元组圆（由 1-3 个点定义）。丢弃包含超过 6 个点的圆、其他圆中已有的点、大于已找到的最佳解中最大圆的圆或未包围每个点的解的任何解。
有没有更有效的算法来解决这个问题，因为我只能想到大多数暴力解决方案？我需要大约 1 秒的最坏情况时间，理想情况下平均时间最多为 10 毫秒。
最坏情况下18点，最多有
>>> sum(math.comb(18, i) for i in range(1, 7))
31179
1 到 6 点之间的可能子集。舍弃所有最小外接圆（使用Emo Welzl's randomized algorithm) encloses a pip not in the subset. Using the Sauer–Shelah lemma 且圆盘的VC维度为3，我们观察到剩余的子集数量最多为
>>> sum(math.comb(18, i) for i in range(4))
988
（编辑：实际上我们可以尝试由点的三元组生成的圆盘、由点对生成的圆盘和单个点。）现在我们寻找三个成对不相交的子集，它们的并集就是一切。这是通过按位图索引子集、遍历子集对并测试 1) 这些子集是否不相交 2) 它们的并集的补集是否也是一个子集来有效地实现的。
我很确定如果您使用的是像样的编译器，这可以在 10 毫秒的最坏情况下达到 运行。
我有一卷 3（6 面）骰子的（自上而下）图像，我从中提取了点的坐标，剩下 3..18 个点。
如何找到骰子上掷的是什么，或者换句话说，哪些点组合在一起形成骰子？
至此，我把它简化为找3个圆的问题，使每个点正好在一个圆内，最大圆的尺寸最小化。
我想到了 2 种可能的方法，但都不太慢。
方法一：
找到所有可能的不相交点集的三元组和每个点集的最小边界圆。放弃圆中包含点以外的点的任何解决方案，或者如果圆大于已找到的最佳解决方案中的最大圆。
方法二： 找到所有可能的三元组圆（由 1-3 个点定义）。丢弃包含超过 6 个点的圆、其他圆中已有的点、大于已找到的最佳解中最大圆的圆或未包围每个点的解的任何解。
有没有更有效的算法来解决这个问题，因为我只能想到大多数暴力解决方案？我需要大约 1 秒的最坏情况时间，理想情况下平均时间最多为 10 毫秒。
最坏情况下18点，最多有
>>> sum(math.comb(18, i) for i in range(1, 7))
31179
1 到 6 点之间的可能子集。舍弃所有最小外接圆（使用Emo Welzl's randomized algorithm) encloses a pip not in the subset. Using the Sauer–Shelah lemma 且圆盘的VC维度为3，我们观察到剩余的子集数量最多为
>>> sum(math.comb(18, i) for i in range(4))
988
（编辑：实际上我们可以尝试由点的三元组生成的圆盘、由点对生成的圆盘和单个点。）现在我们寻找三个成对不相交的子集，它们的并集就是一切。这是通过按位图索引子集、遍历子集对并测试 1) 这些子集是否不相交 2) 它们的并集的补集是否也是一个子集来有效地实现的。
我很确定如果您使用的是像样的编译器，这可以在 10 毫秒的最坏情况下达到 运行。