查找大集合中的nearset邻居

Question

我在多维空间中有大量的点。我想找到几个邻居（在附近）任何给定的点（要求是为了避免扫描所有点）。

我想知道如果我的解决办法是适当的：

预处理：

1. 定义设置的ortogonal轴系
2. 使每个点的投影每个轴上
3. 每个投影都与从轴（键）的起点到点（值）的标识符的距离相关联。 指数预测 - 把所有的人都到有序set（如树集）

dist = distance of projection to the start point of axis 
point_num = number of point 
sorted_set.put(dist, point_num) 

找到任何给定的点的邻居：

1. 查找其投射在每个轴上
2. 使用idexes - 在每个exis上查找最近投影数
3. 查找实际的邻居 - 相交所有的导致

dx = radius of neighborhood (some constant) 

dist_1 = distance of projection of given point to start point of axis_1 
list_1 = sorted_set_1.get_sub_set(dist_1 - dx, dist_1 + dx) 

dist_2 = distance of projection of given point to start point of axis_2 
list_2 = sorted_set_2.get_sub_set(dist_2 - dx, dist_2 + dx) 

return intersection_of(list_1, list_2) 

下面是一个简单的例子：

相交[2, 4, 1]和[4, 5]产生回答[4]

请点我，如果我在我的算法来实现任何错误

感谢

Answer 1

你还没有给我们关于如何建立你的实际邻居设置指令，在这种情况下[2, 4, 1]和[4, 5]。你为什么选择一个索引中的3个元素和另一个索引中的2个？

你还声明你想找几个邻居。有多少是应该作为您的功能的输入？在这个例子中，你只能找到一个，算法决定你想要多少？

在所有点位于某个轴上的某一行上的情况下会发生什么情况？那么一套肯定会包含所有元素。