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

Question

我正在用node.js开发多人游戏。每秒我都会得到每个玩家的坐标（X，Y，Z）。我怎么能为每个玩家列出距离他一定距离的所有玩家？

任何想法，以避免O（n²）的计算？

Answer 1

我回答我自己的问题，因为我现在有答案。由于G.萨马拉斯和Anony-慕斯： 我用kd树算法：

• 首先，我建立了树所有的球员
• 然后每个球员，我计算的所有球员中的列表给定的范围角落找寻这个球员

这是非常快速和容易与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); 
} 

它返回nearest这是一个阵列，每个玩家在1000米范围内拥有所有他的邻居。我用10万个模拟玩家在我的电脑上做了一些测试。建立树只需要500毫秒，另外需要500毫秒来找到最近的neigboors对。对于如此众多的球员，我发现它非常快。

奖金：如果你需要用经纬度来代替X，Y，Z要做到这一点，只是转换纬度，经度笛卡尔X，YZ，因为对于短距离弦上的球体〜大圆距离距离

Answer 2

您并不是在寻找聚类算法。

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

实例：

• R * -tree
• kd树
• M-树
• Gridfile
• 八叉树（为三维，四叉树为2d）的

任何这些应该做的伎俩，并在理论上产生一个O(n log n)表现。实际上，这并不容易。如果所有物体都非常接近，“比给定坐标更近”可能意味着每个物体，即O（n^2）。

Answer 3

你在找什么是一个四叉树三维，即八叉树。八叉树基本上与二叉树相同，但每个节点代替两个孩子，每个节点有2^D = 2^3 = 8个子代，其中D代表维度。

例如，想象一个立方体。为了创建根的下一层，实际上每个节点都代表立方体内的8个子立方体等等。

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

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

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