4

ランダムに配置された任意の数のポリゴン（この場合はヘクス）がありますが、それらはすべて別のヘクスに接触しています。

ここに画像の説明を入力してください

個々のヘクスには6つのx、y頂点があります。頂点はすべてのヘクスで知られています。

誰かが私を、すべてのヘクスを1つのポリゴンに結合するアルゴリズムの方向に向けることができますか？基本的に、私は、ある頂点から次の頂点に線を引くときにポリゴンを形成するように順序付けられた頂点位置の配列を吐き出す関数を探しています。

これはこれまでの私の方法です：

  1. すべてのヘクスのすべての頂点の配列を作成します。
  2. 配列内で頂点が発生する回数を決定します
  3. 頂点が配列内に3回以上ある場合は、配列から頂点を削除します。
  4. 頂点が配列に2回含まれている場合は、そのうちの1つを削除します。

ただし、次のステップは注意が必要です。私はキャンバスを使用してこれらのポリゴンを描画しています。これには、基本的に、ある頂点から次の頂点に線を描画することが含まれます。したがって、最終的な配列の頂点の順序は重要です。任意に並べ替えることはできません。

また、ポリゴンを正しく描画できないため、「凸包」アルゴリズムは探していません。

このようなことをする関数はありますか？私は正しい方向に進んでいますか、それとももっと効率的な方法がありますか？

4

3 に答える 3

5

私はこのようなことをします：

  1. すべての側面をリストします。辺は2組の座標で定義されます。
  2. いずれかの側が複数回表示される場合は、その側のすべてのインスタンスを削除します。
  3. 任意の側を選択し、その側からそのポイントの1つを選択します。
  4. そのポイントを配列に配置します。
  5. 現在の側をたどり、もう一方のポイントを配列に配置します。
  6. フォローした側を削除します。
  7. 次に、配列の最後の点と同じ点を持つ反対側を見つけます。そのような側面は1つだけになります。ない場合は、完了です。
  8. 手順5に戻ります。

これで、必要な形状を順番に構成するポイントの配列ができました。

これは穴を処理しないことに注意してください。形状は、単一のパスで定義可能である必要があります。

于 2012-12-01T23:08:22.360 に答える
0

線を構成する座標ペアを追跡しなければ、形状の外側の境界を決定することは不可能です。

線を構成する座標ペアがわかっている場合は、

  1. 2つのリストを作成します。1つは頂点（リスト1）、もう1つはライン（リスト2）です。
  2. 頂点リストから重複する頂点をすべて削除します
  3. 3本の線が接続されているすべての頂点の新しいリスト（リスト3）を作成します
  4. リスト3を使用して、2つの頂点を2つの座標ペアとしてリスト3から削除します。
  5. 形状をトラバースするときが来ました。残りの線のリストは、任意の座標から始めて、（x1、y1）=現在の座標の場合はすべての線の各座標に対して、（x2、y2）をスタックに追加するだけで目的の形状を形成する必要があります。その行をリストブレークから削除しますelseif（x2、y2）=現在の座標次に（x1、y1）をスタックに追加し、その行をリストブレークから削除します
于 2012-12-02T00:27:17.660 に答える
0

各ヘクスについて、6つの頂点のリストがあります。必要に応じてリストを並べ替えて、頂点が反時計回りの順序になるようにします（これが数学的な規則です）。

これで、ポリゴンのセット（最初は六角形）ができました。アイデアは、ポリゴンが1つだけになるまで（またはできるだけ少なくなるまで）ポリゴンを結合することです。

ポリゴンのエッジを選択し、他のポリゴンの中から同じエッジ（つまり同じ頂点のペア）を探します。2つのインスタンスがある場合は、そのエッジで2つのポリゴンを結合します。たとえば、（a、b、c、d、e、f）+（g、h、d、c、i、j）=>（a、b、c 、i、j、g、h、d、e、f）。（2つの頂点が両方のポリゴンで同じ順序である場合、またはエッジのインスタンスが3つ以上ある場合は、エラーを報告して中止します。）すべてのエッジを反復処理します。ヘクスが実際に連続したグループを形成した場合、ポリゴンは1つだけ残ります。

ポリゴンのエッジが重複している可能性があります。エッジが複数回発生する場合は、リストを2つに分割して削除します。たとえば、（a、b、c、d、b、a、e、f、g）=>（b、c、d）+（a、 e、f、g）。または、エッジが隣接している場合は、それらを削除します：（a、b、c、b、d、e）=>（a、b、d、e）。または、そのリストにそのエッジしかない場合は、リストを削除します：（a、b）=>何もありません。

重複するエッジを削除すると、ポリゴンの反時計回りの外側のエッジのリストが1つになり、穴の時計回りの内側のエッジのリストが1つ以上表示される可能性があります。

于 2012-12-02T02:28:45.660 に答える