配列内のその時点にタイルがあるかどうかを示すブール値のみを含む 2D 配列があります。これは次のように機能します。たとえば、array[5,6] が true の場合、座標 (5,6) にタイルがあるとします。配列によって記述される形状は、内部に穴がある可能性のある接続された多角形です。
基本的に必要なのは、配列内の形状を記述する頂点と面のリストだけです。
私はしばらく探しましたが、この問題の解決策を見つけることができませんでした。
編集：これはすべて行われているので、形状を取り、それらを一緒に衝突させることができます.
このプロジェクトは、プログラミングのスキルや物理学などを向上させるために私が行っていることです。
Edit2: 助けてくれてありがとう。基本的に私の問題は、ビットマップ画像をベクター画像に変換するのと非常によく似ていました。http://cardhouse.com/computer/vector.htmは、将来誰かが私と同じ問題に遭遇した場合に役立ちます。
個々のピクセルに焦点を合わせすぎないでください。ピクセルの角（4つのピクセルが交わる点）に焦点を合わせます。これらのコーナーの座標は、ピクセルのハーフオープン座標とよく似ています。ハーフオープン境界は下限で包括的ですが、上限で排他的であるため、1から3までのハーフオープン範囲は{1、2}です。
エッジのセットを定義します-2つのピクセル間の単一ピクセル長の線（垂直または水平）。次に、隣接グラフを作成します。2つのエッジがポイントを共有している場合、それらは隣接しています。
次に、接続されているエッジのセットを特定します。これは、すべてのポイントが直接または間接的に相互に接続されているサブグラフです。論理的には、接続されているほとんどのサブグラフは閉ループを形成する必要があり、すべてのループが単純な閉ループと見なされるようにする必要があります。
1つの問題は、ビットマップのエッジです。ビットマップが無限ビットマップのごく一部であり、すべての範囲外のピクセルの値が0であると想像すると、状況が単純化される可能性があります。そのルールに基づいて、ビットマップのエッジにピクセルエッジを含めます。これにより、すべてのループが確実に閉じられます。
また、4つの境界エッジがあるピクセルコーナーを検討してください。つまり、ピクセルパターンが...
1 0 0 1
0 1 1 0
これらの場合、「1」ピクセルは別々のポリゴンの一部と見なす必要があります（そうしないと、巻き取りルールが複雑になります）。これらの場合の隣接のルールを微調整して、基本的に2つの接続された（直角の）エッジを取得します。これらのエッジは、あるポイントで偶然に接触しますが、隣接しているとは見なされません。それらはまだ接続できますが、他のエッジを介して間接的にのみ接続できます。
また、フラグの追加の配列を使用して、ループですでに使用されているピクセルエッジを識別します。1つは水平エッジ用、もう1つは垂直エッジ用です。これにより、繰り返し評価することなく、すべてのループを簡単に見つけることができます。メインビットマップをスキャンし、関連するエッジを見つけたら、スキャンしてループ全体を見つける前に、これらの配列をチェックします。ループをスキャンするときに、これらの配列に関連するフラグ（またはループID番号）を設定します。
ところで-これらのステップをすべて文字通りのbuild-this-data-structureステップとは考えないでください。むしろ、抽象化レイヤーと考えてください。重要な点は、グラフ操作を行っていることを認識することです。ビットマップを参照するアダプタを使用することもできますが、特殊なグラフデータ構造を使用しているかのように、グラフアルゴリズムが直接使用するのに適したインターフェイスを提供します。
特定のループが穴であるかどうかをテストするには、（たとえば）左端の垂直ピクセルエッジ（ループ上）を選択します。右側のピクセルが塗りつぶされている場合、ループはポリゴン境界です。左側のピクセルが塗りつぶされている場合、ループは穴です。注-適切なテストピクセルは、ループの周りをトレースする前に、最初のピクセルエッジを見つけたときに見つけたものです。これはそのような左端ではないかもしれませんが、そのスキャンラインの左端/最上部になります。
最後の問題は単純化です-ピクセルエッジが一緒に直線に走る場所を見つけます。これは、最初にループを識別するスキャンに組み込むことができますが、スキャンを適切に開始する前にコーナーを見つけるのがおそらく最善です。これで、各行は、while-I-can-continue-tracing-the-same-directionループを使用して識別されますが、これらの2つのポリゴンが角に触れる問題に注意してください。
これらすべてを組み合わせようとすると、複雑な混乱のように聞こえるかもしれませんが、トリックは、問題を異なるクラス/関数に分割することです。たとえば、ビットマップなどの基礎となるレイヤーの抽象化されたビューを提供するクラスを使用します。呼び出しのオーバーヘッドや最適化についてあまり心配する必要はありません。インラインおよびその他のコンパイラの最適化でそれを処理する必要があります。
本当に興味深いのは、対角線や曲線などを取得できる、一部のベクターグラフィックプログラムがこれまで行ってきたよりインテリジェントなトレースです。
希望する結果を明確にする必要があります。次のようなもの
██ ██
██
██ ██
与えられた
1 0 1
0 1 0
1 0 1
入力として？はいの場合、これは非常に些細なことのように思われます。配列エントリごとに1つの四角形があれば、それ以外の場合は何も生成しないのはなぜですか。
この問題は、単純なステートマシンを使用して解決できます。現在の状態は、現在の位置（x、y）と現在の方向（左（L）、右（R）、上（U）、または下（D））で構成されます。「X」は現在の位置であり、状態の変化を制御できる8つのネイバーがあります。
0 1 2
7 X 3
6 5 4
次に、次のルールに従います。状態X、Y、Dで、指定された2つのフィールドを確認し、それに応じて状態を変更します。
X,Y,R,23=00 => X+1,Y,D
X,Y,R,23=01 => X+1,Y,R
X,Y,R,23=10 => X+1,Y,U
X,Y,R,23=11 => X+1,Y,U
X,Y,D,56=00 => X,Y+1,L
X,Y,D,56=01 => X,Y+1,D
X,Y,D,56=10 => X,Y+1,R
X,Y,D,56=11 => X,Y+1,R
...