3

2D の空 (10000x10000座標) があるとします。この空のどこにでも航空機があり、その位置によって識別されます(x, y)。任意の航空機は別の座標に (直線で) 移動を開始できます。

このすべての配置と移動を管理する単一のコンポーネントがあります。航空機が移動したい場合は、 の形式でメッセージを送信します(start_pos, speed, end_pos)。コンポーネントで、ある航空機が別の航空機の視線内を移動するタイミングを通知するにはどうすればよいですか (各航空機は、これをプロパティとして見通し半径として持っています)。多くの航空機が同時に移動する可能性があることに注意してください。また、このアルゴリズムは、最大 1000 の平面を処理できるため、効果的です。

なんらかの制約がある場合、それがソリューションを制限しています - おそらく削除できます。問題は解決されていません。

4

5 に答える 5

3
  • 線を使用して飛行経路を表します。
  • 各線をそれを囲む長方形に変換します。長方形の幅は、「閉じる」の定義によって決まります（安全距離が大きいほど、長方形の幅を広くする必要があります）。
  • 新しいフライトプランごとに：
    • 新しい長方形が別の長方形と交差するかどうかを確認します。
      • その場合、各平面がいつ衝突点に到達するかを計算します。時間差が小さすぎる場合（シナリオに応じて小さすぎると定義する必要があります）、新しいフライトプランを拒否します。
于 2010-12-08T11:04:12.503 に答える
3

時間的な側面 (つまり、航空機が移動するという事実を扱う) に対処したい場合は、潜在的に単純化することで、時間の次元によって問題を持ち上げることができると思います (もう 1 つの次元を追加します。したがって、元の問題は 2D であり、は 3D 問題になります)。

次に、問題は、線が（傾いた）円柱と交差する点を見つける問題になります。考えられるすべての交点を見つけると、n^2 になります。それが十分に効率的かどうかはよくわかりません。

于 2010-12-08T11:18:59.057 に答える
2

どの飛行機が特定の飛行機に近いかを簡単に見つけるためのデータ構造については、Wikipedia:Quadtreeを参照してください。これにより、O(N^2) の近さのテストを行う必要がなくなります。

于 2010-12-08T11:19:33.173 に答える
1

あなたには良い答えがあります、私は1つの側面についてのみコメントし、おそらく正しくはありません

  • 航空機はフォーム（start_pos、speed、end_pos）で移動すると言います
  • すべての航空機がそのようなものを持っている場合、それらをフライトプランと呼びましょう。そうすれば、いつどこでそれらが互いに一定の距離内にあるか、いつそれらが互いに最も近い点にあるか、または衝突/取得するかどうかを直接計算できるはずです。近すぎる

したがって、実際に飛行計画に従って移動し、それらから逸脱しない場合、問題は決定論的です。つまり、一連の方程式を解くことになります。これは、約1000の平面ではそれほど大きな作業ではありません。

これらの方程式をより速く解く必要がある場合は、他の回答で説明されている手法を使用できます。

  • 距離の計算を高速化できる効率的な構造（quadtree、octree、kd-trees）を使用して、
  • いくつかの関連する将来のタイムスライスについてのみ方程式を解くために問題を分割する
  • 距離が最も急速に変化するペアの方程式を解くことを優先します

もちろん、時間を3次元に変換すると、航空機がポイントからラインに変わり、2つの3Dラインの間で最も近いポイントを検索することになります（ここにいくつかの数学があります）

于 2010-12-08T11:52:17.127 に答える
-1

私は実際にこの質問に対する答えを見つけました。

それは本のリアルタイム衝突検出、p。223. 2D 球体が円である場合、Intersecting Moving Sphere Against Sphereとも呼ばれます。ここで説明するのは簡単ではありません (また、いくつかの権利を侵害する可能性もあります) が、基本的な考え方は、円の 1 つを点として固定し、その半径を移動円の半径に追加することです。移動するものの新しい方向は、2 つの元のベクトルの合計です。

于 2011-02-26T19:14:07.267 に答える