python - 计算从一个点到所有其他点的距离

Question

我正在处理消防栓位置的 ID、X 和 Y 数据列表。我正在尝试为列表中的每个消防栓找到最近的三个消防栓。

a = [[ID, X, Y],[ID, X, Y]]

我尝试使用 for 循环来实现此目的，但遇到了麻烦，因为在迭代点列表时无法保持原始点数据相同。

是否有一种直接的方法来计算从一个点到其他每个点的距离，并为列表中的每个点迭代此距离？我对 python 很陌生，还没有看到任何关于如何在线执行此操作的信息。

任何帮助将不胜感激。

Answer 1

您不必计算所有点到所有其他点的所有距离即可获得所有点的三个最近邻点。

一个kd-tree search由于其 O(log n) 复杂度而不是蛮力方法(计算所有距离)的 O(n**2) 时间复杂度，因此效率会更高。

示例

import numpy as np
from scipy import spatial

#Create some coordinates and indices
#It is assumed that the coordinates are unique (only one entry per hydrant)
Coords=np.random.rand(1000*2).reshape(1000,2)
Coords*=100
Indices=np.arange(1000) #Indices 

def get_indices_of_nearest_neighbours(Coords,Indices):
  tree=spatial.cKDTree(Coords)
  #k=4 because the first entry is the nearest neighbour 
  # of a point with itself
  res=tree.query(Coords, k=4)[1][:,1:]
  return Indices[res]