获取 3D 中点的 26 个最近邻居 space - 矢量化

Question

假设您在 3D space 中有一个坐标为 (2,2,2) 的点。如何使用 numpy（我正在考虑使用 meshgrid，我只是无法让它工作）或 scipy 对操作进行矢量化，以在 3D space 中找到 26 个最近的邻居？有 26 个邻居，因为我将点视为一个立方体，因此邻居将是沿立方体面的 6 个邻居 + 沿立方角的 8 个邻居 + 12 个连接到立方体边缘的邻居。

那么对于点(2,2,2)，如何得到如下坐标：

(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3), (1, 3, 1), (1, 3, 2), (1, 3, 3), (2, 1, 1), (2, 1, 2), (2, 1, 3) , (2, 2, 1), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), ( 3, 1, 2), (3, 1, 3), (3, 2, 1), (3, 2, 2), (3, 2, 3), (3, 3, 1), (3, 3, 2), (3, 3, 3)

我已经用三重 for 循环实现了它，它可以工作。但是，速度对我的系统至关重要，因此我需要对该操作进行矢量化处理，以免我的系统出现故障。三重for循环如下：

neighbors = [] # initialize the empty neighbor list

# Find the 26 neighboring voxels' coordinates
for i in [-1, 0, 1]: # i coordinate
    for j in [-1, 0, 1]: # j coordinate
        for k in [-1, 0, 1]: # k coordinate
            if (i ==0 and j ==0 and k ==0): # if at the same point
                pass # skip the current point
            else:
                neighbors.append((self.current_point[0]+i,self.current_point[1]+j,self.current_point[2]+k)) # add the neighbor to the neighbors list

这是我第一次 post 访问 Whosebug，如有遗漏，请见谅。这是我想在无人机上使用的路径规划算法，因此时间很关键，这样我就不会撞墙或其他东西。

Answer 1

如果您已经有了要作为 numpy 数组进行比较的坐标，假设它是 x，那么您可以计算 (2, 2, 2) 和 x 之间的欧氏距离

distances = np.power(x - (2, 2, 2), 2).sum(axis=1)

现在你只需要 26 个最小的索引，你可以用 np.argpartition

indices = np.argpartition(distances, 26)[:26]

现在，获取实际元素：

elements = x[indices, :]

例如，如果 x 只是您提供的一组点，则

distances = np.power(x - (2, 2, 2), 2).sum(axis=1)
indices = np.argpartition(distances, 2)[:2]
elements = x[indices, :]

这个returns

array([[1, 2, 2],
       [2, 1, 2]])

符合预期。

请注意，this 高度评价的答案声称此函数在线性时间内 argpartition 运行s，而不是常规排序的 nlog(n) 时间带到运行.

Answer 2

您可以使用 itertools.product 轻松创建运动方向：

from itertools import product 
motion = np.array(list(product(m, repeat=3)))
motion
>>> array([[-1, -1, -1],
           [-1, -1,  0],
           [-1, -1,  1],
           [-1,  0, -1],
           [-1,  0,  0],
           [-1,  0,  1],
           [-1,  1, -1],
           [-1,  1,  0],
           [-1,  1,  1],
           [ 0, -1, -1],
           [ 0, -1,  0],
           [ 0, -1,  1],
           [ 0,  0, -1],
           [ 0,  0,  0],
           [ 0,  0,  1],
           [ 0,  1, -1],
           [ 0,  1,  0],
           [ 0,  1,  1],
           [ 1, -1, -1],
           [ 1, -1,  0],
           [ 1, -1,  1],
           [ 1,  0, -1],
           [ 1,  0,  0],
           [ 1,  0,  1],
           [ 1,  1, -1],
           [ 1,  1,  0],
           [ 1,  1,  1]])

这很简单，但比纯 numpy 慢：

m = [-1, 0, 1]
motion = np.stack(np.meshgrid(m, m, m), axis=-1).reshape(-1, 3)

或：

motion = np.transpose(np.indices((3,3,3)) - 1).reshape(-1, 3)

然后删除原点(0, 0, 0)（在中间）：

motion = np.delete(motion, 13, axis=0)

然后你就可以捕捉到所有周围的点了：

motion + [[2, 2, 2]]
>>> array([[1, 1, 1],
           [1, 1, 2],
           [1, 1, 3],
           [1, 2, 1],
           [1, 2, 2],
           [1, 2, 3],
           [1, 3, 1],
           [1, 3, 2],
           [1, 3, 3],
           [2, 1, 1],
           [2, 1, 2],
           [2, 1, 3],
           [2, 2, 1],
           [2, 2, 3],
           [2, 3, 1],
           [2, 3, 2],
           [2, 3, 3],
           [3, 1, 1],
           [3, 1, 2],
           [3, 1, 3],
           [3, 2, 1],
           [3, 2, 2],
           [3, 2, 3],
           [3, 3, 1],
           [3, 3, 2],
           [3, 3, 3]])

获取 3D 中点的 26 个最近邻居 space - 矢量化

Get 26 nearest neighbors of a point in 3D space - vectorized

python

numpy

scipy