半径内でオブジェクトを見つける

Question

半径内でオブジェクトを見つけるための軽量な方法を探しています。

これまでのところ、私にとって明らかな答えは、各オブジェクトを通過し、そのXとYの位置を半径の中心と比較することです。

例：

Turret - 半径のターゲットを探しています。

TargetArray - 可能なターゲットの配列。

WithinRangeArray - 適用されるターゲットをプッシュします

Distance^2 = (TargetArray[n].x - Turret.x)^2  +  (TargetArray[n].y - Turret.y)^2

if( Distance^2 < maxRadius^2 ){
WithinRangeArray.push(TargetArray[n])
}

平方根を避けることで、処理能力を節約できます。しかし、私は他のアルゴリズム/理論/方法がより良い（より軽量）になるかもしれないと感じています。

理想的なターゲットアレイの長さ：一度に500未満のターゲット。

Answer 1

放射状距離を計算する前に、最初にオブジェクトが砲塔の位置を中心にあるボックス内にあるかどうかを確認します。 Target_X <Turret_X-Rangeの場合、範囲外で距離を確認する必要はありません。Turret_x+範囲、turret_y-range、turret_y+範囲も確認します。これには、最大4つの比較と4つの追加/減算OPSが必要です。ターゲットがボックスにあるかどうかを判断します。

Answer 2

2Dでは、クワッドツリーを実装でき、3Dではオクトリーを実装できます。これは、正確な距離を実際にチェックする前に、オブジェクトをグループ化し、より効率的にそれらの大きなグループを破棄できることを意味します。あなたがもっと知りたいなら、あなたは彼らのためにグーグルでなければなりません。それらは、オブジェクトの世界の非常に有用なデータ構造です。

最終的な実装はスペースをそれほど節約しないかもしれませんが、膨大な数のオブジェクトを非常に迅速に破棄できるため、非常に高速になります。

Answer 3

可能なターゲットは、占有するグリッドスクエアにキー付きマルチセットに保存できます。次に、ターゲットである可能性のあるタレットのグリッドスクエアに十分に近いグリッド正方形にあるターゲットを反復するだけです。

これが価値があるかどうかにかかわらず、ターゲットの数と、範囲がある可能性が高いターゲットの数に依存します。私は数十万のターゲットを持つアプリケーションに取り組んでいますが、10または20のみが範囲内にある可能性があります。この状況では、潜在的なターゲットリストを剪定するために、かなりの複雑さに投資する価値があります。あなたの場合、わずか500のターゲットで、それは価値がないかもしれません。