java - グリッドのJAVAホール

Question

Javaの2Dグリッドで「穴」を見つける必要があります。これを行うための最良の種類のアルゴリズムを教えていただけますか？

以下の点を入力して：

5,3
5,4
8,4
5,5
6,3
7,3
7,4
6,5

このグリッドの「穴」または囲まれたスペースの位置を把握する必要があります。私はこれを行う方法について少し迷っています。

ポイントのプロット：

各ポイントが1x1であると仮定します

Answer 1

これは基本的にブロブ抽出アルゴリズム+少し余分です。これを行う：

1）ソリッドが配置されている最西端、最東端、最北端、最南端を見つけます。それらをxminxmaxyminymaxとして覚えておいてください。

2）整数の2d配列（0に初期化）をそれらの次元に割り当て、その中のすべての実線を値-1として配置します。

3）カウンタを1に初期化します。2Dアレイをスキャンします。0であるポイントを見つけるたびに、それをに設定しcounter、フラッドフィルcounterするポイントがなくなるまで、-1ではないすべての隣接するポイントにフラッドフィルします。（フラッドフィルを行うには、1つの方法は、まだすべてのネイバーをフラッドフィルしていないすべてのポイントのセットを保持し、これらを繰り返して、セットが使い果たされるまでセットに新しいポイントを追加することです->フラッドフィルするものは何も残っていません。）ここで、カウンターをインクリメントして続行します。

4）グリッド全体をスキャンしたら、周囲をスキャンします。周囲に-1以外の値が表示されるたびに、そのブロブを囲まれていないものとしてマークします（見つかったブロブの数と同じ数のboolの配列を使用します）。

5）マークしていない番号付きのブロブはすべて囲まれています。

ここでブロブ抽出について読んでください：http：//en.wikipedia.org/wiki/Blob_extraction