複雑な形をした領域の「境界線」を求めるアルゴリズムを考えてみます。ただ境界線といっても、そもそもコンピュータは画面上に自ら描いた図形(ある色の領域)の「形」を直接「認識」する事はできません。そこで、境界にある「点」の座標を求め、その点を描いていく事で境界線を描くアルゴリズムを考えてみました。 この問題を目を閉じたまま部屋の境界線(壁)に沿って歩くにはどうすれば良いか、という問題として考えてみましょう。目を閉じているので、全体の形を一度に見渡す事はできませんが、歩く事でそこに壁が「あるかないか」わかりますし、壁を探り当てれば手を触れながら壁に沿って歩く事もできます。さらに、目を閉じていても現在の「位置」は常に把握できる、と仮定します。これで、コンピュータが画面内の図形に対してできる処理と同様の状況を作る事ができました。 では、具体的にどうすれば壁に沿って歩けるか、考えてみます。 ・プログラム実行例プログラムでは、部屋を32*32のマス(2次元配列 dot[x][y])で表す事にします。一番左上が(0、0)で、各要素はtrue ,false いずれかの値をとり、出発点は常に(16、16)です。出発点がtrue なら壁はfalse 、逆に出発点がfalseなら壁はtrue という事にしましょう。 出発点から上の方へ壁を探していき、壁が見つかったらそこに青い点を打ちます。後は右手をついて壁沿いに進んでいって、通過した場所は赤く表示します。位置を確認しながら壁沿いに進み、最初の地点に戻ったら壁(境界線)をすべてまわった事になるので「縁取り」終了です。 ・探査方向とdx, dy右 dx=-1/dy=0 下 dx=0/dy=1 左 dx=1/dy=0 上 dx=0/dy=-1 マウスでドラッグしながら適当に領域を作ったら、G o!ボタンをクリックすると領域の境界線が赤く表示されます。 |