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

Question

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

a=[[ID，X，Y]，[ID，X，Y]]

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

有没有一种简单的方法来计算从一个点到其他每个点的距离，并对列表中的每个点进行迭代？我是python的新手，还没有在网上看到任何关于如何做到这一点的内容。

如有任何帮助，我们将不胜感激。

Answer 1

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

kd树搜索由于其O(logn(复杂度而不是蛮力方法(计算所有距离(的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]

Answer 2

开始吧。假设您有一个格式为[[ID, X, Y],[ID, X, Y]]的输入列表。

当循环通过每个消防栓时，您可以简单地循环通过每个消火栓，并计算它们之间的最小距离。您只需要有一些变量来存储每个消防栓的最小距离和最近消防栓的ID。

import math # for sqrt calculation

def distance(p0, p1):
""" Calculate the distance between two hydrant """
return math.sqrt((p0[1] - p1[1])**2 + (p0[2] - p1[2])**2)

input = [[0, 1, 2], [1, 2, -3], [2, -3, 5]] # your input list of hydrant
for current_hydrant in input:  # loop through each hydrant
min_distance = 999999999999999999999999
closest_hydrant = 0
for other_hydrant in input:  # loop through each other hydrant
if current_hydrant != other_hydrant:
curr_distance = distance(current_hydrant, other_hydrant) # call the distance function
if curr_distance < min_distance: # find the closet hydrant
min_distance = curr_distance
closest_hydrant = other_hydrant[0]
print("Closest fire hydrants to the", current_hydrant[0], "is the hydrants",
closest_hydrant, "with the distance of", min_distance)  # print the closet hydrant

由于距离函数不是很复杂，我重写了它，你可以使用scipy或numpy库中的其他函数来获得距离。

希望这能有所帮助；(

Answer 3

如果您有地理位置，我们可以执行简单的距离计算(https://en.m.wikipedia.org/wiki/Haversine_formula)以获得两个位置之间的公里距离。此代码并不意味着高效。如果这是你想要的，我们可以使用numpy来加快速度：

import math
def distance(lat,lon, lat2,lon2):
R = 6372.8  # Earth radius in kilometers
# change lat and lon to radians to find diff
rlat = math.radians(lat)
rlat2 = math.radians(lat2)
rlon = math.radians(lon)
rlon2 = math.radians(lon2)
dlat = math.radians(lat2 - lat)
dlon = math.radians(lon2 - lon)

m = math.sin(dlat/2)**2 + 
math.cos(rlat)*math.cos(rlat2)*math.sin(dlon/2)**2
return 2 * R * math.atan2(math.sqrt(m),
math.sqrt(1 - m))
a = [['ID1', 52.5170365, 13.3888599],
['ID2', 54.5890365, 12.5865499],
['ID3', 50.5170365, 10.3888599],
]
b = []  
for id, lat, lon in a:
for id2, lat2, lon2 in a:
if id != id2:
d = distance(lat,lon,lat2,lon2)
b.append([id,id2,d])
print(b)