c++ - 如何在C++中获取距给定位置一定距离内的对象列表

Question

• 我有一个位置为 (x, y) 的对象集合
• 这些物体随机移动
• 可能有数千个

在任何时刻，我都会获得从位置 POS 开始的(恒定)半径 RAD 内的对象列表。

编辑 - 上下文:它用于游戏服务器，(乌托邦)有数千名玩家。当玩家移动/[做出 Action ]时，我想将更新发送给半径内的其他玩家。

最简单的方法，每次我需要列表时:

near_objects;
foreach( objects o ) {
    if( o.distance( POS ) < RAD )
        near_objects.add( o )
}

我想有更好/更快的方法，但我不知道要搜索什么。

Answer 1

这里有两个建议。

通常您使用 sqrt( (a.x-b.x)^2 + (a.y-b.y)^2 ) 计算距离，而昂贵的部分是计算 sqrt()，如果您在循环外计算一次 RAD^2 并将其与在 sqrt() 内部，您可以避免在循环中计算 sqrt()。

如果大部分物体距离较远，您可以使用以下方法消除它们

if( abs(a.x-b.x) > RAD ) continue;
if( abs(a.y-b.y) > RAD ) continue;