2D配列（長方形の行列）が直線を持つかどうかを調べる方法

Question

アルゴリズムの問​​題を解決する際にこの問題が発生しました。長方形の行列があります。

私は、彼らが一直線に落ちるならば、どのように私は例えばのために、計算することができ、入力として位置のペアを取得します。この場合、実際には直線である（d、B）（c、D）（b、F）（a、H）として入力されます。 私たちが注意深く見れば、短辺のカウンターは1ずつ飛び、長辺のカウンターは2跳びます。このロジックに基づいてコードを書くと、より大きな四角形または私はその論理に問題に直面することができますか？

ここでは、傾斜した直線は2種類しかないと仮定しています。 1）両方のカウンタが正方形の行列の対角線のように1ずつジャンプする場合。 2）カウンターが短い側で1、長い側で2でジャンプしている上記のケース。

直線になる可能性があるが、上記のいずれの条件にも合わず、単一行または一列にない点群がありますか？まあ

Answer 1

、の2つのから始めましょう例縮退：あなたは（どちらかのラインがあります、またはそのような行がありません）望むようにあなたがポイント、答えを持っている場合

• を
• あなたの場合または2つのポイントを持って、答えは常にはい

です

3+ポイントがあり、それらがすべて同じ行にあるかどうかを確認したいとします。任意の2つの点(x1, y1)と(x2, y2)を取る。もう一度2つのケースがあります：

• x1 == x2;すべてのポイントがそのようなものであることを確認してください。xi == x1

• x1 != x2;

   (y1 - y2) * (xi - x2) == (yi - y2) * (x1 - x2) 
  (y2*x1 - y1*x2) * (xi - x2) == (y2*xi - yi*x2) * (x1 - x2) 
  

すなわち：すべての点がが満たされるように2つの条件があることを確認してくださいすべてのポイントは、私たちが同じ行にある

(2, 4) 
    (4, 3) 
    (6, 2) 
    (8, 1) 

ポイントを持っているA = 1, B = 2, ..., H = 8; a = 1, b = 2, ..., d = 4kとbがあなたの場合

(x1, y1)と(x2, y2)から派生しているのと同じy = kx + bライン、上にあります。可能（C＃）の実装：

private static bool SameLine(IEnumerable<Tuple<int, int>> points) { 
    if (null == points) 
    return true; 

    Tuple<int, int>[] data = points.ToArray(); 

    // i = 2 - first two points are always on the same line 
    for (int i = 2; i < data.Length; ++i) { 
    int x1 = data[0].Item1; 
    int y1 = data[0].Item2; 

    int x2 = data[1].Item1; 
    int y2 = data[1].Item2; 

    int xi = data[i].Item1; 
    int yi = data[i].Item2; 

    // y = k * x + b where k = infinity 
    if (x1 == x2) { 
     if (xi != x1) 
     return false; 

     continue; 
    } 

    // Same k in y = k * x + b 
    if (!((y1 - y2) * (xi - x2) == (yi - y2) * (x1 - x2))) 
     return false; 

    // Same b in y = k * x + b 
    if (!((y2 * x1 - y1 * x2) * (xi - x2) == (y2 * xi - yi * x2) * (x1 - x2))) 
     return false; 
    } 

    return true; 
} 

テスト

Tuple<int, int>[] test = new Tuple<int, int>[] { 
    new Tuple<int, int>(2, 4), 
    new Tuple<int, int>(4, 3), 
    new Tuple<int, int>(6, 2), 
    new Tuple<int, int>(8, 1), 
    }; 

    // Same line 
    Console.Write(SameLine(test) ? "Same line" : "different lines");