高速な閉領域を判定をするアルゴリズム

Question

高速な閉領域を判定をするアルゴリズムを考えています。
画像1のようにマスが塗りつぶされているかいないかの値が入っている2次元配列bool[,]が用意してある場合に、
画像2のように赤色のマス(矩形)を配置した場合に、赤斜線のような閉鎖されているマスを高速に判別するアルゴリズムをご教授いただきたいです。

調べたところ閉領域を塗りつぶすアルゴリズムは存在するのですが、その手法だとすべてのマスを走査する必要があるので、低速になってしまいます。

データとしてbool[,]の他に、塗りつぶされた重複しているマスのないの矩形情報(画像1を例にすると、座標(2,2)から幅4、高さ1の矩形、座標(1,3)から幅2、高さ4の矩形、座標(2,7)から幅5、高さ2の矩形)を参照ものできるものとします。

ヒントだけでもありがたいです。よろしくお願い致します。

現状思いついている最適化

• 新しく配置した矩形が、0または1種類の矩形にしか隣り合っていない場合は新しく閉領域となる部分は存在しない

画像1

画像2

Answer 1

• 前提として，黒塗りの領域は常にラベリング処理により，各領域を区別できるようにしておきます．

• 赤矩形が与えられたとき，赤矩形と隣接する黒マス群のラベル値を調べます．
  ある黒領域が赤矩形と協力(?)して新たな閉領域を作る場合，その黒領域のラベルが複数回登場するハズです．
  （下図で黄色矩形で示した場所が赤に隣接する黒マス．この２つのマスには同じラベル値が付与されているハズ）

• 前ステップで，どの黒領域について調べれば良いのかがわかったので，
  その領域の黒マスと赤マスとが共有する「角」から輪郭を追跡します．
  （図では２つの矢印で例示）
  輪郭を辿る際は，「（黒あるいは赤で）塗られているマスの内側を常に左側に見る」といったルールを設けて辿る方向を決めます．
  （図の例はこのルールで辿る形になっている）

• 輪郭を辿って元の位置に戻ってきたとき，領域の輪郭形状が得られます．
  あとは，その輪郭が「閉領域」を成す物か否かを判定するだけです．
  （図の例では，緑で示した輪郭追跡結果を棄却し，青で示したものを採用すべきである）
  このことは，輪郭追跡中に出会った「角」が「左曲がり と 右曲がり のどちらが多かったか」とかで判定できるかと．

• ※閉領域内のマスを列挙したい場合には，後段処理として，ふつーの塗りつぶし処理的なことを行う等してください．
  輪郭情報が得られているのだから，塗りつぶし開始点は自明なハズです．

Comments

[fana]

赤領域と黒領域との隣接部のラベル値を調べる際に，
隣接している黒マスがある場合には「１箇所」として数える等の工夫をすれば，
「赤領域と黒領域が（閉領域を作らずに）接しているだけ」みたいな状況に対する無駄な探索を省くこともできるでしょう．

[concern12]

ご回答ありがとうございます。
ご回答いただいた手法でうまくいきそうです！
一つ質問ですが、
>隣接している黒マスがある場合には「１箇所」として数える等の工夫をすれば，
がわからなかったので、もう少し詳しくご説明していただけないでしょうか？

[fana]

黒マスを■，赤マスを□とするとき，例えば，

■■■■■
□□□

みたいな状況で何も工夫しない場合，３つの■が赤領域に隣接しているため，

> その黒領域のラベルが複数回登場するハズ

という話を満たしてしまいます．
この状況で輪郭追跡を走らせるのは無駄です．

この状況を
「赤領域に ■が３個 隣接している」ではなく「赤領域と黒領域が １箇所で 隣接している」と判断できれば
輪郭追跡を走らせずに済みます．

[fana]

処理効率を考える（無駄処理を削る）なら

■■■□
■■　□
■■■□
■■■□

これを「３箇所で接する」じゃなくて「２箇所で接する」と判定できるように，【赤矩形と隣接する黒マス群のラベル値を調べる処理】を作りましょう，って話．

[fana]

まぁ，あとは，
「ある黒領域と赤領域とがN箇所で接する」と分かった時点で，閉領域がいくつ生まれるハズなのかがわかると思うので，
処理中に閉領域がその個数見つかった時点で終了してよい，だとか，そういう細かい工夫を入れる余地はあるかと．

[fana]

■■■■■■■■
■■■■□□　■■■
■　　　□□■■■
■　■■□□■■
■　■　□□
■　■■□□■■■■
■　　　□□　　■■
■■■■□□■■■

こういう，複数の黒領域が赤領域に接する場合に，同じところを何度も追跡しちゃわないように，とか，実装においてはいろいろ考えることはあると思うけど，頑張って．

[concern12]

細かく最適化できそうですね。
試行錯誤してみます。
ありがとうございました！