计算到多个点的最小距离的地图
Computing an map of minimum distance to a number of points
给定点列表 obstacles
(以 row, column
矩阵坐标的列表形式给出,形状为 (n, 2)
的 ndarray),return 大小为 size
(其中 size
是二维 NumPy 数组的形状)其中 r, c
的值是到最近的 "obstacle."
的欧氏距离
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
我的方法真的很慢,我觉得应该有更好的方法。
Here 是使用 Numpy 和 SciPy 的 KD 树解决类似问题的方法。只需将您的障碍物插入 KD 树并查询树中的每个网格点以获得其最近的邻居。
我最终使用了 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
给定点列表 obstacles
(以 row, column
矩阵坐标的列表形式给出,形状为 (n, 2)
的 ndarray),return 大小为 size
(其中 size
是二维 NumPy 数组的形状)其中 r, c
的值是到最近的 "obstacle."
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
我的方法真的很慢,我觉得应该有更好的方法。
Here 是使用 Numpy 和 SciPy 的 KD 树解决类似问题的方法。只需将您的障碍物插入 KD 树并查询树中的每个网格点以获得其最近的邻居。
我最终使用了 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