多个点是否能组成一个圆形？

Question

如果我有20个点，如何检查这些点是否组成了一个圆？它不必是一个完美的圆。

例如，如果我每200毫秒存储鼠标的坐标（当用户移动鼠标时），我想看看用户是否做出了一个圆形手势。但我不能期望用户做出一个完美的圆。

- Afra

---

你可以再具体说明一下你想实现什么吗？ - Alexandros

我将继续Don Roby的陈述 - “什么是不完美的圆”。假设您在4个点中采样一个完美的圆。现在假设这些点是：从45度开始，并围绕圆旋转90度。这将为您提供4个点，它们恰好位于完美圆形所在的位置。但是，如果您绘制这4个点，您最终会画出一个矩形。这是一个不完美还是完美的圆？ - brano

@Brano，我将不完美的圆定义为一组在规定公差内共圆的点。例如，如果你通过这些点创建一个最佳拟合圆，并且85%的点位于拟合圆半径的20%距离内，那么你就有了一种“不完美的圆”。请注意，你需要至少四个点作为起点，并且需要针对不同的应用程序和用户调整接受标准。 - SmacL

不知道为什么这个问题被关闭了。可能将“构成一个圆”这个术语改为“共圆”会消除歧义。 - SmacL

Answer 1

我会做以下几件事：

• 计算通过这些点的最佳拟合圆
• 为每个点计算残差（从中心到该点的距离减去最佳拟合圆半径）
• 如果足够多的残差小于用户定义的接受标准，即最佳拟合半径的一小部分，则接受结果。这些参数是可定义的接受标准。

- SmacL

---

这可能是最正确的方法，但在代码实现上似乎需要付出很大的努力。根据点数，它仍然可能足够快以进行实时手势识别。 - Louis Ricci

最好使用L_1拟合，因为它对单个异常值不太敏感。另一个可能性是L_∞（最小环）拟合，其中测试可以基于环宽与平均半径的比率。这里有一份关于圆拟合算法的良好调查，其中包含代码和其他资源的链接。在网络搜索中搜索“L1圆拟合”会出现大量L_1和L_∞算法的资源。 - Ted Hopp

@Ted，非常感谢你提供的链接，非常有用。我过去也遇到过单个异常值的问题。 - SmacL

@Lastcoder，我在开发一款建模软件时使用了类似的东西，它足够快速地实现了C++桌面解决方案中鼠标移动时圆形的实时更新。在低功率平台（例如移动设备）上，性能可能会成为一个问题，特别是在较慢的语言中。请注意，有许多简单的优化方法，例如在比较距离<、==、>时可以省略平方根。 - SmacL

Answer 2

更新：根据@LastCoder的建议，删除太靠近前一个点的连续点（我将阈值设置为10；也许可以增加），并将容差级别设置为0.25（即与中心点的平均距离相差25%是可接受的），我制作的应用程序在超过一半的情况下识别出了我的“圆形”，不再被正方形所欺骗。所以这可能不是一个坏主意。

---

我会找到给定点集的质心，并检查从质心到每个点的距离是否相等（假设您期望得到一个完整圆形的近似值，而不仅仅是一个弧线）。

在实践中，对于使用鼠标完成圆形手势的检测问题，它对我很有效；请参见C＃示例（VS2010，仅主要表单，其余部分是自动样板文件；忽略ideone上的错误），以及此处的屏幕截图：

- Alexey Kukanov

---

只需记住径向偏差必须与半径成比例，否则您会将非运动误检测为圆形。该算法可以作为在线算法高效实现，其中圆度得分会随着新样本的到来而重新计算。 - cyborg

如果点没有均匀地分布在整个圆周上，那么这个公式就会失效，从而使得质心偏离圆心。 - Rafał Dowgird

@RafałDowgird和其他人：我同意，但对于鼠标手势检测问题，人们可以期望点被相当均匀地分配；并且这已经通过实验得到了证实（请参见更新的答案） :) - Alexey Kukanov

从性能上来看，这似乎是最有效的估计方法。为了使质心更准确，您可以剔除连续的点，如果它们之间的距离太接近（对于手势感应，这可以相当容易地校准，并消除由于在圆的某一部分缓慢移动而不是另一部分而引起的额外权重）。 - Louis Ricci

@LastCoder：谢谢你的建议，尝试一下是个好主意。这个问题很有趣，对吧？ :) - Alexey Kukanov

实现、测试、回来展示结果并证明一切都正常运行，这些都值得加1分。干得好！ - SmacL

Answer 3

这是一个简单的方法，我提供了一个可行的实现。 http://jsfiddle.net/kBsdW/29/

• 循环遍历点
• 找到与第一个点距离最大的第二个点
• 记录距离
• 一旦你有了所有的最大距离，平均它们并计算误差容限
• 检查所有记录的距离是否符合误差容限

这对于像鼠标或触摸传感器这样的用户输入非常有效。此算法的时间复杂度为O(n^2)，使用最大距离而不是查找质心和检查半径距离。

它“似乎”比最佳拟合圆方法更有效，后者必须在每个3个点的组合上进行计算。

这个hack~algo利用了一个事实，即圆上两点之间的最大距离就是圆的直径。

function isCircle(points, error) {
    if(points.length <= 2) return true;
    var weights = [];
    var maxDistance = 0;
    var sumDistance = 0;
    var avgDistance = 0;
    var errorConstraint = 0;
    for(var i=0; i<points.length; i++) {
        var distance = 0;
        for(var j=0; j<points.length; j++) {
            var d = getDistance(points[i], points[j]);
            if(d > distance) {
                distance = d;
            }
        }
        if(distance > 0) {
            if(distance > maxDistance) maxDistance = distance;
            sumDistance += distance;
            weights.push(distance);
        }
    }
    avgDistance = sumDistance / weights.length;
    errorConstraint = error * avgDistance;
    for(var i=0; i<weights.length; i++) {
        if(Math.abs(avgDistance - weights[i]) > errorConstraint) {
            return false;
        }
    }
    return true;
}

- Louis Ricci

---

+1。但是Math.abs(avgDistance - weights[i]) > errorConstraint太过简单了。想象一下从圆的中心开始的人。你需要大多数点来验证这一点。所以需要2个参数。 - UmNyobe

@UmNyobe - 这就是为什么在这些情况下它返回false，只有当“所有”长度都在公差范围内时才返回true。您还可以对权重数组进行一些额外的处理并删除异常值，但我在简单的jsfiddle示例中没有这样做。 - Louis Ricci

我尝试了一下你的实现。即使容差级别设置为0.15，它仍然可以将正方形甚至三角形（如果接近等边）视为圆形 :) - Alexey Kukanov

@Alexey。假阴性将始终存在。这是模式识别。除非他也想开始识别正方形，否则这已经很稳定了。 - UmNyobe

@Alexy，正方形或任何三角形的四个角落点都是共圆的。在同一几何图形上放置更多的点会失败吗？我认为不会，因为涉及到更多不同的距离。 - SmacL