是否有多個點組成一個圓圈？

Question

如果我有例如20分，我如何檢查這些點是否能彌補一個圈？它不一定是一個完美的圓圈。

例如，如果我每隔200毫秒存儲一次鼠標的座標（當用戶移動鼠標時），我想查看用戶是否做出圓圈手勢。我不希望用戶做出完美的圈子。

Answer 1

我做了以下內容：

• 計算best fit circle through the points
• 計算剩餘的每一個點（從中心到該點減最佳擬合圓半徑的連接距離）
• 接受的結果，如果殘差足夠大的比例分別爲低於定義爲最佳擬合半徑的一小部分的某個值。這些參數將是用戶可定義的驗收標準。

Answer 2

更新：從@LastCoder的建議刪除太接近前一個點的連續點（我設置的閾值在10的距離;也許它可以增加），容差水平設置爲0.25（即差異距離中心點的平均距離爲25％是可以接受的），我所做的應用程序在超過一半的情況下識別我的「圈子」，並且不再受廣場欺騙。畢竟，這可能不是一個壞主意。

---

我會找到centroid對於給定的點的集合，並檢查是否從重心到各點的距離或多或少是相同的（假設你希望全圓的近似，不只是一個弧）。

它在實踐中適用於檢測用鼠標完成圓形手勢的問題;看到an example in C#（VS2010中，只有主要形式，應用程序的其餘部分是自動的樣板;在忽略的ideone錯誤）和在這裏的截圖：

Answer 3

這裏有一個簡單的方法，我把一個工作實現放在一起。

http://jsfiddle.net/kBsdW/29/

• 循環遍歷點
• 查找與第一
• 記錄的距離
• 的最大距離第二點一旦你把所有的最大距離取它們的平均值，計算容錯度
• 檢查所有記錄的距離與您的容錯度

這對於鼠標或觸摸傳感器等用戶輸入非常適用。該算法是O（n^2），並使用delta最大距離而不是找到質心和檢查半徑距離。

它似乎比最佳擬合圓方法更有效率，它必須計算每個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; 
}