計算最小距離的一個映射到多個點

的考慮點obstacles（給定爲的row, column矩陣座標，形狀(n, 2)的ndarray列表）的列表，返回地圖大小size（的其中size是形狀2D NumPy數組），其中r, c的值是距離最近「障礙物」的歐幾里德距離。計算最小距離的一個映射到多個點

def gen_distgrid(size, obstacles): 
    n_obstacles = obstacles.shape[0] 
    distgrids = np.zeros((n_obstacles + 4, size[0], size[1])) 
    for layer in range(n_obstacles): 
     for i in range(size[0]): 
      for j in range(size[1]): 
       distgrids[layer, i, j] = np.linalg.norm(obstacles[layer,:] - [i,j]) 
    for i in range(size[0]): 
      for j in range(size[1]): 
       distgrids[n_obstacles + 0, i, j] = i 
       distgrids[n_obstacles + 1, i, j] = (size[0] - i) 
       distgrids[n_obstacles + 2, i, j] = j 
       distgrids[n_obstacles + 3, i, j] = (size[1] - j) 
    distgrid = np.min(distgrids, axis=0) 
    return distgrid

我的方法真的很慢，我覺得應該有更好的方法。

來源

2015-08-08 Simon Kuang

對不起，'r'和'c'是什麼？ – mgilson

@mgilson：行和列，或者你可以說'i，j'。 –

因此，對於每個障礙物，您想知道哪個障礙物最接近？ – mgilson

我最終使用了SciPy的a KD-tree。它具有非常簡單的距離功能。

from scipy.spatial import cKDTree as KDTree 
def gen_distgrid(obstacles): 
    n_obstacles = obstacles.shape[0] 
    obstacles = np.vstack((obstacles, [0,0], [0, size[1] - 1], [size[0] - 1, 0], [size[0] - 1, size[1] - 1])) 

    distgrid = np.zeros((size[0], size[1])) 
    obs_tree = KDTree(data=obstacles) 

    i_v = np.arange(size[0]) 
    j_v = np.arange(size[1]) 

    coordmat = np.dstack(np.meshgrid(i_v, j_v, indexing='ij')) 
    obs_dists, obs_locs = obs_tree.query(coordmat) 

    top_dists = np.repeat(i_v, size[1]).reshape(size) 
    bottom_dists = np.repeat(size[0] - i_v, size[1]).reshape(size) 
    left_dists = np.repeat(j_v, size[0]).reshape(np.transpose(size)).T 
    right_dists = np.repeat(size[1] - j_v, size[0]).reshape(np.transpose(size)).T 

    dists = np.min([obs_dists, top_dists, bottom_dists, left_dists, right_dists], axis=0) 
    return dists

來源

2015-08-09 23:45:14

這不是理論上最好的，但它的速度驚人。 –

Here是使用Numpy和SciPy使用KD樹的類似問題的解決方案。只需將您的障礙物插入KD樹並查詢每個網格點的樹以獲取其最近的鄰居。

來源

2015-08-09 02:14:33 dpmcmlxxvi

計算最小距離的一個映射到多個點

回答

相關問題