2

毎秒異なる方向 (南東、南西、北東、北西) に移動する座標 (x と y) を持つ円のリストが与えられた場合、円は壁にぶつかると方向を変えます。バウンスのようなものですが、それらのいずれかが互いに衝突または重なり合っているかどうかをどのように検出しますか? Binary Search Treeすべての座標が毎秒変化するため、それに応じてツリーを再構築する必要があるため、a のようなデータ構造を使用できるかどうかはわかりません。または、毎回垂直スイープ ライン アルゴリズムを使用できますか? 効率的な方法でこれを行う方法についてのアイデアはありますか?

4

2 に答える 2

3

あなたの形は円だけなので、次のようになります。

  • 境界線までの距離が半径よりも小さい場合、円は長方形の境界線に接触します。
  • 中心間の距離が半径の合計よりも小さい場合、2 つの円は互いに接触します。

長方形の境界が水平軸上にX1あり、垂直軸上にあるとします（および）。最初のケースでは、円の中心が で、その半径が である場合、次のことを確認する必要があります。X2Y1Y2X1 < X2Y1 < Y2(x, y)r

  • x-r < X1?
  • x+r > X2?
  • y-r < Y1?
  • y+r > Y2?

これらのいずれかに該当する場合、円は長方形の境界に接しています。

2 番目のケースでは、円がそれぞれ(x1, y1, r1)およびで定義されているとし(x2, y2, r2)ます。かどうかを確認する必要があり(x1 - x2)^2 + (y1 - y2)^2 < (r1 + r2)^2ます。これが当てはまる場合、円は互いに接触しています。

于 2012-10-27T09:20:21.580 に答える
0

提供された仮定を考えると、次のようになります。

  • あなたの動く形は円だけです。
  • 壁は、ボックスを形成する垂直または水平の壁のみです。
  • 円は互いに衝突しません (実装は難しくありませんが)

次の単純なアルゴリズムを実装できます。

  • 円ごとに、現在の原点 (中心) からのオフセットとして 4 つの座標を追跡します。
    • 上、下、左、右（または北、南、西、東）
    • これらは、円と壁がこれら 4 つの正確な場所にある唯一の接触点であることに注意してください。
  • 円が移動した直後に、原点からの 4 つの座標のそれぞれをチェックして、壁の境界と重なっているかどうかを確認します (単純で怠惰な方法は、FPS / ボールの速度と同じ厚さの長方形として壁を作成することです)必要）
  • オーバーラップ検出の実装方法:
    • 壁を として実装したとしますRectangleWall。
    • で、 (またはシグネチャが である可能性がある) とRectangleWall呼ばれるパブリック メンバー関数を追加し、渡されるポイントが四角形の境界内にあるかどうかを確認するためのロジックを追加します。これは簡単なはずです ;)public boolean isPointInside(Point pt)(int x, int y)
  • オーバーラップを検出したときの衝突に対応するロジックを実装します。
    • ボールの左または右のスポットが何かと重なっている場合は、その x 速度を逆にします。
    • ボールの上部または下部のスポットが何かと重なっている場合は、その y 速度を逆にします。
于 2012-10-27T05:16:54.990 に答える