0-1の配列で矩形座標を効率的に見つける方法

Question

私は0と1のMxN行列を持っているとします。それはまばらであるかもしれないし、そうでないかもしれない。

私は機能が効率的に矩形で私が意味する、アレイ、で四角形を見つけたい：ように、

長方形の4つの隅を作成するすべての1点のある4つの要素のセット矩形の辺は、配列軸の と直交しています。つまり、矩形は、[r1、c1]、[r1、c2]、 [r2、c2]、[r2、c1]のような座標[行インデックス、列インデックス]を持つ4 1の要素 のセットです。 。

など。この設定は、一つの矩形があります指定されたM×Nのアレイについて

0 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
1 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 1 

、私が欲しいのPythonの関数各サブアレイは、矩形の角の座標対であるFサブアレイのアレイLを返す（A）、（長方形の4つのコーナーのすべてを含む）。配列の同じ要素が複数の矩形の角である場合は、それらの座標を複製しても問題ありません。

---

私の考え方は、これまでのところです：

1）は、それが一部であるかどうかを確認するために座標配列

2）確認し、各直角三角形の頂点にそれぞれ直角三角形の頂点の座標を見つけますステップ1）は、1であり、列sum> = 2であり、行sum> = 2である列にある要素を見つけることによって達成することができる。

ステップ2）は直角三角形の頂点であると決定された各座標を反復する。与えられた直角三角形の座標対について、それはその列を反復し、その列にある1）のすべての直角三角形座標を調べます。列内の2つの直角三角形のポイントのペアについては、どちらの行がより小さい行合計を持つかをチェックして、どの行が反復処理が速いかを知ることができます。次に、その行の直角三角柱の座標をすべて反復して、他の行にもその列に直角三角形の点があるかどうかを確認します。そうであれば、それらの4つの点は矩形を形成します。

私はこれがうまくいくと思いますが、繰り返しがあり、全体的にはこの処理は合理的に計算集約的であるようです。 0-1配列の長方形のコーナーを検出するためのより良い方法は何ですか？

Answer 1

これは私の頭の上からで、LAXでの5時間のレイオオーバー中です。以下は、私のアルゴリズムです：

ステップ1：少なくとも 2のもの

| 0 0 0 1 0 1 0 
| 0 0 0 0 0 0 0 
| 0 1 0 0 0 0 0 
\|/ 1 0 0 1 0 1 0 
    0 0 0 0 0 0 0 
    0 0 0 1 0 0 1 

出力のためのすべての行を検索：

-> 0 0 0 1 0 1 0 
    0 0 0 0 0 0 0 
    0 1 0 0 0 0 0 
-> 1 0 0 1 0 1 0 
    0 0 0 0 0 0 0 
-> 0 0 0 1 0 0 1 

ステップ2：各ペアに対してそれぞれの行にあるは、1つの列に対応する列のインデックスを取得し、t彼は最初の行：

-> 0 0 0 1 0 1 0 

次の列のものかどうかを確認：

 | | 
     \|/ \|/ 

0 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
1 0 0 1 0 1 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 1 

ステップ3：両方のインデックスが一致した場合、すべての4つのインデックスを返します。これは、すべてのステップで行とインデックスを知っているので簡単にアクセスできます。

0 0 0 ->1 0 ->1 0 
0 0 0 0 0 0 0 
0 1 0 0 0 0 0 
1 0 0 ->1 0 ->1 0 
0 0 0 0 0 0 0 
0 0 0 1 0 0 1 

ステップ4：私たちの場合は、列3での検索は、5あなたは0からインデックスを開始すると仮定だから我々は、次のためなインデックスを取得3を返すしようとしているすべてのペアのための繰り返し

アルゴリズムの複雑さ columns * rows * number of pairsを検索する必要があることは知っていますが、常にハッシュマップを使用して検索を最適化することができますO(1)。これは複雑さを対の数に結びつけるものになります。お気軽にコメントしてください。

Answer 2

ここに@PseudoAjソリューションに似たPython実装があります。 dictを構築している最中から始まる行を処理します。ここで、キーはx座標であり、値はそれぞれy座標のセットです。リストの長さは、次の行に2未満でムーブ

反復にわたる場合

1. は
2. 現在の行から1Sとx座標のリストを生成する：すべての行以下のステップが行われるため

   すべてのペアごとに、座標ペアについてleft < right

3. は、すべての場合dict含む処理された行
4. から交差点を取るleft, right座標Yは、交差点の座標を現在の行からの座標

コードでdictを更新最後

をもたらすことが四角形を追加：

from collections import defaultdict 
from itertools import combinations 

arr = [ 
    [0, 0, 0, 1, 0, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 1, 0, 0, 0, 0, 0], 
    [1, 0, 0, 1, 0, 1, 0], 
    [0, 0, 0, 0, 0, 0, 0], 
    [0, 0, 0, 1, 0, 0, 1] 
] 

# List corner coords 
result = [] 

# Dict {x: set(y1, y2, ...)} of 1s in processed rows 
d = defaultdict(set) 

for y, row in enumerate(arr): 
    # Find indexes of 1 from current row 
    coords = [i for i, x in enumerate(row) if x] 

    # Move to next row if less than two points 
    if len(coords) < 2: 
     continue 

    # For every pair on this row find all pairs on previous rows 
    for left, right in combinations(coords, 2): 
     for top in d[left] & d[right]: 
      result.append(((top, left), (top, right), (y, left), (y, right))) 

    # Add coordinates on this row to processed rows 
    for x in coords: 
     d[x].add(y) 

print(result) 

出力：

[((0, 3), (0, 5), (3, 3), (3, 5))]