JavaScriptのアルゴリズム：コンポーネントが円形であるか

Question

場合取得するためにX/Y-点を確認してください私はこのような行列を持っているので、私はあなたが円のアウトラインを得ることができることを望む：

EDIT 1：何についてのアウトライン？アウトラインには空白が含まれていません（すべてのy値が最小2 x値を取得するように）

EDIT 2：円とは何ですか？以下の例のように、より正確な「正確な円」を探してください！ （すべての点でほぼ同じ半径）

00000000000000000000000000000000 
    00000000000001111111100000000000 
    00000000000100000000010000000000 
    00000000010000000000000100000000 
    00000000100000000000000010000000 
    00000000100000000000000010000000 
    00000001000000000000000001000000 
    00000010000000000000000000100000 
    00000010000000000000000000100000 
    00000010000000000000000000100000 
    00000100000000000000000000100000 
    00000100000000000000000000100000 
    00000100000000000000000000100000 
    00000100000000000000000000100000 
    00000100000000000000000000100000 
    00000010000000000000000000100000 
    00000010000000000000000000100000 
    00000010000000000000000001000000 
    00000001000000000000000010000000 
    00000000100000000000000010000000 
    00000000100000000000000100000000 
    00000000010000000000001000000000 
    00000000000111111111100000000000 
    00000000000000000000000000000000 
    00000000000000000000000000000000 

と私はまた、アウトラインのすべての位置を含めて、このような配列がありますかどうかを確認するための良い方法です何

var coordinates = [ 
    [13,1],[14,1],[15,1],[16,1],[17,1],[18,1],[19,1],[20,1], 
    [11,2],[21,2], 
    [9,3],[23,3], 
    [8,4],[24,4], 
    [8,5],[24,5], 
    [7,6],[25,6], 
    [6,7],[26,7], 
    [6,8],[26,8], 
    [6,9],[26,9], 
    [5,10],[26,10], 
    [5,11],[26,11], 
    [5,12],[26,12], 
    [5,13],[26,13], 
    [5,14],[26,14], 
    [6,15],[26,15], 
    [6,16],[26,16], 
    [6,17],[25,17], 
    [7,18],[24,18], 
    [8,19],[24,19], 
    [8,20],[23,20], 
    [9,21],[22,21], 
    [11,22],[12,22],[13,22],[14,22],[15,22],[16,22],[17,22],[18,22],[19,22],[20,22]] 

を座標は円に一致していますか？

私の最初のアイデアは、このようにいくつかのコードを使用していたが、TBH、私は&より効率的な方法は、作業方法があります確信している：

​​

Answer 1

あなたのアルゴリズムのみをチェックしているようだが、 X軸とY軸の4つの最も遠い点。私はあなたが正方形の形状を表すポイントを提供する場合、それはまたis_circleテストに合格すると思います。

の余白をとし、eという2段階テストを行うことを提案します。ポイント全体を歩き、x_min, y_min, x_maxとy_maxを覚えておいてください。次に、XのデルタとYのデルタとの差がエラーマージン、すなわちabs((x_max-x_min) - (y_max-y_min)) <= eにあるかどうかを確認します。それは形状が楕円形ではなく円形になるように角形をチェックします。そのテストに合格した場合は、中心点cを(x_c, y_c) = (x_min+(x_max-x_min)/2, y_min+(y_max-y_min)/2)に、各点について半径（任意の点から中心までの距離c）が誤差マージンe内にあるかどうかを計算します。高価な計算を節約するために、各点の自乗半径が誤差範囲内にあるかどうか、すなわちabs((x-x_c)^2 + (y-y_c)^2 - r^2) <= eである場合、r^2が中心cとリストの最初の点について計算されているかどうかを確認します。