Рассчитать расстояние от одной точки до всех остальных

Question

Я работаю со списком данных ID, X и Y для местоположений пожарных гидрантов.Я пытаюсь найти три ближайших пожарных гидранта для каждого пожарного гидранта в списке.

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

IЯ пытался реализовать это с помощью цикла for, но у меня возникли проблемы, потому что я не могу сохранить исходные данные точек при повторении списка точек.

Есть ли прямой прямой способ рассчитать расстояние от одной точки до каждой из других точек и повторить это для каждой точки в списке?Я очень плохо знаком с Python и не видел ничего о том, как сделать это онлайн.

Любая помощь будет принята с благодарностью.

Answer 1

Если у вас есть геолокация, мы можем выполнить простой расчет расстояния (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)

Answer 2

Вам не нужно рассчитывать все расстояния всех точек до всех остальных, чтобы получить трех ближайших соседей для всех точек.

A Поиск по дереву kd будет намного более эффективным, посколькук его сложности 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]

Answer 3

Вот, пожалуйста. Допустим, у вас есть список ввода с этим форматом [[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, чтобы получить расстояние.

Надеюсь, это поможет;)