領域の境界線(縁取り)

 複雑な形をした領域の「境界線」を求めるアルゴリズムを考えてみます。ただ境界線といっても、そもそもコンピュータは画面上に自ら描いた図形(ある色の領域)の「形」を直接「認識」する事はできません。そこで、境界にある「点」の座標を求め、その点を描いていく事で境界線を描くアルゴリズムを考えてみました。

この問題を目を閉じたまま部屋の境界線(壁)に沿って歩くにはどうすれば良いか、という問題として考えてみましょう。目を閉じているので、全体の形を一度に見渡す事はできませんが、歩く事でそこに壁が「あるかないか」わかりますし、壁を探り当てれば手を触れながら壁に沿って歩く事もできます。さらに、目を閉じていても現在の「位置」は常に把握できる、と仮定します。これで、コンピュータが画面内の図形に対してできる処理と同様の状況を作る事ができました。

では、具体的にどうすれば壁に沿って歩けるか、考えてみます。
まず、出発点は部屋の中央です。とりあえず、壁を探り当てるためにまっすぐに歩く事になるでしょう。そして、壁に行き当たったら現在の「位置」を覚えておきます。次に、壁に右手(あるいは左手)をついて、壁に沿って歩いて行って進行方向の壁に行き当たったら、壁に右手をついたまま回転して歩ける場所を探します。 そしてずっと歩き続け、最初の位置に戻ってきたら壁にそって部屋の「境界線」を歩いた事になるわけです。

・プログラム実行例

 プログラムでは、部屋を32*32のマス(2次元配列 dot[x][y])で表す事にします。一番左上が(0、0)で、各要素はtrue ,false いずれかの値をとり、出発点は常に(16、16)です。出発点がtrue なら壁はfalse 、逆に出発点がfalseなら壁はtrue という事にしましょう。

 出発点から上の方へ壁を探していき、壁が見つかったらそこに青い点を打ちます。後は右手をついて壁沿いに進んでいって、通過した場所は赤く表示します。位置を確認しながら壁沿いに進み、最初の地点に戻ったら壁(境界線)をすべてまわった事になるので「縁取り」終了です。
 壁伝いに「歩く」ためには右手をついたまま進もうとしている方向に壁があるかを調べ、なければそのまま進んであれば調べる方向を反時計周りに回転させていきます(なぜ反時計周りなのかは、壁に右手を付いて歩いてみればすぐにわかるでしょう)。なお、進んだ後には探査方向を一つ(90°)時計周りの方向に「戻す」必要がある点に注意してください。これは右手に壁があるか調べる事で、壁に右手をつきながら、という条件を満たすための処理です。この処理をしないと、壁に突き出た部分があった場合その部分を回り込む事ができず、壁から離れてしまいます。探査方向は、変数dx, dyで決めていますので、dx, dyをどのように変えれば探査方向がどうなるか、に注目しながらソースを読むと良いでしょう。現在の要素にdx, dyを加えた要素を調べれば、調べる方向に壁があるかないかがわかります。

・探査方向とdx, dy

右 dx=-1/dy=0 下 dx=0/dy=1 左 dx=1/dy=0 上 dx=0/dy=-1

プログラムソース表示

 マウスでドラッグしながら適当に領域を作ったら、G o!ボタンをクリックすると領域の境界線が赤く表示されます。