在平面上将点分成三个骰子组

Question

我有一个（自顶向下）的三个六面骰子的图像，提取了点的坐标，留下了3到18个点。

如何找到掷出的点数，换言之，哪些点组合在一起形成一个骰子？

到目前为止，我把它简化成一个问题：查找3个圆，使得每个点恰好位于一个圆中，并且最大圆的大小最小。

我想到了两种可能的方法，但都几乎太慢了。

方法1： 找到所有不相交点集的三元组和每个点集上的最小外接圆。舍弃任何解决方案，其中圆包含除其集合内的点以外的其他点，或者如果比已经找到的最佳解决方案中最大的圆更大。

方法2： 找到所有可能的三个圆（由点1-3定义）。舍弃包含超过6个点、已经在其他圆中的点、比已经找到的最佳解决方案中最大的圆更大的圆，或者不能包围每个点的解决方案。

是否有更有效的算法来解决这个问题？因为我只能想到大多数暴力解决方案。我需要最坏情况下约1秒的时间，理想情况下平均时间长达10毫秒。

- Torn

---

值得展示一张图片 - MBo

这张图片并没有什么特别之处，只是为了解释问题的来源。你可以在网上找到骰子长什么样子的例子。我不能保证有任何特定的背景或骰子颜色，只有点坐标。 - Torn

例如，您可以将骰子点设置为某个半径的圆（不是非常小），并且可以使用Hough变换进行检测。 - MBo

我的问题关于对点进行分组，而不是检测它们。我已经处理了在图像上找到所有的点。 - Torn

Answer 1

在最坏情况下，有18个点时，最多有

>>> sum(math.comb(18, i) for i in range(1, 7))
31179

可能的子集包含1到6个点。丢弃所有最小外接圆（使用Emo Welzl的随机算法）包含不在子集中的点的子集。利用Sauer-Shelah引理和圆盘的VC维数为3的事实，我们观察到剩余子集的数量最多为

>>> sum(math.comb(18, i) for i in range(4))
988

（编辑：实际上，我们可以尝试由三个点生成的磁盘、由两个点生成的磁盘和单个点。）现在我们寻找三个成对不相交的子集，它们的并集是所有内容。通过位图索引子集，循环遍历子集对并测试 1）这些子集是否不相交 2）它们的并集的补集是否也是一个子集，可以有效地完成此操作。如果使用良好的编译器，我非常确定这可以在最坏情况下运行10毫秒。

- David Eisenstat