画像のカタマリを判定

質問

白黒2色を使ったの画像があります。
■■■■■■■■■■■■
■■■■■□■■■■■■
■■■■□□□■■□■■
■■■□■■■□□■□■
■■□■■■■■■■□■
■■□■□□■■■■□■
■■■□■■□■□□■■
■■■■■■□□■■■■
■■■■■■■■■■■■
任意の黒ドットから白ドットに触れずに画像のフチにたどり着けるのか否かを判定する効率的なアルゴリズムを知りたいです。
別の言い方をすれば、その黒ドットは島なのか大陸なのかの判定です。
もしご存知の方がいらっしゃいましたら
とっかかりとなるキーワード等でもかまいませんので、教えていただけますでしょうか。
一応、環境はflashのaction script3ですが別の言語でも構いません。
よろしくお願いいたします。

回答No.1

BlurFiltan

> flashのaction script3ですが別の言語でも構いません。

ということで。

私も回答者の中の１人に入っていますが，
私以外の方も別言後で色々な方法を書かれています。

質問番号：3990775 「多角形の内部かどうか判定する方法」
http://okwave.jp/qa3990775.html

そこ（回答番号：No.7）でも 書いていますが，
私だと，とにかく白線内を塗りつぶします。島を島として塗る。
それでその塗り(島)と ■ との当たり判定をとります。

　塗り(島)と■が当たっている→画像のフチにたどり着けない
　塗り(島)と■が当たっていない→画像のフチにたどり着ける

私の場合なにしろ出がグラフィック系ですから，
内積だの曲線の方程式だのは考えていられません。

そこでは一応 ActionScript1.0 でベクタ図形を塗りつぶす方法を書いていますが，
ビットマップ画像だと塗りにくいかもしれません。
その他データなどの状況によるので何とも言えません。
場合によっては塗りつぶすというより，
白線境界内を □ のスプライトやムービークリップでり配置するということが必要かもしれません。
塗りつぶす（または埋めつくす）ということまでができると後は当たり判定でできると思います。

私は ActionScript3.0 に関しては全くと言って良いほどわかりませんが，
当たり判定自体は，BitmapData との当たり判定や ムービークリップと点との当たり判定 など色々できると思います。

Google検索 「当たり判定 ActionScript 3」
http://www.google.co.jp/search?hl=ja&q=%E5%BD%93%E3%81%9F%E3%82%8A%E5%88%A4%E5%AE%9A+ActionScript+3

その他何かヒントになることが見つかるかもしれません（???）。
Google検索 「塗り潰し アルゴリズム」
http://www.google.co.jp/search?hl=ja&q=%E5%A1%97%E3%82%8A%E6%BD%B0%E3%81%97+%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

お礼

ご回答ありがとうございます。
すごく参考になります。

今のところ輪郭抽出のアルゴリズムで
http://homepage2.nifty.com/tsugu/sotuken/ronbun/sec3-2.html#0014
で、画像のフチにたどり着くか起点に戻ってくるかで判定しようかと考えています・・・が処理速度が心配で・・・

塗りつぶしと、輪郭抽出どちらも試してみて処理速度を比べてみようと思います。

あと、補足ですが
■■■■■■■■■■■■
■■■■■□■■■■■■
■■■■□□□■■■■■
■■■□□■■□□□□■
■■□■■■■■■■■■
■■□□□□■■■□■■
■■■□■□□■□□■■
■■■■■■□□■■■■
■■■■■■■■■■■■

このように島が存在しない画像もありえることを想定しています。