时间戳

首页 > 解决方案 > 计算一个点到所有其他点的距离

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

问题描述

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

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

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

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

任何帮助将不胜感激。

标签： pythonproximity

解决方案

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

由于其 O(log n) 复杂度而不是蛮力方法（计算所有距离）的 O(n**2) 时间复杂度，kd-tree 搜索将更加有效。

例子

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]

推荐阅读