在一組點中找到比給定距離（鄰近）更近的對

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，其中你實際上在每一步都將數據集（玩家）減半。

您可以使用提供最近鄰居搜索的庫。