在3D空间中沿着特定轴有效查找最近点

我一直在玩这个游戏几天，并且一直跑到性能墙上。在3D空间中沿着特定轴有效查找最近点

数据：

10秒到几十万3D的点
点是正/负整数，并落在一个三维网格没有重叠
很少会加点
通常是无间隙的，但可能有间隙

结构：

必须能够有效地找到沿每个轴（“最靠近的点左”）最近的邻居和只有那个轴。
很少处理插入或施工后删除（但必须处理它们）
不需要处理重叠点

我发现在http://docs.scipy.org/doc/scipy/reference/spatial.html一个可能的解决方案，然而kd树似乎是极其浪费对于这种类型的数据（适用于更多的任意点的聚类）并进行调整以找到半径内的点。这些数据的主要用例通常是找到（和跟踪）每个点的最近邻点。

的示例数据（X，Y，Z）：

[(4, 3, 0), (4, 4, 0), (5, 3, 0), (3, 3, 0), (4, 3, 1), ...]

也许我的谷歌福失败了我和最佳结构存在已经（最好是在Python），但我一直没能找到一个。

来源

2012-03-20 TkTech

对不起，我没有你的答案，但我很好奇你想要做什么，需要这样多样的分析。 – 2012-03-20 13:46:36

你是在飞机上这样做的吗？根据您选择的点与其他点之间的绝对差异对列表进行排序有什么问题？ – Ben 2012-03-20 13:48:39

@burhan这是一个[minecraft]（http://minecraft.net）地形编辑器库。现有的库（例如：[pymclevel]（https://github.com/mcedit/pymclevel））非常混乱且效率低下。这种方法旨在通过简单的抽象来支持任何现有的世界格式，将其分解为固定大小的网格，其中关键是高效地遍历该网格。没有这一点，没有什么意义。 – TkTech 2012-03-20 13:51:40

如何构建3 KD-树木为X，Y，Z轴分别？无论如何你需要某种树结构IMO。

来源

2012-03-20 14:04:10

赢得kd-tree！听起来就像是一个完美的数据结构。 – wheaties 2012-03-20 14:07:05

嗯，发现“最接近左边”，而且如果你在x = 4上说了多个点，那么将会证明很棘手，那么就需要找到其他轴上的关闭点。

请问如下更简单的“最近点”不起作用？

for n in xrange(len(points)): 
    diff = (((x0-points.x[n])**2) + ((y0-points.y[n])**2) + ((z0-points.z[n])**2))**0.5

然后，只需剔除掉 'n' 个具有最小差异（不包括如果包括当前点）..：/

来源

2012-03-20 13:56:57 headcrab

尽管你不需要** 0.5，但据我所知，它是关于识别哪个点最接近而不是实际距离（以及事件是否可以将时间应用到最近点）。 – deinonychusaur 2012-03-20 14:00:19

如果只有这些点在它们跟随该轴并且其他轴的值是静态的情况下才被计数为最近的，即（1,1,0）将没有资格作为最接近于（0,0,0），但（4,0,0），将你可以：

import numpy as np 
#The .T is ofcourse not neccesary here but then you have to fix it below as well. 
points = np.asarray([(4, 3, 0), (4, 4, 0), (5, 3, 0), (3, 3, 0), (4, 3, 1)]).T 
#You have still to check thiss for all points just showing for pt 0 
on_same_xy = (points[:-1,:].T == points[:-1,0]).all(axis=1) 

z_distance = (points[2,on_same_xy] - points[2,0]) 
z_distance_up = z_distance[np.where(z_distance > 0)] 
if z_distance_up.size == 0: 
    up = None 
else: 
    up = z_distance_up.min() 

z_distance_down = z_distance[np.where(z_distance < 0)] 
if z_distance_down.size == 0: 
    down = None 
else: 
    down = z_distance_down.max() 

print "Z-up-neighbour %s, Z-down-neighbour %s" % (str(up), str(down))

既然你有两个第一坐标值只是的点[-1,0]，然后可以从上到下访问上下点的位置以及距离。

我意识到代码有点混乱，但是一旦大数据集在内部时它真的应该工作得更快。另外，这也是你的问题所要求的问题。

来源

2012-03-20 15:20:08 deinonychusaur

在3D空间中沿着特定轴有效查找最近点

回答

相关问题