6

私は小惑星のクローンに取り組んでいます。すべてが 2D で、C++ で書かれています。

小惑星については、ランダムな N 辺のポリゴンを生成しています。私はそれらが凸であることを保証しました。次に、それらを回転させ、回転速度を与えて、宇宙を飛ばします。それはすべて機能し、とてもきれいです。

衝突には、自分で考えたアルゴリズムを使用しています。これはおそらく悪い考えであり、プッシュするようになった場合は、おそらくすべてを破棄して、インターネットでチュートリアルを見つけるでしょう.

私はすべてを書いて実装しましたが、衝突検出は問題なく動作します....ほとんどの場合。画面に明らかに衝突がある場合はランダムに失敗し、何も触れていないときに衝突を示すことがあります。実装をどこかでフラブしたか、アルゴリズムがひどいです。私の実装 (複数のソース ファイルにまたがる) のサイズ/スコープのために、私はそれについてあなたを悩ませたくありませんでした。私のアルゴリズムが実際に健全であることを誰かに確認してもらいたかっただけです。その時点で、私は大きなバグハントに行くことができます.

アルゴリズム：

小惑星ごとに、小惑星を描画するときに各頂点がどこにあるべきかを出力する関数があります。隣接する頂点の各ペアについて、頂点が置かれている線の式を生成します。 y=mx+bフォーマット。次に、船の頂点の 1 つから始めて、その点が小惑星の内部にあるかどうかをテストします。ポイントの X 座標を入力し、出力を実際の Y 値と比較することから始めます。これにより、ポイントが線の上にあるか下にあるかがわかります。次に、小惑星の中心についても同じことを行い、線のどの半分が小惑星の「内側」と見なされるかを判断します。次に、頂点のペアごとに繰り返します。ポイントが小惑星の中心と同じ側にない線を見つけた場合、衝突がないことがわかり、そのポイントの検出を終了します。私の船には 3 つのポイントがあるので、次のポイントをテストする必要があります。3 つのポイントすべてが早期に終了した場合、船のどのポイントにも衝突はなく、完了です。

このアルゴリズムで発見した 2 つの問題は次のとおりです。

  1. 凹面ポリゴンでは機能しません。
  2. Slope が定義されていない Edge の場合に問題があります。

NANすべてのポリゴンが凸面であることを確認し、未定義の勾配の問題を処理するコードを書きました ( で割るとdouble が返される必要0があるため、そのテストは非常に簡単です)。

それで、これはうまくいくでしょうか？

4

2 に答える 2

7

この問題の標準的な解決策は、分離軸定理 (SAT) を使用することです。2 つの凸多角形 A と B が与えられると、アルゴリズムは基本的に次のようになります。

for each normal N of the edges of A and B
    intervalA = [min, max] of projecting A on N
    intervalB = [min, max] of projecting B on N
    if intervalA doesn't overlap intervalB
        return did not collide
return collided
于 2013-01-31T16:33:27.063 に答える
2

ポリゴンの交差を計算するのと似たようなことをしました。つまり、頂点が特定のポリゴン内にあるかどうかを調べました。

あなたのアルゴリズムは健全であり、実際に凹型ポリゴンでは機能しません。選択した線の表現は、無限に近づく勾配でも問題があります。私はいくつかのベクトルを使用することを選択しました。1つは線の方向に、もう1つは線の基準点に使用します。これらから、直線のパラメータ化された方程式を簡単に導き出し、それをさまざまな方法で使用して、他の形状との交点を見つけることができます。

P = S +  t * D

線の任意の点Pは、上記の関係が与えられた場合、線上の座標tによって特徴付けることができます。ここで、Sは参照点であり、Dは方向ベクトルです。

この表現により、方向の向きのおかげで、平面のどの部分が正と負の部分（つまり、線の上と下）であるかを簡単に定義できます。これで、平面の任意の領域を、複数の線の負または正のサブ平面の交差として定義できます。したがって、「ポリゴン内のポイント」アルゴリズムを少し変更して、その表現を使用することができます。時計回りを指すすべての方向の制約が追加され、ポイントがすべての線の負のサブプレーンにあるかどうかがテストされます（したがって、ポリゴンの中心）。

私が使用した線に対する点の辺を計算する式は次のとおりです。

(xs - xp) * yd - (ys - yp) * xd

ポイントPがSに近い場合、勾配の問題がここに表示されます。

この表現はエッジの頂点を使用して計算できますが、正しいサブプレーンを作成するには、ポリゴン内の頂点を連続した順序で保持する必要があります。

凹多角形の場合、問題はもう少し複雑です。簡単に言うと、ポイントが2つの連続する凸エッジの間にあることをテストする必要があります。0これは、エッジに投影されたときにエッジ上のポイントの座標をチェックし、それがとの間にあることを確認することで実現できますlength(edge)（方向が正規化されていると仮定します）。ポイントがポリゴン内の三角形に属しているかどうかを確認するために要約されることに注意してください。

于 2013-01-31T18:39:28.793 に答える