グリッド内の連続した色付き領域を決定するアルゴリズムはありますか？

StackOverflow https://stackoverflow.com/questions/452480

  •  19-08-2019
  •  | 
  •  

質問

各セルがランダムにn色のいずれかで塗りつぶされている基本的なグリッド（グラフ用紙のようなもの）を考えると、隣接する領域（セルのグループ）を教えてくれる実証済みのアルゴリズムがあります横で結合されている同じ色の）がありますか？ nが5のように合理的なものだとしましょう。

アイデアはいくつかありますが、どれもひどく非効率的です。

役に立ちましたか？

解決

最適なアルゴリズムはO（セルの数）であり、色の数とは関係ありません。

これは、セルを反復処理することで実現でき、訪問済みとしてマークされていないセルにアクセスするたびに、グラフトラバーサルを実行してその領域内のすべての連続するセルを見つけてから、反復を続けます。

編集：

ここでは、深さ優先検索の簡単な擬似コード例を示します。これは、グラフトラバーサルを簡単に実装できます。

function visit(cell) {
    if cell.marked return
    cell.marked = true
    foreach neighbor in cell.neighbors {
        if cell.color == neighbor.color {
            visit(neighbor)
        }
    }
}

他のヒント

再帰の再帰的な答えに加えて、再帰が遅すぎる場合はスタックを使用できます：

function visit(cell) {
    stack = new stack
    stack.push cell

    while not stack.empty {
        cell = stack.pop
        if cell.marked continue
        cell.marked = true
        foreach neighbor in cell.neighbors {
            if cell.color == neighbor.color {
                stack.push neighbor
            }
        }
    }
}

各広場で塗りつぶしを試すことができます。洪水が広がったら、グリッドの正方形を配列などに記録し、-1などの未使用の色で塗りつぶします。

Union-find はここで機能します同様に。実際、質問をグラフに関する問題として定式化できます。頂点はグリッドセルであり、グリッドセルの色が同じであれば2つの頂点が隣接しています。接続されているコンポーネントを見つけようとしています。

ユニオン検索データ構造の使用方法は次のとおりです。最初に、セルと同じ数の要素を持つユニオン検索データ構造を作成します。次に、セルを繰り返し処理します。同じ色の場合、隣接する2つのセルはunionです。最後に、各セルでfindを実行し、応答を保存します。同じ<=>のセルは、同じ連続した色の領域にあります。

もう少しきめ細かい制御が必要な場合は、 A * アルゴリズムを使用し、ヒューリスティックを使用して同様の色のタイルを含めます。

スキャンラインの領域を左から右、上から下に繰り返します。セルごとに、セル間で同じメモリオブジェクトとして共有されるセルのリストを作成します。セルごとに、現在のセルをリストに追加します（共有または作成されます）。次に、右または下のセルが同じ色の場合、そのリストをそのセルと共有します。そのセルに既にリストがある場合は、リストを結合し、リストにリストされている各セルのリストオブジェクトへの参照を新しい結合リストに置き換えます。

各セルに配置されているのは、そのセルと隣接するすべてのセルを含むリストへの参照です。これにより、すべてのセル間のフラッドフィルの作業が適切に結合されます。セルごとに繰り返すのではなく。あなたはリストを持っているので、データをマージされたデータで置き換えているのは、リストを反復するだけです。これはO（n * c）になります。nはセルの数で、cはグラフの連続性の尺度です。完全にばらばらのグリッドはn時間になります。 n ^ 2/2の完全に連続した1色グラフ。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top