matrix - マトリックス内の領域を見つける..?

Question

10000x10000 個の要素がすべて値「0」を持つ非常に大きな行列があるとします。「1」の大きな「巣」がいくつかあるとしましょう。これらの領域は接続されている可能性もありますが、「1」の「パイプ」によって非常に毎週接続されています。

これらの「1」の「ネスト」を非常に迅速に（必要に応じてダーティに）見つけるアルゴリズムを取得したいと考えています。ここでは、2 つの毎週接続された「巣」を「切り離す」べきではありません。

このようなアルゴリズムをどのように行うべきか考えていますか?

Answer 1

この場合、A* (または BFS や DFS などのより単純なもの) のような経路探索アルゴリズムが機能する可能性があります。

あなたはできる：

• 小さな巣を見つけて検索の開始点を検索します（パイプを無視します）..少なくとも3x3の1のブロック
• 次に、マトリックス内の「接続されたコンポーネント」（詩的なライセンス）を終了するまで、そこから1を通過するパスファインディングを行う必要があります
• 別の小さな 1 のブロックから繰り返します

Answer 2

1. マトリックスを白黒のビットマップに変換します
2. サイズ N のネストが 1 つのピクセルになるように行列をスケーリングします (したがって、10x10 のネストを探す場合は、N=10 倍にスケーリングします)。
3. 出力の残りのピクセルを使用して、巣を見つけます。中心座標 (上記の係数を掛けたもの) を使用して、マトリックス内の同じネストを見つけます。
4. ローパス フィルターを使用して、ネストを接続するすべての「パイプ」を取り除きます。
5. ビットマップ上でコントラスト フィルターを使用して巣の境界を見つけます。
6. ネストを含まないビットマップを作成します (つまり、ネストのすべてのピクセルを 0 に設定します)。
7. 単一のピクセルを広げるフィルターを使用して、巣の輪郭を大きくします。
8. 7 と 5 の出力をビットごとに計算ANDして、すべてのパイプの接続ポイントを取得します。
9. パイプをたどって、巣がどのように接続されているかを確認します

Answer 3

それは、データがどのように必要とされるかによると思います。2 つのポイントが与えられた場合、それらが同じ 1 のブロックにあるかどうかを確認する必要がある場合は、@Jack の回答が最適だと思います。これは、ブロックが最初にどこにあるかについてある程度の知識がある場合にも当てはまります。これは、それらをアルゴリズムの開始点として使用できるためです。

他の情報がない場合は、次のいずれかが考えられます。

ポイントが与えられ、同じブロック内のすべての要素を検索したい場合は、塗りつぶしが適切です。次に、各ネストを見つけたらキャッシュし、別のポイントを取得したら、最初にそれが既知のネストにあるかどうかを確認し、そうでない場合はフラッド フィルを実行してこのネストを見つけ、それをキャッシュに追加します。

実装の詳細として、マトリックスをトラバースすると、各行は前の行に存在するネストのセットを使用できるようにする必要があります。次に、新しいポイントが既知のセットにあるかどうかを判断するために、完全なセットではなく、それらのネストに対して新しいポイントをチェックするだけで済みます。

確率的な影響に対処できる場合は、ハッシュテーブルやブルーム フィルターなど、ルックアップ コストが非常に低いセット実装を必ず使用してください。