找到比一组点中的给定距离（接近度）更近的对

I'm developping a multiplayer game with node.js. Every second I get the coordinates (X, Y, Z) of every player. How can I have, for each player a list of all players located closer than a given distance from him ?

我正在使用node.js开发多人游戏。每一秒我都得到每个玩家的坐标（X，Y，Z）。对于每个玩家，我如何能够获得距离他一定距离更近的所有玩家的列表？

Any idea to avoid a O(n²) calculation?

有没有想过避免O（n²）计算？

3 个解决方案

#1

You are not looking for clustering algorithms.

您不是在寻找聚类算法。

Instead, you are looking for a database index that supports radius queries.

相反，您正在寻找支持半径查询的数据库索引。

Examples:

例子：

R*-tree
R * - 树
kd-tree
kd树
M-tree
M-树
Gridfile
Gridfile
Octree (for 3d, quadtree for 2d)
八叉树（3d，四叉树2d）

Any of these should do the trick, and yield an O(n log n) performance theoretically. In practise, it's not as easy as this. If all your objects are really close, "closer than a given coordinate" may mean every object, i.e. O(n^2).

任何这些都应该成功，并在理论上产生O（n log n）性能。在实践中，它并不像这样容易。如果所有对象都非常接近，“比给定坐标更近”可能意味着每个对象，即O（n ^ 2）。

#2

What you are looking for is a quadtree in 3 dimensions, i.e. an octree. An octree is basically the same as the binary tree, but instead of two children per node, it has 2^D = 2^3 = 8 children per node, where D is the dimension.

您正在寻找的是三维的四叉树，即八叉树。八叉树基本上与二叉树相同，但是每个节点不是两个子节点，而是每个节点有2 ^ D = 2 ^ 3 = 8个子节点，其中D是维度。

For example, imagine a cube. In order to create the next level of the root, you actually have every node representing the 8 sub-cubes inside the cube and so on.

例如，想象一个立方体。为了创建根的下一级，实际上每个节点都代表多维数据集中的8个子多维数据集，依此类推。

This tree will yield fast lookups but careful not to use it for more dimensions. I had built a polymorphic quadtree and wouldn't go to more than 8-10 dimensions, because it was becoming too flat.

此树将产生快速查找，但小心不要将其用于更多维度。我已经构建了一个多态四叉树，并且不会超过8-10维，因为它变得太平了。

The other approach would be the kd-tree, where actually you halve the dataset (the players) at every step.

另一种方法是kd-tree，实际上你在每一步都将数据集（玩家）减半。

You could use a library that provides nearest neighbour searching.

您可以使用提供最近邻搜索的库。

#3

I'm answering my own question because I have the answer now. Thanks to G. Samaras and Anony-Mousse: I use a kd-tree algorithm:

我正在回答我自己的问题，因为我现在有了答案。感谢G. Samaras和Anony-Mousse：我使用kd-tree算法：

First I build the tree with all the players
首先，我与所有玩家一起构建树
Then for each player I calculate the list of all the players within given range arround this player
然后对于每个玩家，我计算该玩家周围给定范围内的所有玩家的列表

This is very fast and easy with the npm module kdtree: https://www.npmjs.org/package/kdtree

使用npm模块kdtree非常快速和简单：https：//www.npmjs.org/package/kdtree

var kd = require('kdtree');
var tree = new kd.KDTree(3); // A new tree for 3-dimensional points
var players = loadPlayersPosition(); // players is an array containing all the positions
for (var p in players){ //let's build the tree
    tree.insert(players[p].x, players[p].y, players[p].z, players[p].username);
}

nearest = [];    
for (var p in players){ //let's look for neighboors
    var RANGE = 1000; //1km range
    close = tree.nearestRange(players[p].x, players[p].y, players[p].z, RANGE);
    nearest.push(close);
}

It returns nearest that is an array conataining for each player all his neighboors within a range of 1000m. I made some tests on my PC with 100,000 simulated players. It takes only 500 ms to build the tree and another 500 ms to find the nearest neigboors pairs. I find it very fast for such a big number of players.

它返回最接近的数组，每个玩家的所有邻居都在1000米的范围内。我在PC上用100,000个模拟玩家进行了一些测试。构建树只需要500毫秒，另外500毫秒可以找到最近的neigboors对。对于如此众多的玩家，我发现它非常快。

bonus: if you need to do this with latitude and longitude instead of x, y, z, just convert lat, lon to cartesian x, y z, because for short distances chord distance on a sphere ~ great circle distance

奖励：如果你需要用纬度和经度而不是x，y，z做这个，只需将lat，lon转换成笛卡尔x，y z，因为短距离球面上的弦距离〜大圆距离

#1