10

各セクターは (x,y,r,a,d) として表すことができます。ここで、x,y は位置、r は半径、d は方向、a は角度です。2 つの円形セクターに関するこれらの情報が与えられた場合、それらが互いに重なるかどうかを判断するにはどうすればよいでしょうか? それを解決するための効率的なアルゴリズムはありますか? ありがとう！

4

3 に答える 3

8

以前に円の衝突に使用したことがあるので、可能性を割り引く非常に簡単な方法を知っています。

2 つの中心間の距離を計算し、それが半径の合計よりも大きい場合、衝突はあり得ません。効率を高めるために、平方根を使用せず、2 乗した値を直接処理してください。

if (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) > (r1 + r2) * (r1 + r2):
    # No chance of collision.

円セグメントの計算は少し難しくなります。

どの方法を選択するかは、必要な精度によって異なります。実際の計算を行っている場合は、おそらく高い精度が必要です。ただし、たとえば、コンピューター ゲームなどでこれを行っている場合は、十分に近くても十分な場合があります。

その場合、円弧を一連の直線に変換することを検討します (その数はおそらくa円弧の「広がり」に依存します。 1 度の円弧の広がりですが、180 度ではうまく機能しません)。

比較の数が急速に増加する可能性があるという事実に対処する必要がありますが、直線衝突検出ははるかによく知られている方法です。

線分を使用したくない場合は、次のプロセスに従います。円衝突アルゴリズムを使用して、完全な円のゼロ、1、または 2 つの衝突点を見つけ、それらの点をチェックして、それらが両方の円弧内にあるかどうかを確認します。

最初に、上記のチェックを実行して、衝突が発生しないケースを検出します。円同士が衝突しない場合、円弧も衝突しません。

次に、円に単一の衝突ポイントがあるかどうかを確認します。次の場合に該当します。

(x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1) == (r1 + r2) * (r1 + r2)

もちろん、適切な誤差範囲内で。浮動小数点数を比較して等しいかどうかを判断するには、ある種のデルタ比較を使用する必要があることを、今ではすべて知っているはずです。

そんなときは、チェックポイントが1つあれば、そのポイントを簡単に見つけることができます。orからor にr1至る直線に沿ったポイント単位であり、その線に沿って分数を移動すると見なします。(x1,y1)(x2,y2)

(x1 + (x2-x1) * (r1+r2) / r1, y1 + (y2-y1) * (r1+r2) / r1)

それ以外の場合は、チェックするポイントが 2 つあります。このような質問への回答を使用して、それらの 2 つのポイントが何であるかを確認できます。

いくつかの衝突ポイントを取得したら、それらのポイントが円弧上にあるかどうかを確認する方法ははるかに簡単です。ただし、候補ポイントが衝突するには、一方だけでなく両方の円弧上にある必要があることに注意してください。

于 2012-05-22T01:38:12.373 に答える
4

2つのステップがあります。最初に、2 つの中心が衝突を許すほど十分に接近しているかどうかを調べます。これは、それらの間の距離をそれらの半径の合計と比較することによって行うことができます。

if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) > ((r1 + r2) * (r1 + r2)))
    // No collision.

次に、中心間の線がさまざまな角度で定義された円弧内にあるかどうかを確認する必要があります。

float angle1to2 = Math.atan2(y2 - y1, x2 - x1);
if (angle1to2 < (d1 - a1/2) || angle1to2 > (d1 + a1/2))
    // No collision
float angle2to1 = angle1to2 + Math.PI;
if (angle2to1 < (d2 - a2/2) || angle2to1 > (d2 + a2/2))
    // No collision

衝突の可能性を除外せずにこれらのチェックを通過した場合は、衝突を正常に検出したことになります。

警告: このコードはまったくテストされていません。特に、atan2座標系によっては、呼び出しに微調整が必​​要になる場合があります。

編集:これは、アークが互いに「指している」のではなく、まだ重なっている重要なコーナーケースを見逃していることに気付きました。これについて反芻し、戻ってきます...

于 2012-05-22T01:52:51.897 に答える
1

扇形は円形なので、リアルタイムでこれを行う場合、角度と方向は問題になりません。以下は、完全な円のセクター、または両方のセクターが互いに指している場合にのみ適用されます。

次の手順を実行できます。

1) 各セクター間の距離を求めます。2) その距離から両方の半径を引きます。3) 結果が負の場合、両方のセクター間に衝突がありました。それ以外の場合は、衝突までの距離です。

たとえば、2 つのセクターがあり、どちらも半径 50 単位です。中心点間の距離は 80 です。80-50-50 = -20 を引くと、20 単位の距離で衝突があったことがわかります。

それ以外の場合、距離が 500 の場合、500-50-50 = 400 (正の値) であり、これら 2 つのセクターが 400 単位離れていることがわかります。

ここで、円が近すぎる場合、たとえば 1 単位離れている場合、1-50-50 = -99 となり、ほぼ完全に重なり合っていることを意味します。

コメントで指定した真のセグメント化された円形セクターについては、paxdiablos または Macs の回答を使用する必要があります。

于 2012-05-22T01:41:20.947 に答える