在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空間中沿着特定軸有效查找最近點

回答

相關問題